C++のニュートン二項係数に関する問題

Question

ニュートンの二項係数について私のプログラムに問題があります。最初は負の数を表示しましたが、階乗関数タイプをunsigned long longに変更すると、負の数を印刷する問題が解決されたようです。このプログラムは最大でn = 20で動作し、それより上にゼロ、1および2を印字します。それを修正する方法は考えていないし、うまくいけば誰かが私に手を差し伸べることができる。

Answer 1

階乗は一般的に非常に大きいので、ここで整数オーバーフローが発生します。この問題を修正するには、たとえば、階乗を使用していないC(n, k)計算の他のアルゴリズムを実装することができます：ここでは、以下の再発規則が使用されている

unsigned long long C(unsigned n, unsigned k) { 
    if (n == k || k == 0) { 
     return 1; // There's exactly one way to select n or 0 objects out of n 
    } 
    return C(n - 1, k - 1) * n/k; 
} 

：C(n, k) = C(n - 1, k - 1) * n/kを。 C(n, k) = n!/(k! (n-k)!) = (n/k) * (n-1)!/((k-1)!(n-1-k+1)!)から証明するのはとても簡単です。