組み合わせ

質問

n個の集合からp個を取る組み合わせの総数を出力するプログラムなんですが
nCp=n!/p!(n-p)!という式を使い
#include<stdio.h>
int kaijo(int m);
int comb(int n,int p);
int main(void)
{
int i,j;
printf("n="); scanf("%d",&i);
printf("p="); scanf("%d",&j);
printf("comb(%d,%d)=%d\n",i,j,comb(i,j));
}

int kaijo(int m)
{
if(m>0) return(m*kaijo(m-1));
else return 1;
}

int comb(int n,int p)
{
if(n>0) return((n*kaijo(n-1))/(p*kaijo(p-1)*(n-p)*kaijo(n-p-1)));
else return 1;
}

と書いてみたのですがこれではnが大きいとＣ言語のint型で扱える最大値を超えてしまい正しい結果が出力されません。
　そこでint型を使ったままでnやpが大きい場合でもある程度出力できるようにしたいのですがどう改良したらよいのでしょうか？
おそらくnCp=n*(n-1)*・・・*(n-p+1)/p!という式を使うのですがよく分かりません。よろしくお願いします。

回答No.5

BLUEPIXY

効率は良くないですが、
//nCr=n-1Cr-1 + n-1Cr,nC0=nCn=1,nC1=n;より
unsigned comb(unsigned n, unsigned r){
if(r==0 || r==n) return(1);
if(r==1) return(n);
return (comb(n-1,r-1)+comb(n-1,r));
}
途中の計算結果を再利用するようにすると効率はよくなります。

回答No.4

jacta

あらかじめ計算して、結果を配列に格納しておくのが一番確実です。

回答No.3

Interest

> そこでint型を使ったままでnやpが大きい場合でもある程度出力できるようにしたい

「ある程度」とはどの程度ですか？それによってやり方が変わります。プログラムを設計するときは、最初に仕様を決めましょう。

それから、int は処理系依存ですので、16bitの処理系と32bitの処理系では扱える値の範囲が異なりますので注意が必要です。

回答No.2

migoreng

もっと大きい n の値を扱う必要がある場合は、n! に関するスターリングの公式を使う方法もあります。この公式は、n! は、(n の n乗) と (e の -n乗)の積にほぼ等しいというもの(ただし e = 2.718... は自然対数の底)で、n が十分大きいときに成り立ちます。
詳しくは、
- http://szksrv.isc.chubu.ac.jp/stirling/stirling.html
や、
- http://mathworld.wolfram.com/StirlingsApproximation.html
を参照してください。

回答No.1

migoreng

その式を使うのであれば、
int comb(int n, int p);
を、
int comb(int n, int p)
{
　　int w = 1;
　　int m;
　　for ( m = n; m > n - p; m-- )
　　{
　　　　w *= m;
　　}
　　return w / kaijo( p );
}
にしてみたらどうでしょうか。