AOJの問題で、質問があります。

質問

AOJの問題で考えても全然わからない問題があり、他の人の解答例を参考にしようと思い、見てみたのですが、一つ分からないところがあり、質問させていただきます。

問題です。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0089

自分が参考にしている解答例です。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=570672

以下は分かっていないところを書かせていただきます。

なお、コードは解答例と同じです。

include <stdio.h>
#include <string.h>

int max(int a,int b){
return (a > b) ? a : b;
}
/*上の数、i-1行目の数から、i行目の大きい数をとっていく関数だと思いましたが、じっくり考えてみると、何パターンかのdataの足し算をしていることに気づきました。まずは左端のみ足す場（data[i+1][0] += data[i][0];）、次に右端だけを足す場合（ data[i+1][i+1] += data[i][i];） 、そして
for(j = 1;j <= i;j++){
data[i+1][j] += max(data[i][j-1],data[i][j]);
}
という、端以外の数から足すものです。ここで分からないことは
・このdata[i+1][j] += max(data[i][j-1],data[i][j]);という解答はi+1行目から、i行目の大きな数を選んでいますが、i行目からi+1行目の隣の大きいほうの数を足すようにしないと、ただしい経路は求まらないと思うのですが、どうでしょうか？また、端のみを足しているdataは、どういう役割をしているのでしょうか？　試しに端だけを足す式を削除したら、間違いとなってしまいます。また、この関数はreturn などがないですが、どの値が残るのでしょうか？main関数内では、どのような役割をするのでしょうか？*/

void solve(int data[100][50],int cnt){
int i,j;

for(i = 0;i < cnt/2;i++){
data[i+1][0] += data[i][0];
for(j = 1;j <= i;j++){
data[i+1][j] += max(data[i][j-1],data[i][j]);
}
data[i+1][i+1] += data[i][i];
}
for(i = cnt/2+1;i < cnt;i++){
for(j = 0;j < cnt-i;j++){
data[i][j] += max(data[i-1][j],data[i-1][j+1]);
}
}
}

int main(){
int h,i,j,cnt,len,num;
int data[100][50];
char str[1024];

memset(data,0,sizeof(data));

i = 0;
cnt = 0;
while(scanf("%s",str) != EOF){
h = 0;
j = 0;
len = strlen(str);
while(h <= len){
if(h < len && str[h] != ','){
num = 0;
while(h < len && str[h] != ','){
num *= 10;
num += str[h]-'0';
h++;
}
data[i][j] = num;
j++;
}
h++;
}
i++;
cnt++;
}

solve(data,cnt);//ここでは、計算した結果、どのような値が帰ってくるのでしょうか？

printf("%d\n",data[cnt-1][0]);

return 0;
}

長文失礼しました。
よろしくお願いします。

回答No.1

kmee · ベストアンサー

コメントがまったく無いので、わかりずらいプログラムになってしまっています。
「何をしているか?」を考えてコメントを付けてみてはどうでしょうか。

> //ここでは、計算した結果、どのような値が帰ってくるのでしょうか？

voidですから、戻り値はありませんが、第一引数で指定した配列が変更されます。
どうしてそうなるか理解できない場合は、参考書等でポインタの勉強してください

> printf("%d\n",data[cnt-1][0]);
結果らしきものを出力している箇所はここだけです。
ということは
・data[cnt-1][0] が結果ではないだろうか?
と予想できます。すると
・配列 data には、もともと入力したデータが入っていたはず
・入力から出力までの間に solve関数を実行している
ということから、solve関数で配列dataが書き変わっているのでは?と予想できます。

○solve関数の動作
実際に、コンピュータになったつもりで、動作を追い掛けてはですか?

・i=0 のとき、
data[0] : a0
data[1] : b0 b1
data[2] : c0 c1 c2

data[i+1][0] += data[i][0];
→ data[1][0] += data[0][0] ;
→ data[1][0] +=a0

data[i+1][i+1] += data[i][i];
→ data[1][1] += data[0][0] ;
→ data[1][1] +=a0

j=1 は j<=iではないので、forループは実行されず

結果
data[0] : a0
data[1] : b0+a0 b1+a0
data[2] : c0 c1 c2

・i=1のとき
data[i+1][0] += data[i][0];
→ data[2][0] += data[1][0] ;
→ data[2][0] +=b0+a0

data[i+1][i+1] += data[i][i];
→ data[2][2] += data[1][1] ;
→ data[2][2] +=b1+a0

j=1
data[i+1][j] += max(data[i][j-1],data[i][j]);
→data[2][1] += max(data[1][0],data[1][1]);
→data[2][1] += max(b0+a0,b1+a0);

結果
data[0] : a0
data[1] : b0+a0 b1+a0
data[2] : c0+b0+a0 c1+max(b0+a0,b1+a0) c2+b1+a0

ここまで追い掛けたら、solveがどんな方法で結果をだそうとしているのか、わかるのではないでしょうか?

幅が広がっていく部分では、候補は1つしかありません。
あえてやるなら次のようになります。
for(j = 0;j <= i+1;j++) として
・data[i+1][0] += max(data[i][-1],data[i][0]); // ただし、範囲外となる data[i][-1]は0とする
・data[i+1][i+1] += max(data[i][i],data[i][i+1]); // ただし、範囲外となる data[i][i+1]は0とする
data[i][i+1]の方は、サイズを大きく取って、予め0にしておく、という方法で対応できます。
しかし、data[i][-1]は先に添字をチェックする必要があります。
それなら、候補が1つしか無い場合は、そのまま計算した方がいいのではないでしょうか。

お礼

なるほど！
具体的に書いてみると、この関数の動きが分かりますね！
やっと理解できました。ありがとうございます。
あと、ご指摘の通り、回答者様に理解されやすいような説明、書き方をしていくことを念頭に置き、今後はやっていこうと思います。