ページ 1 ／ 1
再帰関数の宿題
Posted: 2007年7月08日(日) 18:17
by 羽流布
（問題）
組合せの総数（二項係数）nCr は次の関係式で定義できる．
nC0 = 1 (n >= 0)
nCn = 1 (n >= 1)
nCr = 0 (r > n)
nCr = n-1Cr + n-1Cr-1 (n > r > 0)
この式に従って再帰関数 unsigned int reccomb(int m, int n) を定義し，動作テストせよ．
ただし，関数 reccomb() には関数を呼び出した回数を数える機能を追加しておき，何回 reccomb() を呼び出したかも表示せよ．
なのですが、現在、下記の状況で行き詰まっています。
どのように再帰関数を使えばいいのか分からないのと、関数を呼び出した回数を数える方法が分かりません。
#include <stdio.h>
int count = 0;
int recfact(int n) {
return (n <= 1 ? 1 : n * recfact(n - 1));
}
unsigned int reccomb(int m, int n) {
count++;
if (m >= 0 && n == 0) {
return (1);
}
else if (m >= 1 && m == n) {
return (1);
}
else if (m < n) {
return (0);
}
else {
}
}
int main(void) {
int n, r;
printf("n C r の n と r を入力せよ．\n");
printf("n = "); scanf("%d", &n);
printf("r = "); scanf("%d", &r);
printf(" reccomb() の呼び出し回数：%d\n", count);
printf(" n C r = %d\n", reccomb(n, r));
return (0);
}
助言だけでもいいですので、よろしくお願いしますm(_ _)m
Re:再帰関数の宿題
Posted: 2007年7月08日(日) 18:45
by 組木紙織
一言助言を
>printf(" reccomb() の呼び出し回数：%d\n", count);
>printf(" n C r = %d\n", reccomb(n, r));
この部分ですが、
一度もreccomb()を呼ばずにcountを使っているの分かりますか？
countはreccomb()を呼び出した後に使わないと、絶対に0になります。
Re:再帰関数の宿題
Posted: 2007年7月08日(日) 19:14
by box
> int recfact(int n) {
> return (n <= 1 ? 1 : n * recfact(n - 1));
> }
この関数は不要ですね。
> else {
>
> }
ここには、
> nCr = n-1Cr + n-1Cr-1 (n > r > 0)
この式の右辺をreturnするような文を書けばよいです。
Re:再帰関数の宿題
Posted: 2007年7月08日(日) 21:53
by 羽流布
皆さん、助言ありがとうございますm(_ _)m
とりあえず、下記のような感じになったのですが、合っているのでしょうか？（特に呼び出し回数）
#include <stdio.h>
int count = 0;
unsigned int reccomb(int m, int n) {
int comb = 0;
if (m >= 0 && n == 0) {
return (1);
}
else if (m >= 1 && m == n) {
return (1);
}
else if (m < n) {
return (0);
}
else {
comb += reccomb(m - 1, n);
++count;
comb += reccomb(m - 1, n - 1);
++count;
return (comb);
}
}
int main(void) {
int n, r;
printf("n C r の n と r を入力せよ．\n");
printf("n = "); scanf("%d", &n);
printf("r = "); scanf("%d", &r);
printf(" n C r = %d\n", reccomb(n, r));
printf(" reccomb() の呼び出し回数：%d\n", ++count);
return (0);
}
/* 実行結果
n C r の n と r を入力せよ．
n = 32
r = 16
n C r = 601080390
reccomb() の呼び出し回数：1202160779
n C r の n と r を入力せよ．
n = 3
r = 2
n C r = 3
reccomb() の呼び出し回数：5
n C r の n と r を入力せよ．
n = 16
r = 12
n C r = 1820
reccomb() の呼び出し回数：3639
n C r の n と r を入力せよ．
n = 8
r = 4
n C r = 70
reccomb() の呼び出し回数：139
*/
Re:再帰関数の宿題
Posted: 2007年7月08日(日) 22:03
by box
> とりあえず、下記のような感じになったのですが、合っているのでしょうか？（特に呼び出し回数）
呼び出し回数は、reccomb()に入った直後に1回だけ加える方が、
多少なりともコード量が少なくてよいと思います。
今のままでも答えは正しいのですけれど。
また、組み合わせの数は、combという変数を使わなくても、式のとおりに
return reccomb(m-1, n) + reccomb(m-1, n-1);
と書く方がスッキリしているでしょう。
（追記）
実は、答えを早く求めるという観点からは、再帰呼び出しを使うと不利です。
最初の投稿で書かれていた階乗を計算する関数を使う方が、
計算時間の点では格段に有利です。
ところで、組み合わせの数と再帰呼び出し回数との間に
おもしろい関係があることにお気づきになりましたか？
時間があれば、なぜそういう関係があるのかについて
考えてみるのも一興でしょう。
Re:再帰関数の宿題
Posted: 2007年7月08日(日) 22:28
by 羽流布
> box さん
確かにこのコードでは結果を表示するまでに結構かかりました。（特に数字が大きい場合）
先生も言ってましたが、まさかここまで長いとは思いませんでした。（私のパソコンのスペックが低いこともあるでしょうが）
コードは下記のようにスッキリさせました。
#include <stdio.h>
int count = 0;
unsigned int reccomb(int m, int n) {
++count;
if (m >= 0 && n == 0) {
return (1);
}
else if (m >= 1 && m == n) {
return (1);
}
else if (m < n) {
return (0);
}
else {
return (reccomb(m-1, n) + reccomb(m-1, n-1));
}
}
int main(void) {
int n, r;
printf("n C r の n と r を入力せよ．\n");
printf("n = "); scanf("%d", &n);
printf("r = "); scanf("%d", &r);
printf(" n C r = %d\n", reccomb(n, r));
printf(" reccomb() の呼び出し回数：%d\n", count);
return (0);
}
では、本当に助かりました（汗）
Re:再帰関数の宿題
Posted: 2007年7月08日(日) 22:48
by 組木紙織
好みの問題になると思いますが、
次のように書いたらすっきりすると思います。
unsigned int reccomb(int m, int n) {
++count;
if (m >= 0 && n == 0) return (1);
if (m >= 1 && m == n) return (1);
if (m < n) return (0);
return (reccomb(m-1, n) + reccomb(m-1, n-1));
}
/*次はかなり細かい部分なので無視して下さってもかまいません。*/
引数は二項係数なので負になることは無いのでunsignedをつけたほうがいいのかな。
intだと負の値が入ったときを考える必要があるような気がします。
出題者側のミス、になるのかな。
戻り値にはunsignedがついているので少しきになりました。