こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

設定した値が意図せぬ値に

POJ 3176の問題です。
http://poj.org/problem?id=3176


#include <iostream>
#include <algorithm>
#define MAX 100
using namespace std;


int main()
{
int n;
cin >> n;
int line[n-1][MAX];
int num[n-1][MAX];
cin >> line[0][0];
if(n==0)
{
cout << 0 <<endl;
return 0;
}
else if(n==1)
{
cout << line[0][0] << endl;
return 0;
}
for (int i =1;i < n;i++)
{
for (int j=0;j < i+1;j++)
{
int x;
cin >> x;
line[i][j]= x;
}
}
for (int k= 0 ; k<n;k++)
{
num[n-1][k]= line [n-1][k];
}

for (int k= n-2; k > 0 ; k--)
{
for (int l=0 ; l<k+1; l++)
{
num[k][l] = max (num[k+1][l],num[k+1][l+1]) + line[k][l];
}
}

num[0][0] = max(num[1][0],num[1][1]) + line[0][0];

cout << line[0][0] <<" "<<num[0][0]<<endl;
return 0;
}

入力
4
3
1 3
1 2 3
1 3 4 5

出力
1 12


最後に出力でline[0][0]をするようにしているのはバグチェックのためです。
ここで僕がわからないのはどうしてline[0][0]が3で宣言し、ほかでいじっていないにも関わらず、最後に1になっているのかということです。
どなたかわかる方がいらっしゃったらよろしくお願いします。

投稿日時 - 2012-04-27 11:11:39

QNo.7443882

困ってます

質問者が選んだベストアンサー

>int line[n-1][MAX];
>int num[n-1][MAX];

こうすると、使える要素は、line[0][0]~line[n-2][99]の範囲だけど、判ってる?

nに4を代入すると使える要素は、line[0][0]~line[2][99]の範囲だけど、判ってる?

たぶん、このままだと、num[n-1][]にアクセスするとline[0][]のメモリをアクセスすると思う。

int line[10][100];
int num[10][100];

って状態で、num[10][]に書き込むと、line[0][]があるメモリにアクセスする。

メモリの物理配置が以下のようになっていると想定してみよう。

num[0][]
num[1][]
num[2][]
num[3][]
num[4][]
num[5][]
num[6][]
num[7][]
num[8][]
num[9][]
line[0][] ← ここはnum[10][]と同じアドレス
line[1][] ← ここはnum[11][]と同じアドレス
line[2][] ← ここはnum[12][]と同じアドレス
line[3][] ← ここはnum[13][]と同じアドレス
line[4][] ← ここは(以下略)
line[5][]
line[6][]
line[7][]
line[8][]
line[9][]

「配列の要素を何個確保したのか」を良く考えなさい。

投稿日時 - 2012-04-27 14:31:54

お礼

>>int line[n-1][MAX];
>>int num[n-1][MAX];

>こうすると、使える要素は、line[0][0]~line[n-2][99]の範囲だけど、判ってる?

初心者でこういう初歩的なこともわかっていませんでした。
本当に教えてくださってありがとうございます。

後半のメモリについてご教授してくださったことも教科書も教科書を読んだ限りでは曖昧だったのですごい助けになりました。

投稿日時 - 2012-04-27 17:23:15

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(5)

ANo.5

C++98/C++11 の規格に従う限り (どちらも「定数式」とあるので) だめなはずです>#4. GCC では標準で通していると思いますが, -pedantic オプションをつけて
g++ -pedantic -ansi -std=c++98 これ
とかやると警告が出ます. なお, MSC ではきっちりエラーにしてくれます.

C99 や C11 なら OK なんだけど....

あと, 「n がでかい状況」もやばいっちゃやばいですが, それよりもこんなところで 0 や 1 のチェックをしちゃいかんでしょう.

投稿日時 - 2012-04-27 16:16:25

お礼

環境によればエラーが出るようなことなんですね

投稿日時 - 2012-04-27 17:19:57

ANo.4

Wr5

>int line[n-1][MAX]; って. 規格的にはアウトじゃないかなぁ (n が定数じゃない).

C++なら…OKでしたかね?

>#include <iostream>

なのでC++かと思われますが。

ちなみに、
c++ (GCC) 4.4.6 20110731 (Red Hat 4.4.6-3)
ではビルドは通りました。(CentOS6.2の標準パッケージ)
結果は異なりましたけどね。
出力
3 14
でした。(まぁ、どのみち正常動作は期待できないので結果がどうなろうがアレですが。)

>よしんば OK だとしても, この後で n のチェックするようじゃだめ.

スタックオーバーフローかコアダンプか……。
100000000で「セグメンテーション違反です (コアダンプ)」でした。

投稿日時 - 2012-04-27 15:24:10

お礼

指摘ありがとうございます

投稿日時 - 2012-04-27 17:20:29

ANo.2

本題は終わってるような気がするんだけどちょっと気になったので:

int line[n-1][MAX]; って. 規格的にはアウトじゃないかなぁ (n が定数じゃない).

よしんば OK だとしても, この後で n のチェックするようじゃだめ.

投稿日時 - 2012-04-27 13:57:35

お礼

ご指摘ありがとうございます

投稿日時 - 2012-04-27 17:23:35

ANo.1

Wr5

単純にバッファオーバーランしているだけではありませんか?

>cin >> n;
でnに4が入ると、
>int line[n-1][MAX];
>int num[n-1][MAX];

int line[3][MAX];
int num[3][MAX];
になります。

で…
>num[n-1][k]= line [n-1][k];
ここでバッファオーバーランしています。
num[3][k]はありませんから。
num[0][0]~num[0][99]、num[1][0]~num[1][99]、num[2][0]~num[2][99]まででnum[3][]は無い。
ということは理解されてます?
# line[n-1][k]も同様です。

投稿日時 - 2012-04-27 11:42:45

お礼

バッファーオーバーランっていうんですね
ありがとうございます

投稿日時 - 2012-04-27 17:24:04