二项式系数 [英] binomial coefficient

问题描述

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

I have a code which calculate binomial coefficient, but when number is bigger then 20, it start to calculate wrong, where is the problem? Thanks

#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不正确

for example 12 and 5 = 792 which is correct, but 20 and 4 = -2 which is not correct

推荐答案

您正在使用

bin(n);

当n> = 20时，您的运行时间超过了上限。

You are running past the limit of long when n is >=20.

正如@SteveJessop在注释中指出的，即使您使用 unsigned long long （最长的定点类型），也会超出限制， b $ b从 0到18446744073709551615

As @SteveJessop pointed out in the comments, You would overrun the limit even if you used unsigned long long (the longest fixed-point type) which has a range from 0 to 18446744073709551615

您可以使用int数组将结果存储为详细 这里 。

You could use an int-array to store your result as detailed here.

这篇关于二项式系数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！