- ベストアンサー
nCmの関数
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
以下のソースをコンパイルして実行して下さい。 ------------------------ #include <stdio.h> int comb1(int n,int m){ if (m==0){ return 1; }else{ // return((n-m+1)/m)*comb1(n,m-1); ・・・式１ return comb1(n,m-1)*(n-m+1)/m; } } main() { int a1,a2,a3,a4,a5; a1 = comb1(4,0); a2 = comb1(4,1); a3 = comb1(4,2); a4 = comb1(4,3); a5 = comb1(4,4); printf("a1=%d a2=%d a3=%d a4=%d a5=%d\n",a1,a2,a3,a4,a5); return 0; } ----------------- 本来、すなおに書けば式１ですが、除算による切り捨てが発生するため、除算を最後に行っています。
その他の回答 (2)
- kabaokaba
- ベストアンサー率51% (724/1416)
除法を使ってる段階で駄目です． 結果が整数になるとは限りません． それと括弧の位置が間違ってます． 演算の優先順位を考えましょう． なお，再帰でこれを書くときには， パスカルの三角形を使います． 再帰の停止条件はもっとちょっと複雑になりますし， 工夫しないと再帰呼び出しの回数が多くなりすぎて 遅くて使い物にならなくなります．
お礼
括弧の位置は間違えました 実際に使うかどうかではなく、あくまで試験問題のようなものだとお考えください（事実、過去問の１つです 「nCmを解くには(n-m+1)/m*nCm-1という方法がある、これを用いて/*****/の部分を埋めよ」という問題です 再帰を使えるかどうかを問う問題のようなので、実際に動かして小数点で困る場合や速度・オーバーフローなどは無視してかまわないようです comb1の中に結果をいれていくしかないのかなぁと思うのですが、入れ方がよく分からずにいます
- jacta
- ベストアンサー率26% (845/3158)
「再起」というのがよく分からないのですが、もしかして「再帰」のことでしょうか？
お礼
ああ、すみません 変換をミスしています 仰るとおり、再帰です mが0になるまでreturnでcomb1を呼び出し、(n-m+1/m)*nCm-1をやるようなのですがよく分からないのです
関連するQ&A
- 組み合わせ
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!という式を使うのですがよく分かりません。よろしくお願いします。
- 締切済み
- C・C++・C#
- アッケルマン関数
アッケルマン関数 ack(m,n)={ n+1 m=0のとき { ack(m-1,1) m>0,n=0のとき { ack(m-1,ack(m,n-1)) m>0,n>0のとき をプログラムしたいのですが、再帰を使ったプログラムがうまく実行できません。どこがいけないのでしょうか？ #include<stdio.h> int m,n; int ack(int m, int n) { if (m = 0) return n + 1; if ((m > 0) && (n = 0)) return ack(m - 1, 1); else return ack(m - 1, ack(m, n - 1)); } main() { int m,n; printf("アッケルマン関数ack(m,n)を計算します。\n"); printf("自然数m,nを入力してください\n"); scanf("%d",&m); scanf("%d",&n); printf("アッケルマン関数ack(%d,%d)の値は%dです。\n", m, n, ack(m,n)); }
- ベストアンサー
- C・C++・C#
- 階乗の出力について
Cを勉強中の者です。再起コールを使った階乗計算の結果を出力するプログラムをつくったのですが、もし再起コール(関数 kaijyo)を使わずにfor文などを使って同じように、階乗計算を行いたい場合どのようにすればいいでしょうか？ 以下がそのソースコードです。説明が不足であればまた付け加えますのでよろしくおねがいします。 #include <stdio.h> int kaijyo(int a); int main(void) { int a; a = kaijyo(6); printf("6! = %d\n", a); return 0; } int kaijyo(int n) { if(n == 1) return 1; else return n*kaijyo(n-1); /*これを使わずに6!の結果を出したい/* }
- ベストアンサー
- C・C++・C#
- C言語の関数について。
学校の課題がわからないので教えてください。 1. 次の関数recfunc()は関数内で自分自身を呼び出す再起関数である。 int recfunc(int x){ if(x<=0)return -1; else if(x==1) return 3; else return 3*recfunc(x-1)-2; } 引数に1,2,3,4,5,...を与えたときの返り値を求めよ。その結果から、一般に 整数値nが与えられたとき、どのような値が計算されるか推測せよ。 一体何を返す関数だろうか?またどのようにその計算が実現されているか を簡潔に述べよ。 2.どのような再帰関数も、再帰を用いない関数に書き換えることができる。 問題1の関数recfunc()と同じ引数、同じ返り値をもつ再帰を用いない関数 func()を作成せよ。 ２問も質問してすみません。 このプログラミングのレポートを提出しなくてはならないので困ってます。 何卒よろしくお願いします。
- 締切済み
- C・C++・C#
- パスカルのピラミッドを作りたいのですが...
*/ 入力した段数のパスカルの三角形をつくる */ #include <stdio.h> /*---nCr値を返す---*/ int comb(int n,int r) { if (r == 0 || r == n) return (1); else if (r == 1) return (n); else return (comb(n - 1,r-1) + comb(n - 1,r)); } int main(void) { int ln; int i,j; do{ printf(" 段数を入力して下さい："); scanf("%d",&ln); }while (ln < 1); if (r == 0 || r == n) return (1); else if (r == 1) return (n); else return (comb(n - 1,r-1) + comb(n - 1,r)); } int main(void) { int ln; int i,j; do{ printf(" 段数を入力して下さい："); scanf("%d",&ln); }while (ln < 1); for (i = 0; i < ln; i++){ for(j = 0;j < ln - i;j++) putchar(' '); for(j = 0; j < i; j++){ printf("%d",comb(i,j)); printf(" "); } putchar('\n'); } return (0); } と作ったら、うまく 1 1 1 1 2 1 1 3 3 1 とは表示されず、 1 1 2 1 3 3 1 4 6 4 となってしまいます。 どこを直せばよいのでしょうか。教えて下さるとうれしいです。 よろしくお願い致します。
- ベストアンサー
- C・C++・C#
- 組み合わせ プログラミング
ｃ言語についてです os linux コンパイラはgccです long fact2(int n,int m)を作成してfact2(n,m)を使って組み合わせを計算するプログラムを作れという問題で下記のように作りましたが コンパイルできません. エラーメッセージは 2-1.c:14: error: 関数 `fact2' への引数が少なすぎます 2-1.c:14: error: 関数 `fact2' への引数が少なすぎます 2-1.c:14: error: 関数 `fact2' への引数が少なすぎます です 関数のとこが違うと思うですが どうしたらいいのかわかりません それともなにか他のとこが違うのでしょうか？ #include <stdio.h> long fact2(int,int); main() { int n, m; long c; printf(" nCm (n>m) \n"); printf("input n m ="); scanf("%d %d",&n, &m); c =fact2(n) / (fact2(m) * fact2(n-m)); printf("%dC%d = %ld\n",n,m,c); } long fact2(int n,int m) { int i; long c=1; for(i=1; i<=n; i++) c*=i; return(c); }
- 締切済み
- C・C++・C#
- C言語でシグマで総和を求める関数を作りたい
おかしな点がありましたらご指摘お願いします /* nの総和を求める関数 */ int sum(int n) { /* n-1 */ /* f(n) + Σ f(i) (n > 1) */ /* i=1 */ /* f(1) (n = 1) */ if (n > 1) return n + (n - 1) * (n / 2); /* 直接総和を返す*/ else if (n == 1) return 1; }
- 締切済み
- C・C++・C#
- 異なるn個の整数からr個の整数を取り出す組み合わせ
異なるn個の整数からr個の整数を取り出す組み合わせの数 nCrを求める関数 int combination(int n, int r){ /* ・・・ */} を作成せよ。なおnCrは以下のように定義される。 nCr = n-1Cr-1 + n-1Cr (ただし nC0 = nCn =1、nC1 =n ) (新版 明解C言語 入門編(柴田望洋 著) P.197 演習8-6) というので答えが int combination(int n, int r) { if((n>r) && (r>0)){ return combination(n-1,r-1) + combination(n-1,r); } else if(n==r || r==0){ return 1; } } ・という風になると教えてもらったのですがなぜこうなるのかが分かりません。 ・else if(n==r || r==0){ というのは削っても正常に動きますが、必要な物なのでしょうか？ ・またifを使うときは if→eise if →else の順に使って ２つの時は if→else と使っていたのですが 上のものはif→else ifと書いています。 加えてelse(n==r || r==0){ と書いたらコンパイルエラーになってしまいました なぜelse ifと書くのでしょうか？ 以上３点について教えてください。よろしくお願いいたします。
- ベストアンサー
- C・C++・C#
- 組み合わせ順列
nＣrを求める関数combination(n,r)をC言語で作りたいのですが、どうすればよいか教えてください。また、参考となるようなサイトを教えてください。僕の作った関数だと、すぐに桁あふれになってしまいます。そのことを考慮して、桁あふれにになりにくい関数もつくりました。これは パスカルの三角形の関係を使ったnＣr=n-1Ｃr +n-1Ｃr-1の関係を使っての再帰関数です。しかし、これだと結果を出すのに時間がかかってしまいます。僕がつくった関数をいくつか出しておきますのでいい考えがあれば教えてください。64Ｃ32が高速に正確に出れれば最高です。 long combination(int n,int r) { int i, a, b; long c; if(r>n/2) r=n-r; a= n; b= 1; c= 1L; for(i=0 ;i< r ;i++){ c= c* a/ b; a--; b++; } return c; } これはすぐに桁あふれになってしまう。 long combination(int n,int r) { int i, a, b; double c; if(r>n/2) r=n-r; a= n; b= 1; c= 1.0; for(i=0 ;i< r ;i++){ c= c/b*a; a--; b++; } return (long)c; } これはｃをdoubleにして計算する分、丸めこみが生じ誤差がでる。 long combination(int n,int r) { long c; if(r> n-r) r=n-r; if(r==0) return 1; else if(r==1) return n; else{ c= combination(n-1,r-1)+ combination(n-1,r); return c; } } これは誤差は出ず正確であるがいかんせん遅い！
- ベストアンサー
- C・C++・C#
- 再起になってますか？[C++]
再起を使って総和のプログラムをつくったのですが、ちゃんと再起に なってるのか自信がないので教えてください。 これはほんの一部のコードなんですが computeRecursiveSum()の中のreturn( computeSum() ); の部分があってるのかわかりません。 本やそこらのサイトをみてみるとこの部分は、 return(n+Sum(n-1)); という風になっているのですが 下のような書き方してもよろしいのでしょうか？ 一応、正しい答えはでます。 int Summation::computeSum() const{ int a=0; for (int i=0; i<=number; i++){ a = i*(i+1)/2; } return a; } int Summation::computeRecursiveSum() const { int n = number; if ( n < 0 ) return (-1); else if ( n = 0 ) return (0); else return( computeSum() ); }
- ベストアンサー
- C・C++・C#
お礼
回答ありがとうございます おそらく、問題としての回答は式１なのだと思います こういった書き方でも動くのですね、非常に勉強になりました 本当にありがとうございます