No.1ベストアンサー
- 回答日時:
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みたいな大きい数字だと計算できないのですが、その理由を教えていただきたいです!!
No.2
- 回答日時:
回答でなくコメントです。
int が無限の桁数があるならNo1の回答で良いと思いますが、有限の桁数なので、
有効桁数内で計算できるアルゴリズムを検討する必要がありそうですね
No.3
- 回答日時:
return combi; の手前に
combi = bunnsi / bunnbo;
を入れればいいだけだと思います。
(int 同士の除算は「小数点以下切り捨て」
になる。)
No.4
- 回答日時:
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.5
- 回答日時:
今気がついたのですが、
bunnsi の初期値がa-b+1なのに、
bunnsiのforループが i= a-b+1から
始まってます?
a-b+1を2回かけたりしてないですか?
No.6
- 回答日時:
1 からはじめて
(n-i) を掛けて i で割る
って書けばオーバーフローしにくくなる. しないわけじゃないけど.
もっと頑張って
(n-i)/i を約分して分母で割ってから分子を掛ける
ようにすれば, さらにオーバーフローしにくくなる... ここまでやればオーバーフローしないようになってるかなぁ.
No.7
- 回答日時:
>1 からはじめて
>(n-i) を掛けて i で割る
>って書けばオーバーフローしにくくなる. しないわけじゃないけど.
確かに!
でも計算途中で割り切れずに分数表現が必要になってしまいそうな気がしますが大丈夫でしょうか?
分子と分母の数列を記憶する配列を用意し、
分子にn!の計算に必要な数値1,2,・・、n を書き込み,
分母に(n-r)! / r!、 の計算に必要な数値1,2,・・、(n-r),1,2,..,rを書き込み
分子分母で約分できる部分を見つけ約分し、
(この段階で分母は全て1に約分出来ているはずなので)、
分子をかけ合わせて答えにする
のが正解かしら
No.8
- 回答日時:
No7です
>でも計算途中で割り切れずに分数表現が必要になってしまいそうな気がしますが大丈夫でしょうか?
No6さんの計算方法では、
nCi (i=1,2,...)を計算し続けるので、必ず割り切れ整数になる
ので大丈夫ですね。
失礼しました。
No.9
- 回答日時:
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.10
- 回答日時:
> 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)|
になるので、これを利用利用してプログラミングします。そして、結果を返す前に指数関数で元に戻して計算結果の数の肥大化を防ぐ、ってのが割にありきたりなテクニックにはなりますね。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C言語 3 2022/10/04 15:07
- C言語・C++・C# プログラム内から、MIDIファイルの一部分だけを再生する方法 1 2023/02/15 11:08
- C言語・C++・C# 至急教えてください。プログラミングの問題です。 malloc関数を使ってください!お願いします! 最 1 2022/07/21 09:28
- C言語・C++・C# 至急教えてください。プログラミングの問題です。 最初に正の整数nの入力を受け付け、次に分数の分子と分 1 2022/07/19 17:03
- C言語・C++・C# c言語の問題です 課題1 (二分探索木とセット) 大きさ size の配列 array を考える。す 2 2023/01/10 21:08
- C言語・C++・C# 至急教えてください!プログラミングの問題です。 割られる整数と割る整数を受け取って、商と余りを出力す 3 2022/07/05 10:23
- C言語・C++・C# const char** p;のとき、free(p)でC4090エラーとなるのはなぜですか 3 2023/03/31 16:28
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- C言語・C++・C# 至急お願いします。プログラミングの問題です。 最初に正の整数nの入力を受け付け、次に分数の分子と分母 3 2022/07/19 17:09
- Java javaでのプログラム(配列)について質問です. 2 2022/10/14 22:27
このQ&Aを見た人はこんなQ&Aも見ています
-
外出時に「待たせる妻」vs イライラする「待つ夫」は日本だけ?見習いたい海外事情
夫の家事参加に積極的なイメージのある海外でも、同様の事例はあるのか。結婚カウンセラーの佐竹悦子さんに伺ってみた。
-
異なるn個の整数からr個の整数を取り出す組み合わせ
C言語・C++・C#
-
困ってます…nCrを求めるC言語プログラミング
C言語・C++・C#
-
組み合わせ順列
C言語・C++・C#
-
-
4
n個の要素で出来る順列組み合わせを全て出力するアルゴリズム
C言語・C++・C#
-
5
nCrの計算
C言語・C++・C#
-
6
C言語 exitの使い方
C言語・C++・C#
-
7
順列の内容をすべて表示するプログラムについて
C言語・C++・C#
-
8
C言語の入力した文字を反転させるプログラミングの仕方が分かりません。
Ruby
-
9
重複しない組み合わせのプログラム
その他(パソコン・スマホ・電化製品)
-
10
”/”を使わずに割り算したいんですが…
C言語・C++・C#
-
11
組み合わせと順列 アルゴリズム
C言語・C++・C#
-
12
エクセルでnCr (組み合わせ)の作成方法
Excel(エクセル)
-
13
c言語の質問です。 ある月のカレンダーを作る際に、その月の日数とその月の1日の曜日を入力すればできる
C言語・C++・C#
関連するカテゴリからQ&Aを探す
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
Vb6.0で三角関数が使えない
-
変化させるセルが変化しない
-
やってみてもわからないので教...
-
C# 計算処理中に実行中ウィン...
-
MATLABの積分について
-
C言語で、漸化式を使ってパスカ...
-
スライムがつぶれていく様子を...
-
絶対ち
-
VBAの再計算が反映されない件に...
-
JavaScriptでSQLiteの値を使いたい
-
Excel VBAの残業時間の合計計算...
-
VBでReplace
-
Java 電卓の連続計算
-
あのコンピュータアーキテクチ...
-
60進数の四則計算
-
バッチファイルでウインドウを...
-
スパイダソリティアの問題
-
MathematicaのNDSolveで連立常...
-
65536は2の何乗なのでしょうか?
-
素数を自動的に作る
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
VBAの再計算が反映されない件に...
-
排他的論理和 BCC(水平パリテ...
-
EXCELなどで「返す」という表現
-
C言語の課題で、1年の秒数を計...
-
バッチファイルでウインドウを...
-
骨折リスク評価のFRAXについて...
-
変化させるセルが変化しない
-
CとFORTRANの計算速度はどちら...
-
なぜオーバーフローになるので...
-
数値計算の高速化 (cos, sin, exp)
-
モジュラス103の計算とは何でし...
-
C# 計算処理中に実行中ウィン...
-
モジュロ
-
引き放し法による除算アルゴリ...
-
60進数の四則計算
-
C言語についてです。 再帰を使...
-
Perlで時間の計算
-
CRC8を教えてください
-
傾いた四角形内の範囲の条件式
おすすめ情報