二項式係數函數C++不正確的答案n> 13

Question

我想學習C++，因此我試圖做一個函數來計算二項式係數。代碼最多可以運行12個，對於更大的值，生成的結果不正確。我很感激你的意見。

long double binomial(int n, int k) { 
int d = n-k; 
int i = 1, t = 1, n1 = 1, n2 = 1; 
if (d == 0) { 
    return 1; 
} else if (n==0) { 
    return 1; 
} else { 
    while (i <=n) { 
     t *= i; 
     if (i == d) { 
      n1 = t; 
      cout << t; 
     } 
     if (i == k) { 
      n2 = t; 
      cout << t; 
     } 
     i++; 
    } 
} 
return t/n1/n2; 
} 
int main() { 
int n, k; 
cout << "Select an integer n: \n"; 
cin >> n; 
cout << "Select an integer k: \n"; 
cin >> k; 

long double v = binomial(n,k); 
cout << "The binomial coefficient is: " << v << "\n"; 
return 0; 
} 

Answer 1

如果int在您的系統上長32位（現在很常見），那麼13的階乘不適合它（6227020800 > 2147483647）。

要麼轉換成更大的東西（unsigned long long，任何人？），要麼使用bigint庫，要麼提出一個更好/更聰明的算法，不涉及大型因子計算，至少不是直接。

Answer 2

一個int變量只能保持數字達到一定的大小。這從編譯器到編譯器，平臺到平臺都有所不同，但典型的限制將在20億左右。你的程序使用的數字比這個大，所以你會得到錯誤。

如果你想計算大整數的答案是得到一個大整數庫。 GMP是一個受歡迎的。

Answer 3

其中一個建議是使用其他類型。

下面是整數類型，大小和限制的列表。

-------------------------------------------------------------------------------------- 
|type    |size (B)|Limits             | 
-------------------------------------------------------------------------------------- 
|long long   |8  |–9,223,372,036,854,775,808 to 9,223,372,036,854,775,807| 
-------------------------------------------------------------------------------------- 
|unsigned long long |8  |0 to 18,446,744,073,709,551,615      | 
-------------------------------------------------------------------------------------- 
|int    |4  |–2,147,483,648 to 2,147,483,647      | 
-------------------------------------------------------------------------------------- 
|unsigned int  |4  |0 to 4,294,967,295          | 
-------------------------------------------------------------------------------------- 
|short    |2  |–32,768 to 32,767          | 
-------------------------------------------------------------------------------------- 
|unsigned short  |2  |0 to 65,535           | 
-------------------------------------------------------------------------------------- 
|char    |1  |–128 to 127           | 
-------------------------------------------------------------------------------------- 
|unsigned char  |1  |0 to 255            | 
-------------------------------------------------------------------------------------- 

注意long和int通常是相同的尺寸。

注那些限度不是在所有體系相同的非標準保證只有兩件事約可變大小：

1. 1 = sizeof(char) = sizeof(unsigned char)
2. 2 = sizeof(shor) = sizeof(unsigned short) < = sizeof(int) = sizeof(unsigned int) < = sizeof(long) = sizeof(unsigned long) < = sizeof(long long) = sizeof(unsigned long long)

---

另一種選擇是使用bigint庫，但是在這種情況下，計算將需要更多的時間，但將適合。