- ベストアンサー
nCrの計算
nCrの計算のプログラムを nCr=n!/(r!(n-r)!) を用いて再帰的関数を使って書いたのですが、もし nCr=n(n-1)(n-2)・・・(n-r+1)/r! であることを用いて、nからmまでの掛算を実現する2引数の関数を定義して、再帰的関数呼び出しを用いたnCrのプログラムを作成するとしたらどうなるでしょうか。 関数x!の定義は、関数の宣言をlong factorial(int x)として、 if (x==0) return(1); else return(x*factorial(x-1)); となることは分かるのですが、 2引数の関数m(m+1)・・・nはどう作れば良いのか全くわからないので、プログラムが書けない状態です。アドバイスお願いします。
- MP4-18
- お礼率68% (20/29)
- C・C++・C#
- 回答数3
- ありがとう数4
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
いまいち、質問の意味がわかりにくいのですが、mからnまでの積を再帰的に計算する関数を作りたいのでしょうか？ それでしたら int factorial (int m, int n) { if (m == n) return m; else return m * factorial(m + 1, n); } で良さそうですが…。
その他の回答 (2)
- επιστημη（@episteme）
- ベストアンサー率46% (546/1184)
再帰を用いて nＣr : comb(n,r) を求めるのなら、 comb(n,r) = comb(n-1, r-1) + comb(n-1, r) を使った方が楽ではないかと。 int comb(int n, int r) { if ( n == r ) return 1; if ( r == 0 ) return 1; return comb(n-1, r-1) + comb(n-1, r); }
お礼
これは気づきませんでした。そうですね、漸化式の形ででもできますね。ありがとうございます。
nCr=n(n-1)(n-2)・・・(n-r+1)/r! で「n(n-1)(n-2)・・・(n-r+1)」は nを基準にr回ループさせればいいのではないでしょうか？ ベーシックでいいでしょうか？ というより、どんなプログラムでもforはあると思うのでそれを用いればよいかと思います。 ベーシックしかわからないのでベーシックで記述しておきます。n，rはすでに入力されているとして、メインプログラムだけ記述しておきます。 10 b=1;d=1 20 for a=1 to r 30 b=b*(n-a+1) 40 next a 50 for c=1 to r 60 d=d*c 70 next c 80 e=b/d で、答えはeとなりませんか？
お礼
すみません、私はベ-シック知らないんです。どうも、ご回答ありがとうございました。
関連するQ&A
- nCrの値が表示されない
Ｃ言語でnCrの値を求めるプログラムをnCr＝n!/(r!*(n-r)!)を元に、再帰を用いて階乗を求める関数を用いて作成したのですが、nとrがn=40,r=11等の大きな値になるとnCrの値をunsigned long intで定義していても値が表示されませんでした。桁あふれではないんですが何故でしょうか？ＰＣの構造にそこまで詳しくないので、詳しい理由を教えてください。
- 締切済み
- C・C++・C#
- nCrはどうあらわせばい？？
キーボードから二つの正の整数n，r を入力し，組み合わせの数nCr を計算して画面表示するプログラムを作成せよ．ただし，組み合わせの数を計算する関数のプロトタイプをint combination( int, int )とし，my_scanf()をキーボードから二つの正の整数n，r を入力する関数，kaijo() を階乗を求めるプログラムとする． という問題なんですが #include <stdio.h> int my_scanf(void){ int n; do{ scanf("%d",&n); }while(n <= 0); return n; } int kaijo(int m){ int i,x = m; for(i=1;i<m;i++){ x *= i; } return x; } int combination( int m, int w){ int ncr; ncr = m/w; return ncr; } int main (void){ int pos,sum_n,sum_r,answer; printf("n = "); pos = my_scanf(); sum_n = kaijo(pos); printf("r = "); pos = my_scanf(); sum_r = kaijo(pos); answer = combination(sum_n,sum_r); printf("nCr = %d",answer); return(0); } 結果的にはｎ！／ｒ！を求めるプログラムに・・・・。 combination関数内を書き直せばいいのでしょうか？
- ベストアンサー
- C・C++・C#
- 再帰を用いた場合の計算量
nの階乗を再帰呼び出しを用いて計算する以下のプログラムの計算量はいくらになるのでしょうか？ 調べてみてもどこにも記述されていなくて困っています． int factorial(int n) { if(n > 0) return (n * factorial(n - 1)); else return (1); } また，できれば求め方も教えていただけると嬉しいです．
- 締切済み
- C・C++・C#
- 再帰呼び出しの計算量
再帰呼び出しを用いた関数の計算量を求める方法がわからないので質問させていただきます． xのn乗を再帰呼び出しを用いて求める関数に関して，計算量を求める問題なのですが，どのような方針で求めればよいのでしょうか？ int exponent(int x, int n) { if(n == 0){ return 1; }else{ return x * exponent(x, n-1); } } exponentがn回呼ばれるからO(n)というのは間違いでしょうか？
- ベストアンサー
- C・C++・C#
- 漸化式：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; } 外郭まではソースで指示がありますが処理がまったくわかりません どうかよろしくお願いします<_ _>
- ベストアンサー
- C・C++・C#
- c言語の関数定義について
次の関数定義を考える． int f(int x) {if (x > 0) {return x * f(x-1);} else {return 1;} } この関数f と働き（すなわち，引数と戻り値の関係）が同じで再帰呼出(recursive call) を使わない関数g をC で定義せよ．ただし，オーバーフロー(overflow) については考慮しなくてよい． ”この関数f と働き（すなわち，引数と戻り値の関係）が同じで再帰呼出(recursive call) を使わない関数g をC で定義せよ”って理解できません、どのように定義したいいか、ご教授お願いします。
- ベストアンサー
- C・C++・C#
- 桁数が増えると正しく計算されません。
今、Perlで作成したモジュールをCに移しています。 Perlではうまく動いているのですが、Cで作った以下のプログラムでは、 nを13以上にすると、値が正しく計算されなくなります。 ユーザ関数をdoubleにしたりすると、全て0になったりコンパイルできません。 せめてdouble型の最大値くらいまでは計算したいと考えています。 また、下のプログラムでC言語ならではの修正すべき点があれば教えてください。 よろしくお願いします。 #-----------------------------------------------------------# #include <stdio.h> int factorial(int j); int main(void) { /* 試行回数n回 */ int i, j, n, r, x; int combination; //printf("試行回数は？"); //scanf("%d", &n); n=13; for (i=1; i<=n; i++){ for (r=0; r<=i; r++){ combination = factorial(i) / (factorial(r) * factorial(i - r)); printf("%5d",combination); } printf("\n"); } } int factorial(int j){ int i; int x; x = 1; for (i = 1; i <= j; i++){ x *= i; } return x; } #-----------------------------------------------------------#
- ベストアンサー
- C・C++・C#
- 困ってます…nCrを求めるＣ言語プログラミング
nCr、つまりn個のうちr個を取り出すときの場合の数を求めるプログラミングを作りたいのですが、どうもうまくいきません。 関数combinationを作って求めるという指定もあり、自分で出来るとこまで作ってみたのですが訳がわからなくなってしまい、かなり困っています…； コンパイルは出来るのですが実行してもセグメントエラーが出るばかりで… すみませんがご指摘していただけないでしょうか…？ #include<stdio.h> //階乗を計算する関数 int fact(int num){ int i; if(num < 0){ return -1; } else if(num == 0){ return 1; } else if(num == 1){ return 1; } else { i = num * fact(num - 1); return i; } } //コンビネーションを計算 int combination(int n, int r) { int fact(int num); int i; i=fact(n)/fact(r)/fact(n-r); return combination(n-1, r-1)-combination(n,r-1); } int main(void) { int n, r; while ( printf("n r を入力して下さい。"), scanf("%d%d", &n, &r) == 2 ) { printf("nCr(%d,%d)=%d\n", n, r, combination(n, r)); } return 0; }
- 締切済み
- C・C++・C#
- CからPerlへの変換がうまくいきません
Cで作った二項分布の計算プログラムをPerlで書き直しています。 ユーザ関数の使い方がよくわかりません。 どこが間違っているか教えていただけませんでしょうか？ 余談ですが、ソースが左揃えになるのを防ぎたいのですが…。 #!/usr/bin/perl $p = 0.5, $s = 0, $t = 0, $combination = 0, $binarydistribution = 0; printf("n="); $n = <STDIN>; for ($r = 0; $r <= $n; $r++){ $combination = &factorial($n) / (&factorial($r) * &factorial($n - $r)); $s = 1; for ($i = 1; $i <= $r; $i++){ $s = $s * $p; } $t = 1; for ($i = 1; $i <= $n - $r; $i++){ $t *= (1 - $p); } $binarydistribution = $combination * $s * $t; printf("%.15f\n", $binarydistribution); } sub factorial{ $j = @_; $x = 1; for ($i = 1; $i <= $j; $i++){ $x *= $i; } return $x; }
- ベストアンサー
- Perl
お礼
できました! factorial(m+1,n)というところに気づかない未熟者でした。ご回答、ありがとうございました。