c++ - 二项式系数

Question

我有一个计算二项式系数的代码，但是当数字大于 20 时，它开始计算错误，问题出在哪里？谢谢

#include <iostream>
using namespace std;

long int bin(long int x)
{
    if(x==0)
        return 1;
    long int r = x;
    for(int i = r-1;i>0;i--)
    {
        r = r*i;
    }
    return r;
}
int main()
{
    cout << "Write n and k: " << endl;
    long int n=0;
    long int k=0;
    cin >> n;
    cin >> k;
    long int result = 0;
    long int fn = bin(n);
    long int fk = bin(k);
    long int fnk = bin(n-k);


    result = fn/(fk*fnk);

    cout << endl << "C = " << result << endl;


    return 0;
}

例如 12 和 5 = 792 这是正确的，但 20 和 4 = -2 这是不正确的

Answer 1

您的bin函数计算阶乘。21 的阶乘不适合long.

您已经依赖于实现细节。long只需要 32 位，但在您的系统上是 64 位。如果它只有 32 位，那么您会很快失败。

Answer 2

20！= 2432902008176640000，这远远超出了long int可以容纳的范围（通常为 2147483647）。改为使用double。

Answer 3

您正在使用计算 n 的阶乘

bin(n);

当 n >=20 时，您将超过 long 的限制。

正如@SteveJessop 在评论中指出的那样，即使您使用unsigned long long（最长的定点类型），其范围从0 to 18446744073709551615

您可以使用 int-array 来存储您的结果，详见此处。