- ベストアンサー
再帰・組み合わせ
新しく再帰という概念を習い始めたのですが、組み合わせを求めるやり方がわかりません 組み合わせの公式通り（nCk → n!/k!(n-k)!）、例えば4C2なら答えは6通りになるのはわかるのですが、 public static int combinations(int n, int k){ if(k==n){ return 1; }else if(k=1){ return n; }else if(0<k && k<n){ combinations(n-1, k-1) + combinations(n-1, k) ←これで出来るらしいのです } } combinations(n-1, k-1)は意味がわかるのですが、combinations(n-1, k)これが組み合わせの公式にどうあてはまっているのかがわからず、 そして何故足してるのかがよくわかりません。どなたかお解かりになればお願いします
- lockwell
- お礼率35% (33/94)
- Java
- 回答数4
- ありがとう数2
- みんなの回答 （4）
- 専門家の回答
質問者が選んだベストアンサー
こんばんわ。 私も再帰処理とか懐かしいなと思って、ちょっと読みはじめて 不思議に思いました。 combinations(n-1, k-1) + combinations(n-1, k) 強引ですけど 上記式を（nCk → n!/k!(n-k)!）にあてはめて、展開すると もとの式と一致します。 ということは、（nCk → n!/k!(n-k)!） から combinations(n-1, k-1) + combinations(n-1, k)も導き出せるはずなのかなと思いました。 直訳すると「n[個]からk[個]選ぶ」組み合わせは (n-1)[個]から(k-1)[個]選ぶ、(n-1)[個]からk[個]選ぶ 組み合わせの和と等しい だと思いますが、なぜこの式なのかは分かりません。 すみません。
その他の回答 (3)
- osamuy
- ベストアンサー率42% (1231/2878)
http://www.ne.jp/asahi/search-center/internationalrelation/mathWeb/arithmetic/PrmtCmbnBinomialTheorem/PrmtCmbnBinomialThrm.htm#PascalTriangle たしかに高校の数学ですね。 実際に動かしてみて、デバッガやprint文出力で挙動を確認してみては。 頭が働かないときは体を動かすのもひとつの手。
- KDASH-XP
- ベストアンサー率46% (63/136)
同じような記述をネット上で見つけました。 （すみません、私自身が興味半分で調べているので、もう適当です。）
- koko_u_u
- ベストアンサー率18% (216/1139)
>そして何故足してるのかがよくわかりません。 順列、組み合わせ、高校生の頃に習いませんでしたか？
関連するQ&A
- 再帰呼び出しの計算量
再帰呼び出しを用いた関数の計算量を求める方法がわからないので質問させていただきます． 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#
- c言語の再帰で(関数呼び出し)+1がわからない
再帰がどのように処理されているのか理解するために、再帰の時に +1 してみたところ 0! = 1 1! = 2 2! = 5 3! = 16 4! = 65 5! = 326 6! = 1957 7! = 13700 8! = 109601 9! = 986410 10! = 9864101 となりました。 普通の階乗の値を求めた最後に +1され、それが戻されると思ったのですが違いました。 これはどういう処理がされているのでしょうか？ #include <stdio.h> int kaijo(int); int main() { int i; for (i = 0; i < 11; i++) printf("%d! = %d\n", i, kaijo(i)); return 0; } int kaijo(int n) { if (n == 0) return 1; else return n * kaijo(n - 1) + 1; }
- 締切済み
- C・C++・C#
- 再帰を用いた場合の計算量
nの階乗を再帰呼び出しを用いて計算する以下のプログラムの計算量はいくらになるのでしょうか？ 調べてみてもどこにも記述されていなくて困っています． int factorial(int n) { if(n > 0) return (n * factorial(n - 1)); else return (1); } また，できれば求め方も教えていただけると嬉しいです．
- 締切済み
- C・C++・C#
- 再帰関数について
非負の整数nに対して次のように定義された 関数F(n),G(n)がある。F(5)の値はいくらか。 関数 F(n)：if n=<1 then return1 else return n×G(n-1) G(n)：if n=0 then return0 else return n+F(n-1) (1)50 (2)65 (3)100 (4)120 正解 (2)65 以下解説 F(5)：5×G(5-1)=5×(G(4)) =5×(4+F(4-1))=5×(4+(F(3))) =5×(4+(3×G(3-1)))=5×(4+(+3×G(2)))) =5×(4+(3×(2+F(2-1))))=5×(4+(+3×(2+F(1))))) =5×(4+(3×(2+(1)))) =65 再帰関数についての知識が皆無なので 教えて頂きたいのですが、なぜ=後の5×は残るのでしょうか。 そもそも再帰関数とは、どんなことを言っているのでしょうか。 具体例を挙げて頂くか、分かり易いURLを教えて頂けると幸いです。 お手数ですが、上記について1つ1つ丁寧に解説して頂きたいです。 大変ご迷惑な質問かと思いますが、分かる方おられましたら、 お手数ですが、ご教授お願いします。 以上、よろしくお願い致します。
- ベストアンサー
- その他([技術者向] コンピューター)
- 組み合わせ
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#
- 再帰
他の質問と平行してしまい申し訳ありません。再帰について少々おききしたいのですが、 配列の中にある数字の中から最大値と最小値を再帰処理でもとめたいのですが、うまくいきません。 public int minMax(n, array, min, max){ // nは配列のサイズです。 min=max=array[n-1]; if(array[n-2]<min) min=array[n-2]; if(array[n-2]>max) max=array[n-2]; return minMax(n-1,array,min,max); ｝ 最初に比較するために min=max=array[n-1];と初期化したのですが、再帰処理ですからまた同じ初期化をしてしまうことになります。 forループなどを使えるなら初期化だけループの外でやれば済むのですが、再帰だとどのようにすればよいのでしょうか。 宜しくお願いいたします。
- 締切済み
- Java
- 異なる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#
- C言語での組み合わせの問題について
(環境はmacで, gcc 4.0.1を用いています) #include <stdio.h> main(void) { int n, k, nck; printf("n = "); scanf("%d", &n); printf(" k nCk\n"); k = 0; nck = 1; printf("%12d%12d\n", k, nck); for(k=1; k <= n; k++) { nck = nck * (n-k+1)/k; printf("%12d%12d\n", k, nck); } } とした場合, 入力した値n=29までは正しい答えが得られるのですが n=30以降では途中から答えが狂い始めます. この現象はなぜ起こるのでしょうか?
- ベストアンサー
- C・C++・C#
- 再帰プログラムで合ってるのか間違ってるのか
関数zeromade()を作ってプログラムを完成させよ。 プログラムは与えられた値から、0までを順に出力するものである。 例えば、5を入力したら、 5 4 3 2 1 0 と出力されるものである。 ただし、リカーシブ(再帰)プログラムで作成すること。 (つまりfor文やwhile文は出てこない。) main内部を変更してはならない。 という問題があり #include <stdio.h> #include <stdlib.h> int zeromade(int); int main() { int n; scanf("%d", &n); if (n < 3) { fprintf(stderr, "3 ijou no atai wo nyuuryoku site kudasai\n"); exit(1); } zeromade(n); exit(0); } int zeromade(int x) { if(x < 0){ ; }else{ printf("%d\n",x); return (x * zeromade(x-1)); } } とやってこれが正解なのか不正解なのかわからないので質問させていただきます コンパイルすると ５を入力 ５ ４ ３ ２ １ ０ と出ます 足りないことがあれば補足で説明します
- ベストアンサー
- C・C++・C#
- ヒープの探索の再帰
A[N]を利用したヒープのプログラムを作りました。 A[i]の親は、A[(i-1)/2]であるヒープです。 （上に行くほど小さい整数を格納） そしていまある整列されたヒープのなかからキーボードから入力した値ｘを検索する関数findを、 x ←検索する値 A[]←ヒープソートされた配列 n ←格納されているA[]の最後の添え字 として、 int find(int x, int *A, int i, int n) { if(A[i]==x){ printf("*\n"); /* ここの作業が行われているかを確認 */ return 1; } if(i>n)return 0; if(A[i]>x){ return 0; } else if (A[i]<x){ i = 2*i + 1; find(x, A, i, n); i++; find(x, A, i, n); } return 0; } というものを作ってみました。汚いかもしれませんが、とりあえず今はこれでいっぱいいっぱいです。 それで、当然のごとくうまくいきませんでした。 /**/内に書いたように、入力したｘがヒープ内にある場合は「*」が一応表示されるのですが、どうもfindは１を返してくれません。0を返してしまいます。見つけた後もまだ再帰をくりかえしえしているようです。 どこがいけないのでしょうか。
- ベストアンサー
- C・C++・C#
お礼
みなさんどうもありがとうございました！組み合わせと再帰のアルゴリズムがよくわかっていなかったのでこんがらがってしまいました。 ありがとうございました！