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

質問

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になっているのかということです。
どなたかわかる方がいらっしゃったらよろしくお願いします。

回答No.3

chie65536（@chie65535） · ベストアンサー

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

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

nに４を代入すると使える要素は、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][]

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

お礼

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

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

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

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

回答No.5

Tacosan

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

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

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

お礼

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

回答No.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で「セグメンテーション違反です (コアダンプ)」でした。

お礼

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

回答No.2

Tacosan

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

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

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

お礼

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

回答No.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]も同様です。

お礼

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