ID非公開

2022/6/28 22:23

55回答

nC(n/2)を求めるプログラムを組みたいのですが、(n/2はint型の計算ですので、切り捨てが発生します)

C言語関連120閲覧xmlns="http://www.w3.org/2000/svg">250

ベストアンサー

0

ThanksImg質問者からのお礼コメント

一番構文的にスマートでした! 他の方々のプログラムも試して見たら合ってました。 ありがとうございます!

お礼日時:7/5 9:06

その他の回答(4件)

0

質問の最後で述べられた通り、分母と分子がある素数で同時に 割れる限り割っていけばいいです。(n-[n/2])項ある分母すべて が1になるまで素数を変えながらそれを行います。 そして分子も同様の方法で素因数分解します。 素因数分解の形で出力すれば、例えint型の表現可能最大値を 超えたとしても、正確になります。 具体的な10進表現を求める場合でも、素因子がこの問題の 場合小さいので、多倍長整数計算ライブラリを使うまでも なく、簡単に求められることでしょう。 対数計算で、桁数も見積もることができます。 ちなみに C(200,100)=2^3×3×5×11×13^2×17×37×53×59×61×101×103 ×107×109×113×127×131×137×139×149×151×157×163×167 ×173×179×181×191×193×197×199 C(201,100)=2^3×3^2×5×11×13^2×17×37×53×59×61×67×103 ×107×109×113×127×131×137×139×149×151×157×163×167 ×173×179×181×191×193×197×199 と手持ち環境のC言語プログラムは出力しましたが、あっているか どうかは保証できません。電卓の対数検算ではもっともらしい数字 になりました。 なおパスカルの三角形の公式と再帰呼び出しを利用して求める方法は nが大きくなると工夫しないと急激に計算時間がかかります。

コードを追加して素因数分解から10進法表示に直す機能を追加・実行 したところ C(200,100)=90548514656103281165404177077484163874504589675413336841320 C(201,100=180200509365116430834121184084894227116588341829287927773320 となりました。 Windows 電卓での計算でははそれぞれ 9.0548514656103281165404177077484e+58 1.8020050936511643083412118408489e+59 となりました。この範囲ではあっているようです。

0

nCr = n!/(n-r)!/r!  階乗計算をまともにやると、オーバーフローの危険性が増すので、掛け算と割り算で実現する。 double Combination(int iN, int iR) {     if (iN < 0 || iR < 0 || iN < iR) { return -1; }     // error     if (iR > iN - iR) { iR = iN - iR; }     double dResult = 1;     for (int iBig = iN - iR + 1, iSmall = iR; iSmall > 0; iBig++, iSmall--) {         dResult *= double(iBig) / iSmall;     }     return dResult; }

0

/* nCr = ( n*(n-1)*(n-2)*...*(n-r+2)*(n-r+1) ) / r! 素因数をカウントする配列を用意し、分子の各項を素因数分解して素因数をカウントし、そのあと分母の各項も素因数分解して今度は配列からカウントした分減らしていく。最後にカウントした分の各素因数を掛ける。という方針のものです。*/ #include <stdio.h> #include <limits.h> #define MAX 50 void add_factor(int *factor, int k){ while(k > 1){ for(int i = 2; i <= k; i++){ if(k % i == 0){ factor[i]++; k /= i; break; } } } } void sub_factor(int *factor, int k){ while(k > 1){ for(int i = 2; i <= k; i++){ if(k % i == 0){ factor[i]--; k /= i; break; } } } } int combi(int n, int r){ if(n < r || n < 0 || r < 0){ return -1; //error } int factor[MAX] = {}; for(int i = 0, j = n; i < r; i++, j--){ add_factor(factor, j); } for(int i = r; i > 1; i--){ sub_factor(factor, i); } int k = 1; for(int i = 2; i < MAX; i++){ for(int j = 0; j < factor[i]; j++){ if(k > INT_MAX / i){ return -1; //over flow } k *= i; } } return k; } int main(void){ int i = 0; while(1){ int n = i, r = i/2, m = combi(n,r); printf("%dC%d",n,r); if(m == -1){ puts(" Error"); break; } printf(" = %d\n",m); i++; } return 0; } /* 実行結果例: 0C0 = 1 1C0 = 1 2C1 = 2 3C1 = 3 ... 30C15 = 155117520 31C15 = 300540195 32C16 = 601080390 33C16 = 1166803110 34C17 Error */

0

まず、「掛ける」と「割る」をやれば、必ず割り切れます。 ただ、掛ける前に割ろうとしても、それは必ずしもうまくいきません。 1項ずつの計算を、掛けてから割ったら、最大値まで求められるという仕様にできないから、素因数分解的に値を小さくしてから計算するしかありません。