計算ncr的說明

Question

我在閱讀可能有效的方法來計算 ncr當我遇到此帖時。

Which is better way to calculate nCr

這裏給出的第二個答案，一個我不能夠理解。代碼是：

long long combi(int n,int k) 
{ 
    long long ans=1; 
    k=k>n-k?n-k:k; 
    int j=1; 
    for(;j<=k;j++,n--) 
    { 
     if(n%j==0) 
     { 
      ans*=n/j; 
     }else 
     if(ans%j==0) 
     { 
      ans=ans/j*n; 
     }else 
     { 
      ans=(ans*n)/j; 
     } 
    } 
    return ans; 
} 

這將會是什麼複雜性？我試着用一個例子來做，答案是正確的，但是這些條件是什麼？

Answer 1

即最佳化而造成的，它計算

n!/k! (n-k)! = n * (n-1) * ... (n - k + 1)/k * (k-1) * ... * 1 

第一：算法優化：作爲C N K = C N（N-K）：計算具有較少方面所述一個 - 好的。

下計算的優化：計算ans * n/j嘗試做操作之前要簡化分數時 - 恕我直言，這一個是高度discutable，因爲它是一個人會做（你的路，我計算比12345678/9)但是對於處理器快6/3，這個優化只是增加了多餘的操作。

Answer 2

作爲鏈接中的狀態，循環中的多重條件是在執行ans = (ans * n)/j時處理溢出。

因此函數是：

long long ans = 1; 
k = std::min(k, n-k); 
int j = 1; 
for (; j <= k; j++, n--) { 
    ans = (ans * n)/j; 
} 
return ans; 

我們有C（N，R）= N！ /（n-r）！ [R！和大多數因素可以簡化。

而複雜度是k。