C言語関係掲示板

過去ログ

No790 nCrを求める関数 

[戻る] [ホームページ]
No.9861

再帰の問題
投稿者---かおる(2003/10/18 21:09:12)


異なるn個の整数からr個の整数を取り出す組み合わせの数nCrを求める関数を作れという問題なんですが。
数学の組み合わせ求めるときに使うやつです。
わかりません 自分で下のように書いてはみたものの結果はぜんぜん違います。
どう書けばいいんでしょうか?
nCrは以下のように定義される(C以外小さい字ですー。)
nCr=n-1Cr-1+n-1Cr(ただし nC0=nCn=1,nC1=n)
#include <stdio.h>
	
/*---階乗値を返す---*/
int fact(int n)
{
	if(n>0)
		return(n*fact(n-1));
	else
		return(1);
}
/*異なるn個の整数からr個の整数を取り出す組み合わせ数nCrを求める関数---*/
int	comb(int n,int r)
{
	
	int bunbo;
	int bunshi;
	int tmp;	/*求めた数*/
		if(n<=r)	bunshi=( n*fact(n-1));
		if(n>=r)		bunbo=( r*fact(r-1));
		tmp=bunshi/bunbo;
		return(tmp);
}
		
		
int main(void)
{
	int n1,r1;
	
	printf("整数を入力してください");
	scanf("%d",&n1);
	printf("なんこ整数を取り出しますか");
	scanf("%d",&r1);
	printf("組み合わせは%d通りある。",comb(n1,r1));
	return 0;
}



No.9863

Re:再帰の問題
投稿者---すがりん(2003/10/18 21:50:10)


        if(n<=r)
                bunshi=( n*fact(n-1));
        if(n>=r)
                bunbo=( r*fact(r-1));
    

条件判定が謎です
n>=r
に決まってますから、
bunshi=( n*fact(n-1));
は、n=rの時にしか実行されません。

ところで

>nCrは以下のように定義される(C以外小さい字ですー。)
>nCr=n-1Cr-1+n-1Cr(ただし nC0=nCn=1,nC1=n)

とあるのだから、再帰の問題だとすれば
これをそのまま再帰で書けということではないでしょうか?(階乗ではなく)

No.9865

Re:再帰の問題
投稿者---かおる(2003/10/18 22:40:04)


レスありがとうございます。

>条件判定が謎です
>n>=r
>に決まってますから、
>bunshi=( n*fact(n-1));
>は、n=rの時にしか実行されません。

その部分直しても間違いだろうし指摘されても。。。

>再帰の問題だとすれば
>これをそのまま再帰で書けということではないでしょうか?(階乗ではなく)

そうだと思いますが。
もうお手上げなんです。苦し紛れに階乗つかってやってる(>_<)


No.9869

Re:再帰の問題
投稿者---たか(2003/10/18 23:28:52)


nCrの定義をそのままプログラム化すればいいと思いますが。

#include <stdio.h>
	
/*---階乗値を返す---*/
int fact(int n)
{
	if(n>0)
		return(n*fact(n-1));
	else
		return(1);
}
/*異なるn個の整数からr個の整数を取り出す組み合わせ数nCrを求める関数 >nCr=n-1Cr-1+n-1Cr(ただし nC0=nCn=1,nC1=n)---*/
int	comb(int n,int r)
{
  if (r == 0 || n == r) return 1;
  if (r == 1) return n;

  return comb(n - 1, r - 1) + comb(n - 1, r);
}
		
		
int main(void)
{
	int n1,r1;
	
	printf("整数を入力してください");
	scanf("%d",&n1);
	printf("なんこ整数を取り出しますか");
	scanf("%d",&r1);
	printf("組み合わせは%d通りある。",comb(n1,r1));
	
  return 0;
}


No.9891

Re:再帰の問題
投稿者---かおる(2003/10/20 00:25:14)


なるほど〜わかりました。
どうもありがとうございました。