🖇️ 👈 👨🏾‍✈️ 二項係数の計算...それでもソフトウェア 👶🏿 🎵 🧒🏻

以前、3つの記事で、二項係数の計算のトピックが取り上げられました。

Cでの二項係数の計算（C ++）

フーリエ変換を使用した二項係数の計算

二項係数の計算...手動で

前回の記事で、著者は二項係数を計算するための純粋に数学的な最適化を示しました。計算にコンピューターは特に必要ないことが判明しました。十分な紙、ペン、電卓~~、ビール~~ 。ただし、上記の項目のいずれかが手元になく、アイドル状態のコンピューターが届く場合は、コンピューターで同じことを実行できます。

アルゴリズム

記事へのコメントの中で、著者は形式化されたアルゴリズムがないと非難されました。考えた後、次のように描かれました。

階乗式を次の形式に縮小した後、二項係数を計算する場合：

C（n、k）= P（n、k + 1）/ P（1、nk）

削減する必要がある割合を取得します。整数の小数部を減らす最も簡単な方法は何ですか？分子と分母を因数分解します。問題は、この場合、分子と分母の両方が小さな数の積であるという事実によって促進されます。つまり各因子は素因数に個別に分解され、対応する指数を持つ素数のリストの形式で結果を蓄積します。

次に、分母について取得したリストを調べ、各数値を取得し、分子内のこの数値の指数から分母内のこの数値の指数を引きます。二項係数が整数であるという事実に基づいて、分母は完全に縮小する必要があります。つまり、1に等しくなります。

最後のステップ：前のステップで分子について取得したリストを調べて、この数値に対応する累乗されたすべての数値を乗算します。

実装

「プライム番号-指数」のペアをマップコンテナに格納することが決定されました。プライムはキーで、指数は値です。

最も原始的なアルゴリズムは、数値を因数分解するために採用されました。さらなる使用を最適化するために、外部コンテナーは参照により因子分解関数に渡されます。

#include <iostream> #include <map> using namespace std; typedef unsigned long long ullong; //      . //       //    map,      : //  -  ,  -     . template <typename integral_type> void factorize(integral_type num, map<integral_type, unsigned int>& res) { integral_type j = 2; while (num / integral_type(2) >= j) { if (num % j == 0) { res[j]++; num /= j; j = integral_type(2); } else { ++j; } } res[num]++; } typedef map<ullong, unsigned int> factmap; //    . ullong C(int n, int k) { ullong result = 1uLL; //        // C(n, k) = (n, k+1) / (1, nk) int lim_numer_min = k + 1; //       int lim_numer_max = n; //       int lim_denom_min = 2; //       int lim_denom_max = n - k; //       //          factmap numerator, denominator; //        for (int i = lim_numer_min; i <= lim_numer_max; ++i) { factorize(ullong(i), numerator); } //        for (int i = lim_denom_min; i <= lim_denom_max; ++i) { factorize(ullong(i), denominator); } //      for (auto i = denominator.begin(); i != denominator.end(); i++) { numerator[i->first] -= i->second; } //      //     for (auto i = numerator.begin(); i != numerator.end(); i++) { //        for (ullong p = 0; p < i->second; ++p) { result *= i->first; } } return result; }

テスト中

親プログラムは、最初の記事のプログラムのように作成されました。

 int main() { int n; for (n = 34; n < 68; ++n) { cout << "C(" << n << ", " << n/2 << ") = " << C(n, n/2) << endl; } return 0; }

実行結果：

C（34、17）= 2333606220

C（35、17）= 4537567650

C（36、18）= 9075135300

C（37、18）= 17672631900

C（38、19）= 35345263800

C（39、19）= 68923264410

C（40、20）= 137846528820

C（41、20）= 269128937220

C（42、21）= 538257874440

C（43、21）= 1052049481860

C（44、22）= 2104098963720

C（45、22）= 4116715363800

C（46、23）= 8233430727600

C（47、23）= 16123801841550

C（48、24）= 32247603683100

C（49、24）= 63205303218876

C（50、25）= 126410606437752

C（51、25）= 247959266474052

C（52、26）= 495918532948104

C（53、26）= 973469712824056

C（54、27）= 1946939425648112

C（55、27）= 3824345300380220

C（56、28）= 7648690600760440

C（57、28）= 15033633249770520

C（58、29）= 30067266499541040

C（59、29）= 59132290782430712

C（60、30）= 118264581564861424

C（61、30）= 232714176627630544

C（62、31）= 465428353255261088

C（63、31）= 916312070471295267

C（64、32）= 1832624140942590534

C（65、32）= 3609714217008132870

C（66、33）= 7219428434016265740

C（67、33）= 14226520737620288370

プロセスが0（0x0）の実行時間を返しました：0.051秒

二項係数の計算...それでもソフトウェア

アルゴリズム

実装

テスト中

More articles: