再帰の問題です。

質問

AOJの問題で、C言語で書いています。

ある解答者様のコードが自分の理解に深まると思い、見ているのですが、解答者様の作った関数のところの動作がよくわかりません。

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

解答例です。分かるところ、分からないところを書いていきます。

#include<stdio.h>

int n,s,a;//グローバル変数。

void dfs(int i,int sum,int m){//ここでいう、i,sum,mが何を指しているのか分かりません。
if(m==0 && sum==s){a++;return;}
if(i==10 || m==0)return;
dfs(i+1,sum+i,m-1);/*再帰をしています。しかし、どうしてここに自分と同じ関数を２つ、入れている　　　のか、分かりません。あと、どうしてiを足したり、１引いた数を代入しているのでしょうか?*/
*/
dfs(i+1,sum,m);　　
}
int main(){
while(scanf("%d%d",&n,&s)!=EOF){//Ctrl+zを押さない限り、無限ループします。
if(n==0 && s==0)break;//問題文通り、２つとも０だったらループを表すwhileから抜けます。
a=0;
dfs(0,0,n);//ここもわからないです。ただ、関数dfsの動きが分かれば、分かると思います。
printf("%d\n",a);
}
return 0;
}

再帰は今苦戦していますので、ここでもっと理解を深め、自作関数で使えるようになりたいです。
長文失礼しました。
よろしくお願いします。

回答No.2

Ogre7077 · ベストアンサー

この関数は再帰を「問題の分割」に使用しています。

例題通り s=6,n=3 とした場合、解くべき問題は

[0,1,2,3,4,5,6,7,8,9] から 3 個を取り出した合計が 6

一番最初の再帰によって、この問題は以下の二つに分解されます

0 と [1,2,3,4,5,6,7,8,9] から 2 個を取り出した合計が 6
_ と [1,2,3,4,5,6,7,8,9] から 3 個を取り出した合計が 6

さらに分割されて

0,1 と [2,3,4,5,6,7,8,9] から 1 個を取り出した合計が 6
0,_ と [2,3,4,5,6,7,8,9] から 2 個を取り出した合計が 6
_,1 と [2,3,4,5,6,7,8,9] から 2 個を取り出した合計が 6
_,_ と [2,3,4,5,6,7,8,9] から 3 個を取り出した合計が 6

この様に分割してゆき、分割できなくなるまで再帰を続け、その際に目的を達している(sum==s)ならばカウント(a++)しています。
これによって、すべての組み合わせを探索することができます。

余談ではありますが、このプログラムは大域変数が不用意に使われていて読み辛いです。
以下の様にすれば多少は数学っぽくなり読みやすくなるかと。

int dfs(int i, int sum, int m) {
　if (m==0 && sum==0) return 1; // 条件を満たす組み合わせ
　if (i==10 || m==0) return 0; // 条件を満たさない
　retun dfs(i + 1, sum - i, m-1) + dfs(i + 1, sum, m); // 問題を二つに分割　
}
printf("%d\n", dfs(0, s, n));

補足

返事がかなり遅くなり、誠に申し訳ありません。

事情があり、家から離れていました。

詳しい解説本当にありがとうございます！

じっくりと今から読んでみて、分からないところがあったら再度お聞きするかもしれませんが、その際はよろしくお願いします。

回答No.1

Tacosan

動的計画法.

お礼

回答ありがとうございます！

途中で問題が出たときに
「その状態までの計算結果を記憶させる」という方法を採るのを『動的計画法』というのですね。

実は何回か関数内にprintfをいれて、動きをみたりしているのですが、再度やってみようと思います。

アドバイスありがとうございます！