再帰の問題

[桜並木]

学校で出された課題をやっており、うまく結果が表示できないので質問します。課題の内容は、再起を使い組み合わせの結果を表示させるという課題です。現在数字を入力すると、間違った答えが出てしまいます。なので間違っているところを指摘してくれると助かります。c言語の知識は、習い始めたばかりなのであまりないです。

コード:

#include <stdio.h>
int count;
int fac(num);
int main(void)
{
	int n, r, fac_2 = 0, fac_3 = 1;
	puts("nCrの計算をします。");
	printf("nの値を入力してください:");
	scanf("%d", &n);
	printf("rの値を入力してください:");
	scanf("%d", &r);
	fac_2 = fac(n);
	for (count; count >= n; count--)
	{
		fac_3 = fac_3 * r;
		r--;
	}
	printf("%d C %d = %d\n", n, r, fac_2 / fac_3);
	return 0;
}

int fac (int num) {
	count++;
	if (num == 1) {
		return 1;
	}
	else {
		return num * fac(num - 1);
	}
}

[超初級者]

もう1個の方を見てください。

[超初級者]

こんな感じでしょうか。

コード:

#include <stdio.h>

int fac(int n, int r)
{
   return (n == r) ? r : n * fac(n - 1, r);
}

int main(void)
{
   int n, r;

   puts("nCrの計算をします。");
   do {
       printf("nの値を入力してください:");
       scanf("%d", &n);
   } while (n <= 0);
   do {
       printf("rの値を入力してください:");
       scanf("%d", &r);
   } while (n < r);

   printf("%d C %d = %d\n", n, r, fac(n, n - r + 1) / fac(r, 1));
   return 0;
}

[みけCAT]

fac_2に代入した後のループは、実質ループ無しのfac_3 = r--;と同じなので、多分おかしいですね。
また、ここでrの値を破壊しているので、出力の前半部分がおかしくなりそうですね。
そもそも、countはnが1以上なら実質nになるのに、わざわざグローバル変数を使っているというのもおかしいでしょう。

ヒント：nCr = n! / (r! * (n-r)!) (Wikipediaより)
オーバーフローしない程度の入力を与えるといいでしょう。

[桜並木]

ヒントを基に考えてみたのですが、またエラーが起きてしまいました。またどこがおかしいのかを指摘していただきたいです。

コード:

#include <stdio.h>
int fac(int num);
int fac_2(int num_2, int num_3);
int main(void)
{
	int n, r;
	puts("nCrの計算をします。");
	printf("nの値を入力してください:");
	scanf("%d", &n);
	printf("rの値を入力してください:");
	scanf("%d", &r);
	if (r == 0 || n == r) {
		printf("%d C %d = 1\n", n, r);
	}
	else if (r == 1) {
		printf("%d C %d = %d\n", n, r, n);
	}
	else {
		printf("%d C %d = %d\n", n, r, fac(n) / (fac(r) * fac_2(n, r)));
		return 0;
	}
}

int fac(int num) {
	if (num == 1) {
		return 1;
	}
	else {
		return num * fac(num - 1);
	}
}

int fac_2(int num_2, int num_3) {
	if (num_2 - num_3 == 1) {
		return 1;
	}
	else {
		return (num_2 - num_3) * (num_2 - num_3 - 1);
	}
}

[みけCAT]

fac_2関数の実装がおかしく、再帰になっていません。
こんな変な関数は消して、素直にfac関数を使いましょう。
ついでに、r == 1のときだけでなくr == n - 1のときもn固定でいいのではないでしょうか？

[box]

ヒントを基に考えてみたのですが、またエラーが起きてしまいました。またどこがおかしいのかを指摘していただきたいです。

そういうときは、「何をしたときに」「どんなエラーが出るか」を具体的に書くことです。
コンパイル時にエラーが出るのか、コンパイルは通るけど実行結果がおかしいとか、
現在陥っている状況を詳しく書いてください。
「エラーが起きた」だけでは、何のことやらさっぱり…。

[みけCAT]

決め打ちのケースに当たらず再帰を使う時だけ明示的にreturn 0;するのは、
十分新しいC言語の規格ならどうせmain関数でreturn文を通らなかった場合はreturn 0;相当になるので間違いではないですが、おかしいと思います。

[桜並木]

返信ありがとうございます。書き直しまして正しい結果が表示されるかを試したのですが20C18=1になってしまいます。どこがいけないのでしょうか、また教えていただけたら助かります。

コード:

#include <stdio.h>
int fac(int num);
int main(void)
{
	int n, r;
	puts("nCrの計算をします。");
	printf("nの値を入力してください:");
	scanf("%d", &n);
	printf("rの値を入力してください:");
	scanf("%d", &r);
	if (r == 0 || n == r) {
		printf("%d C %d = 1\n", n, r);
	}
	else if (r == 1 || r == n - 1) {
		printf("%d C %d = %d\n", n, r, n);
	}
	else {
		printf("%d C %d = %d\n", n, r, fac(n) / (fac(r) * fac(n - r)));
		return 0;
	}
}

int fac(int num) {
	if (num == 1) {
		return 1;
	}
	else {
		return num * fac(num - 1);
	}
}

[かずま]

どこがおかしいのかの指摘でなくて申し訳ないのですが、こんな風にも書けます。

コード:

#include <stdio.h>

int comb(int n, int r) { return r <= 0 ? 1 : comb(n-1, r-1) * n / r; }

int main(void)
{
    int n, r;
    while (printf("n r>> "), scanf("%d%d", &n, &r) == 2)
        printf("C(%d, %d) = %d\n", n, r, comb(n, r));
    return 0;
}

[box]

返信ありがとうございます。書き直しまして正しい結果が表示されるかを試したのですが20C18=1になってしまいます。どこがいけないのでしょうか、また教えていただけたら助かります。

たぶん、階乗を計算する際にオーバーフローしているのではないでしょうか。

[かずま]

12! = 479 001 600。
13! = 6 227 020 800。
int は 2147483647 まで。

[桜並木]

返信ありがとうございます。
何度もすみません。オーバーフローを回避するためには、どうすればよいでしょうか？
調べたのですがよくわかりませんでした。intのところをdoubleに変えればよいのでしょうか？
それとも、オーバーフローを回避することはできないのでしょうか？

[みけCAT]

int は 2147483647 まで。

環境依存です。
規格上は少なくとも32767までは格納できます。

返信ありがとうございます。
何度もすみません。オーバーフローを回避するためには、どうすればよいでしょうか？
調べたのですがよくわかりませんでした。intのところをdoubleに変えればよいのでしょうか？

fac関数の戻り値をdouble型にしてprintfで適切なフォーマット指定子を使うと、オーバーフローは起こりにくくなりますが、精度が足りないかもしれません。
オーバーフローを回避するには、多倍長計算ライブラリを作るかダウンロードして使うといいでしょう。

[桜並木]

返信ありがとうございます。
皆さんのおかげで解決することができました。
自分の質問に答えてくれた皆さま本当にありがとうございました。

[かずま]

返信ありがとうございます。
皆さんのおかげで解決することができました。

どのようにして解決したのかを書いてください。

[かずま]

unsigned long long を使って、しかも掛け算をしないで足し算だけの再帰に
してみましたが、n=66 程度が限度のようです。

コード:

#include <stdio.h>

unsigned long long comb(int n, int r)
{
    static unsigned long long t[100][100];
    if (t[n][r] == 0)
        t[n][r] = (r==0 || r==n) ? 1 : comb(n-1, r-1) + comb(n-1, r);
    return t[n][r];
}

int main(void)
{
    int n, r;
    while (printf(">> "), scanf("%d%d", &n, &r) == 2) 
        printf("C(%d, %d) = %llu\n", n, r, comb(n, r));
    return 0;
}

これ以上を望むなら、多倍長計算でしょうね。