C言語についてです。 再帰を使わないでnCrの組み合わせを求める関数を作りたいのですが、ここから全く

C言語についてです。


再帰を使わないでnCrの組み合わせを求める関数を作りたいのですが、ここから全く進めません。どなたか教えてください。

ちなみにcombiというのはbunnsi/bunnboを表したかったのですが行き詰まりました、、、、
あと、下のint main(void)からはたぶんできるのでそれ以前を教えていただければ十分です！！！

No.1 ベストアンサー 回答者： cametan_42 回答日時： 2020/12/14 11:51

int factorial(int n) {

　int i, fact;
　for (i = 0; i <= n; i++) {
　　if (i == 0) {
　　　fact = 1;
　　} else {
　　　fact *= i;
　　}
　}
　return fact;
}

int combination(int n, int r) {
　if (r <= 0) {
　　return 1;
　} else {
　　return factorial(n) / (factorial(r) * factorial(n - r));
　}
}

この回答へのお礼

投稿者です。
作成完了したんですけど、20C10みたいな大きい数字だと計算できないのですが、その理由を教えていただきたいです！！

お礼日時：2020/12/15 15:00

No.11 回答者： Tacosan 回答日時： 2020/12/15 18:41

C の場合

・int は -(2^15-1)～(2^15-1)
・long は -(2^31-1)～(2^31-1)
・ついでに long long は -(2^63-1)～(2^63-1)
が規格上の最小範囲＞#10. だから, 「一番狭い」処理系を考えると 8! ですでに範囲を超えてしまう... というか, この場合の「ロジックと全く関係ないトコで計算テクニックが必要」は「多倍長演算を自動でやってくれない」すべての言語の「問題」で, ことさら C だけあげつらう理由もないんではないかと. 強いていえばカテゴリーくらい?

ちなみにいうと #7 の指摘はいい線をついていて, たとえば
・順序を逆にして割り算を先にする
・めんどくさいので 1つの文にする
なんてやると指摘されている通りの現象が発生します. 約分してから処理するなら, 2つの文に分ければ順序はどっちでもいいんだけど (ただし 1つの文にしちゃうと相変わらず問題が発生する).

あと修正感謝＞#9.

No.10 回答者： cametan_42 回答日時： 2020/12/15 16:34

> 20C10みたいな大きい数字だと計算できないのですが、その理由を教えていただきたいです！！

1つは、factorialがかなり速く大きくなるから、ですよね。
一応ロジック自体は書いた通りなんですが、C言語の厄介なトコは、「ロジックと全く関係ないトコで計算テクニックが必要」な辺りです。初学者に向かない理由がその辺なんですよねぇ。

例えば、

1*2*3*4*5*6*7*8*9*10

とたった10個の数だけ、で計算結果が3628800、と7桁、にも達します。11をこれに掛けるだけで8桁突破するのも分かりますよね?10の位を超えた数を今後かけていくと、最低でも桁がひとつづつ増えていって、コンピュータ(っつーかC言語)じゃなかなか扱いづらい桁数へと突入していきます。

実際は、C言語の仕様上、intがどこまで扱えるのか、ってのは実装依存になってたと思います。1つの解決策としてはintを使わずに、もっと桁数が大きく扱えるlongを使う事。また、正の整数しか扱わない、と言う前提で、符号なしの整数にしてしまう、と言う手があります(unsigned long)。
あと、combinationの計算としては

factorial(n) / (factorial(r) * factorial(n - r))

が公式通り、なんですが、この計算をする際、結果の数は小さいにせよ、factorial(n)やfactorial(r) * factorial(n-r)がデカくなる可能性があるんですよね。
良くあるこれらの肥大化の避け方、と言うのに、対数に変換して計算する、ってテクニックがあります。
つまり、

combination(n, r) = factorial(n) / (factorial(r) * factorial(n - r))

なので、両辺対数を取れば

ln|combination(n, r)| = ln|factorial(n) / (factorial(r) * factorial(n - r))|
= ln|factorial(n)|-ln|factorial(r) * factorial(n - r)|
= ln|factorial(n)|-(ln|factorial(r)|+ln|factorial(n - r)|)
= ln|factorial(n)|-ln|factorial(r)|-ln|factorial(n - r)|

になるので、これを利用利用してプログラミングします。そして、結果を返す前に指数関数で元に戻して計算結果の数の肥大化を防ぐ、ってのが割にありきたりなテクニックにはなりますね。

No.9 回答者： iruiru298 回答日時： 2020/12/15 16:03

No2です

No.6の方法でプログラミングしてみました

int combination(int a, intb )
{
　int i,s;

　s=1;
　for(i=0; i<b; i++) {
　　s *= (a-i);
　　s /= (i+1);
　}
　return s;
}

No.8 回答者： usa3usa 回答日時： 2020/12/15 15:48

No7です

>でも計算途中で割り切れずに分数表現が必要になってしまいそうな気がしますが大丈夫でしょうか？

No６さんの計算方法では、
nCi (i=1,2,...)を計算し続けるので、必ず割り切れ整数になる
ので大丈夫ですね。
失礼しました。

No.7 回答者： usa3usa 回答日時： 2020/12/15 12:54

＞1 からはじめて

＞(n-i) を掛けて i で割る
＞って書けばオーバーフローしにくくなる. しないわけじゃないけど.
確かに！　
でも計算途中で割り切れずに分数表現が必要になってしまいそうな気がしますが大丈夫でしょうか？

分子と分母の数列を記憶する配列を用意し、
分子にｎ！の計算に必要な数値１，２，・・、ｎ　を書き込み,
分母に(n-r)! / r!、 の計算に必要な数値１，２，・・、（ｎ-r),1,2,..,rを書き込み
分子分母で約分できる部分を見つけ約分し、
（この段階で分母は全て１に約分出来ているはずなので）、
分子をかけ合わせて答えにする
のが正解かしら

No.6 回答者： Tacosan 回答日時： 2020/12/14 19:27

1 からはじめて

(n-i) を掛けて i で割る
って書けばオーバーフローしにくくなる. しないわけじゃないけど.

もっと頑張って
(n-i)/i を約分して分母で割ってから分子を掛ける
ようにすれば, さらにオーバーフローしにくくなる... ここまでやればオーバーフローしないようになってるかなぁ.

No.5 回答者： metabolian 回答日時： 2020/12/14 17:17

今気がついたのですが、

bunnsi の初期値がa-b+1なのに、
bunnsiのforループが i= a-b+1から
始まってます？
a-b+1を2回かけたりしてないですか？

No.4 回答者： Ogre7077 回答日時： 2020/12/14 14:25

nCr = n! / (n-r)! / r!

combination(a,b)
= a! / (a-b)! / b!
= {1 から a までの総積}/{1 から a-b までの総積}/{1 から b までの総積}
= {(a-b)+1 から a までの総積} / {1 から b までの総積}
= 1 * (a-b+1) * (a-b+2) * ... * a / 1 / 2 / ... / b

c = 1;
for (i = a-b+1; i <= a; i++) c *= i;
for (i = 1; i <= b; i++) c /= i;

No.3 回答者： metabolian 回答日時： 2020/12/14 14:15

return combi; の手前に

combi = bunnsi / bunnbo;
を入れればいいだけだと思います。
（int 同士の除算は「小数点以下切り捨て」
になる。）