做組合時除零發生

我正在嘗試計算數學組合。我使用的公式是N!/K! (N-K)!。做組合時除零發生

我能夠從N=10得到正確的答案（10）與N=5，K=2和120，K=3。

但是，當我試圖用更大的數字測試像N=50，K=5.零除錯誤的整數除以彈出。

我試圖用long int來定義finalAns，但它不起作用。有任何想法嗎？

int N; 
int init; 
int K; 
int factN = 1; 
int factK = 1; 
double finalAns; 

cout << "Input of N = "; 
cin >> N; 
cout << "Input of K = "; 
cin >> K; 

int subs = N - K; 
int factsubs = 1; 

for (init = 1; init <= N; init++) 
{ 

    factN = factN * init; 
} 
for (init = 1; init <= K; init++) 
{ 

    factK = factK * init; 
} 
cout << "K is " << factK << endl; 
for (init = 1; init <= subs; init++) 
{ 

    factsubs = factsubs * init; 
} 

finalAns = factN/(factK * factsubs); 
cout << N << "C" << K << " is " << finalAns << endl;

來源

2016-09-21 chloe.t

整數溢出？您是否嘗試過使用例如'long'？或「長久」？或者'unsigned variants'？請學習如何使用調試器，並逐行檢查代碼，以查看發生了什麼，同時監視變量及其值。 –

此外，由於您所做的分割是一個整數除法，因此將其分配給浮點變量無關緊要，您無論如何都不會得到任何小數。 –

在這種情況下'subs'正被設置爲'45'。 'factsubs'是1.當你試圖在一個循環中用'init'乘以最終增加到'45'會導致'factsubs'的整數溢出時，它的值將變爲負數，最終在一些乘法之後它被設置爲' 0'。現在'init * 0 = 0'。你可以使用'long long'作爲'finalAnswer'和'factsubs'來處理它。記住它是否有效，問題會以更高的值重新生成。 – Awais

10！是非常大的：3.628.800 - 如果這個大，就想象50！

根據你使用的是什麼編譯器，你可能處理好的15個！用久了。然而，這還不夠大 - 所以你需要做其他的事情......你可以制定一個乘法算法，返回一個字符數組 - 無法返回一個長整數或類似的東西。

來源

2016-09-21 18:16:43

int（或任何其他類型）的大小不取決於編譯器。這取決於體系結構。 – Rakete1111

您需要更改一次乘法的方法。

不要一次計算N!。
使用任何兩個正整數的除法減少最終結果的事實，所以有利於除法得到較低的中間值。

展開的N!/(N-K)! * K!表達以容納儘可能多的除法運算的在中間步驟能夠減少溢出的機會。

不要單獨計算N!或(N-K)!或K!，您更有可能面對溢出問題。相反使用最終這個事實，你需要劃分大數字，爲什麼不這樣做之前它變成大！

多個提示：

N!/(N-K)! = multiply i[N..N-K+1] one by one //not i[N..1]

和，檢查是否有價j from [2..K]任何因子（f）完全將所述中間產物的值（p），如果是，執行除法：p = p/f和j = j/f。

來源

2016-09-21 18:29:20

做組合時除零發生

回答

相關問題