3

我写了一个程序，它应该打印牛顿二项式的值。number - 测试数, t[i][0] - n, t[i][1] - k. 对于小数字 n 和 k 似乎没问题，但是当我想输入更大的数字时，它会打印0或1小的负整数。基本上我使用了 long int 而不是 int 所以它应该适用于更大的数字。你能解释一下为什么会这样吗？

#include <iostream>
long fact(int x);
using namespace std;
int main()
{
    int number;
    cin>>number;
    int t[number][2];

    for(int i=0; i<number; i++)
    {
        cin>>t[i][0];
        cin>>t[i][1];
        if (t[i][0]<t[i][1]) return 0;
    }

    for(int i=0; i<number; i++)
    {
        cout<<fact(t[i][0])/(fact(t[i][0]-t[i][1])*fact(t[i][1]))<<endl;
    }
    return 0;
}
long fact(int x)
{
    long factt=1;
    for(int i=1; i<=x; i++)
    {
        factt=factt*i;
    }
    return factt;
}

@编辑

谢谢你的建议。我尝试实现这一点，但它不能很好地计算二项式。它为 n=4 和 k=2 打印 11。你可以看看这个吗？

#include <iostream>

long fact(int n, int k);
using namespace std;
int main()
{
    int number;
    cin>>number;
    int t[number][2];

    for(int i=0; i<number; i++)
    {
        cin>>t[i][0];
        cin>>t[i][1];
        if (t[i][0]<t[i][1]) return 0;
    }
    for(int i=0; i<number; i++)
    {
        cout<<fact(t[i][0],t[i][1])<<endl;
    }
    return 0;
}

long fact(int n, int k)
{
    if(n==0 || n==k)
        return 1;
    else if(n>k)
        return fact(n-1,k-1)+fact(n-1, k);
    else
        return 0;
}
4

2 回答 2

2

阶乘增长非常快，甚至无符号 64 位整数溢出n!。n>20实现二项式系数的无溢出方法是使用以下递归定义：

binom(n, k) = binom(n-1, k-1) + binom(n-1, k)

这可确保仅当binom(n,k)太大而无法容纳整数类型的大小时才会溢出。

于 2014-12-29T23:46:32.343 回答
0

在 Linux 上，32 位 long 与 int 相同，适合 32 位。在 Linux 上，64 位长是 64 位长。在 Windows 上，32 位和 64 位长都是 32 位实体

您必须使用long longto 来保证使用 64 位，尽管它可能不足以克服溢出。如果可能，对二项式使用递归公式

于 2014-12-29T23:48:11.533 回答