漸化式：nCrの計算(C言語)

こんにちは<_ _>
nCrを求める問題について質問です
（n個の中からr個を選ぶ組み合わせの数nCrを求めるという問題です）

ここで漸化式というものを用いよとあり、サイトなどで漸化式について
感覚的な理解はつかめましたが、「プログラムで組め」となると完全にお手上げです；；

漸化式の詳しい解説用法とプログラム（ヒントなどでもいいのでお願いします<_ _>）をお願いします

#include<stdio.h>

long combi(int,int);

int main(void)
{
int n,r;

for(n=0;n<=5;n++){
for(r=0;r<=n;r++)
printf("%dC%d=%ld ",n,r,combi(n,r));
printf("\n");
}

return 0;
}

long combi(int n,int r)
{
long p=1;


処理


return p;
}
外郭まではソースで指示がありますが処理がまったくわかりません
どうかよろしくお願いします<_ _>

No.4 ベストアンサー 回答者： koko_u_ 回答日時： 2007/06/01 15:36

>漸化式について色々調べてみましたがまだ大体の機能・・・みたいな

>ものしか解らず、詳しい使用法などまだ理解が不足しております。

最初の回答の例で言うと、

a(n+1) = 2*a(n) + 1 のように、n+1 番目の項をそれより手前の n 番目の項で定義するのが漸化式。いろんなバリエーションがあるけど説明省略。
当然、「最初の項」が必要で、例えば a(0) = 0 とすると

a(1) = 2*a(0)+1 = 1
a(2) = 2*a(1)+1 = 3
a(3) = 2*a(2)+1 = 7
...

と「すべてのa(n)」が定義できます。

プログラムで同じことをする場合には、これをそのまま書けば

int func_a(int n) {
　if ( n <= 0 ) {
　　return 0;
　} else {
　　return 2*func_a(n-1)+1;
　}
}

とかすれば、func_a(3) を計算する時に、func_a(2) -> func_a(1) -> func_a(0) が順に呼出されて、

func_a(0)で 0 が返ってくるので、
func_a(1) で 2*0+1 が戻され、
func_a(2) で 2*(2*0+1)+1 が戻され、
最終的に 2*(2*(2*0+1)+1)+1 が呼出し側に戻ってきます。

No.5 回答者： AsanoNagi 回答日時： 2007/06/02 09:27

nCr の漸化式については、既に、No.2 の方の回答にありますが、これは、こういう意味です。

１）n 個の中から r 個選ぶ選び方の数を知りたい
２）でも、計算方法がわからない

３）簡単なケースならわかる
　　・n 個のなかから、１個取り出す組み合わせは、n
・n 個のなかから、n個取り出す組み合わせは、１
　　　※全部を取り出すという１つの方法があるから。

４）複雑なケースを単純なケースに分解してみよう
　　・n 個のなかから、r 個取り出す方法を考える
　　・まず、n 個を n - 1 個と、1 個に分けてみる
　　・n - 1 個なかから、r 個取り出す方法を考えてみよう
　　　あ、これは、(n - 1)Cr だから、あとで計算してみよう
　　　※できたことにしておこう
　　・このままだと、別にしておいた１個を無視することになる。
　　　この１個をどうしようか
　　・n - 1 個の中から、r - 1個取り出して、これに、残った１個を
　　　足すと、n 個のなかから、（残った１個を含めて）r個とった
　　　ことになる。
　　　あ、これは、(n - 1)C(r - 1) のことだ
　　　これも計算できたことにしよう

というわけで、全体では、
nCr = (n - 1)Cr + (n - 1)C(r - 1) となります。
ただ、単純にこの計算をすると終わらないので、計算を終える条件が必要です。
それが、
nC1 = n と nCn = 1 になります。

これを式にしたのが漸化式です。
漸化式というのは、ひとつ隣（n → n - 1 や、r → r - 1）との関係がわかれば、なぜか計算できてしまうという魔法のようなものです。
その分、計算の経過を全部追いかけるのは大変ですが。

No.3 回答者： koko_u_ 回答日時： 2007/06/01 11:27

>漸化式の定義そのままです。

>これのどこがわからなかったのですか?

メインのループで C(0, 2) を呼んでるから、そこでクラッシュとか。

この回答へのお礼

早速の回答ありがとうございました<_ _>
漸化式とう言葉を今日始めて目にしたのでまだ理解に不足している
ところがありまして・・・失礼な質問でしたらすいません＞＜

漸化式について色々調べてみましたがまだ大体の機能・・・みたいな
ものしか解らず、詳しい使用法などまだ理解が不足しております。
（数学に関する知識は乏しいです）

プログラムになるとそれをどう組めばいいのか解りませんでした・・・

お礼日時：2007/06/01 13:59

No.2 回答者： episteme_at_goo 回答日時： 2007/06/01 11:21

int C(int n, int r) {

　if ( r == 1 ) return n; // C(n,1) = n
　if ( n == r ) return 1; // C(n,n) = 1
　return C(n-1,r) + C(n-1,r-1);
}

漸化式の定義そのままです。
これのどこがわからなかったのですか?

No.1 回答者： koko_u_ 回答日時： 2007/06/01 11:15

>ここで漸化式というものを用いよとあり、

漸化式が何かは OK ？

a(n+1) = 2*a(n) + 1

みたいなアレね。

n_C_r を n_C_(r-1) で表わして n_C_0 まで降下するのが簡単かな。
他にもパスカルの三角形を使ってもいいし。お好きなものでどうぞ。