再帰の問題

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
桜並木

再帰の問題

#1

投稿記事 by 桜並木 » 9年前

学校で出された課題をやっており、うまく結果が表示できないので質問します。課題の内容は、再起を使い組み合わせの結果を表示させるという課題です。現在数字を入力すると、間違った答えが出てしまいます。なので間違っているところを指摘してくれると助かります。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);
	}
}

超初級者
記事: 56
登録日時: 10年前

Re: 再帰の問題

#2

投稿記事 by 超初級者 » 9年前

もう1個の方を見てください。
最後に編集したユーザー 超初級者 on 2016年7月03日(日) 22:20 [ 編集 1 回目 ]

超初級者
記事: 56
登録日時: 10年前

Re: 再帰の問題

#3

投稿記事 by 超初級者 » 9年前

こんな感じでしょうか。

コード:

#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
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: 再帰の問題

#4

投稿記事 by みけCAT » 9年前

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

ヒント:nCr = n! / (r! * (n-r)!) (Wikipediaより)
オーバーフローしない程度の入力を与えるといいでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

桜並木

Re: 再帰の問題

#5

投稿記事 by 桜並木 » 9年前

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

コード:

#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
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: 再帰の問題

#6

投稿記事 by みけCAT » 9年前

fac_2関数の実装がおかしく、再帰になっていません。
こんな変な関数は消して、素直にfac関数を使いましょう。
ついでに、r == 1のときだけでなくr == n - 1のときもn固定でいいのではないでしょうか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

box
記事: 2002
登録日時: 14年前

Re: 再帰の問題

#7

投稿記事 by box » 9年前

桜並木 さんが書きました:ヒントを基に考えてみたのですが、またエラーが起きてしまいました。またどこがおかしいのかを指摘していただきたいです。
そういうときは、「何をしたときに」「どんなエラーが出るか」を具体的に書くことです。
コンパイル時にエラーが出るのか、コンパイルは通るけど実行結果がおかしいとか、
現在陥っている状況を詳しく書いてください。
「エラーが起きた」だけでは、何のことやらさっぱり…。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: 再帰の問題

#8

投稿記事 by みけCAT » 9年前

決め打ちのケースに当たらず再帰を使う時だけ明示的にreturn 0;するのは、
十分新しいC言語の規格ならどうせmain関数でreturn文を通らなかった場合はreturn 0;相当になるので間違いではないですが、おかしいと思います。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

桜並木

Re: 再帰の問題

#9

投稿記事 by 桜並木 » 9年前

返信ありがとうございます。書き直しまして正しい結果が表示されるかを試したのですが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);
	}
}

かずま

Re: 再帰の問題

#10

投稿記事 by かずま » 9年前

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

コード:

#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
記事: 2002
登録日時: 14年前

Re: 再帰の問題

#11

投稿記事 by box » 9年前

桜並木 さんが書きました:返信ありがとうございます。書き直しまして正しい結果が表示されるかを試したのですが20C18=1になってしまいます。どこがいけないのでしょうか、また教えていただけたら助かります。
たぶん、階乗を計算する際にオーバーフローしているのではないでしょうか。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

かずま

Re: 再帰の問題

#12

投稿記事 by かずま » 9年前

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

桜並木

Re: 再帰の問題

#13

投稿記事 by 桜並木 » 9年前

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

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: 再帰の問題

#14

投稿記事 by みけCAT » 9年前

かずま さんが書きました:int は 2147483647 まで。
環境依存です。
規格上は少なくとも32767までは格納できます。
桜並木 さんが書きました:返信ありがとうございます。
何度もすみません。オーバーフローを回避するためには、どうすればよいでしょうか?
調べたのですがよくわかりませんでした。intのところをdoubleに変えればよいのでしょうか?
fac関数の戻り値をdouble型にしてprintfで適切なフォーマット指定子を使うと、オーバーフローは起こりにくくなりますが、精度が足りないかもしれません。
オーバーフローを回避するには、多倍長計算ライブラリを作るかダウンロードして使うといいでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

桜並木

Re: 再帰の問題

#15

投稿記事 by 桜並木 » 9年前

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

かずま

Re: 再帰の問題

#16

投稿記事 by かずま » 9年前

桜並木 さんが書きました:返信ありがとうございます。
皆さんのおかげで解決することができました。
どのようにして解決したのかを書いてください。

かずま

Re: 再帰の問題

#17

投稿記事 by かずま » 9年前

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;
}

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

閉鎖

“C言語何でも質問掲示板” へ戻る