優化計算組合並避免溢出

我正在解決一個編程問題，它在計算nCr時遇到困難，同時避免溢出。我已經做了如下簡單的簡化，但只是好奇於是否還有更復雜的簡化。優化計算組合並避免溢出

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

相信沒有人可以更簡化，可以考慮K個不同的情況下爲偶數或奇數，只是建議的方式。

任何意見表示讚賞。

2012-08-26 Aman Deep Gautam

作爲替代/補充答案，GMP庫可用於表示任意大的整數。 http://gmplib.org/ –

我發現了一個有趣的解決方案在這裏：http://blog.plover.com/math/choose.html

unsigned choose(unsigned n, unsigned k) { 
     unsigned r = 1; 
     unsigned d; 
     if (k > n) return 0; 
     for (d=1; d <= k; d++) { 
     r *= n--; 
     r /= d; 
     } 
     return r; 
    }

這避免溢出（或至少限制的問題）通過交替地執行乘法和除法。

E.g.爲n = 8，k = 4：

result = 1; 
result *= 8; 
result /= 1; 
result *= 7; 
result /= 2; 
result *= 6; 
result /= 3; 
result *= 5; 
result /= 4; 
done

來源

2012-08-26 12:52:50

我在發佈之前瞭解它的方法和想法，但不能證明當你在某些迭代中用某個數字表示'x'時，那麼爲什麼在那個時候分子必須是「x」的倍數。如果它不是多個，那麼我們不會得到正確的答案。 –

@AmanDeepGautam：在循環的每次迭代中的除法語句之後，r的值爲nCd，n的原始值和d的當前值。因此，當n從10開始時，第一次迭代將r設置爲10（* 10/1）。第二次迭代將r設置爲45（* 9/2）。第三次迭代將r設置爲120（* 8/3）。這些值是10C1,10C2和10C3。我們知道nCd總是一個整數。因此，數學劃分必須總是產生一個整數，因此，在劃分之前，r必須是r的倍數。 –

我必須解決這個問題了。我所做的是使用這樣一個事實，即有相同數量的乘法作爲分割並將它們捆綁在一起，每次只能乘以一個乘法和一個除法。它在最後以整數形式出現，但我使用中間項的雙精度值，然後在最後四捨五入到最接近的整數。

// Return the number of combinations of 'n choose k' 
unsigned int binomial(unsigned int n, unsigned int k) { 
unsigned int higher_idx; 
unsigned int lower_idx; 
if(k > n-k) { 
    higher_idx = k; 
    lower_idx = n - k; 
} else { 
    higher_idx = n - k; 
    lower_idx = k; 
} 
double product = 1.0; 
double factor; 
unsigned int idx; 
for(idx=n; idx>higher_idx; idx--) { 
    factor = (double)idx/double(lower_idx - (n - idx)); 
    product *= factor; 
} 
return (unsigned int)(product + 0.5); 
}

來源

2014-12-21 18:51:01 user1389840

優化計算組合並避免溢出

回答

相關問題