C++函数计算阶乘returns负值

Question

我写了一个 C++ 函数来计算阶乘，并用它来计算 ²²C₁₁（组合）。我已经声明了一个变量 ans 并将其设置为 0。我试图计算

22C11 = fact(2*n)/(fact(n)*fact(n))

我将 n 发送为 11。出于某种原因，我在答案中存储了一个负值。我该如何解决这个问题？

long int fact(long int n) {
    if(n==1||n==0)
        return 1;
    long int x=1;
    if(n>1)
    x=n*fact(n-1);
    return x;
}

main函数中包含以下几行：

long int ans=0;
    ans=ans+(fact(2*n)/(fact(n)*fact(n)));
cout<<ans;

我得到的答案是-784 正确答案应该是 705432

注意： 此函数在 n<=10 时运行良好。我已经尝试使用 long long int 而不是 long int，但它仍然无法正常工作。

Answer 1

您正在触发整数溢出，这会导致未定义的行为。实际上，您可以使用 long long int 或 unsigned long long int 来获得更高的精度，例如：

unsigned long long fact(int n)
{
    if(n < 2)
        return 1;

    return fact(n-1) * n;
}

你说你试过了但没有用，但我猜你忘了也更新 x 的类型或其他东西。（在我的版本中，我删除了 x，因为它是多余的）。 And/or 你的计算还是太大了，溢出了 unsigned long long int。

您可能对 this thread 感兴趣，它展示了一种无需太多中间存储即可计算出 nCr 的算法。

Answer 2

22！ = 1,124,000,727,777,607,680,000

2⁶⁴ = 18,446,744,073,709,551,615

因此，除非 unsigned long long 有 128 位整数，否则就会出现整数溢出。

Answer 3

实际计算阶乘是不明智的——它们增长得非常快。通常，对于组合公式，寻找一种方法来 re-order 操作以保持中间结果在某种程度上受到约束是个好主意。

例如，我们来看(2*n)!/(n!*n!)。可以改写为((n+1)*(n+2)*...*(2*n)) / (1*2*...*n) == (n+1)/1 * (n+2)/2 * (n+3)/3 ... * (2*n)/n。通过乘法和除法交织，降低了中间结果的增长率。

所以，像这样：

int f(int n) {
  int ret = 1;
  for (int i = 1; i <= n; ++i) {
    ret *= (n + i);
    ret /= i;
  }
  return ret;
}

Demo

Answer 4

您通过避免蛮力方法增加了成功的机会。

COMB(N1, N2) = FACT(N1)/(FACT(N1-N2)*FACT(N2))

你可以利用这个事实，即提名人和分母都有很多共同的条款。

COMB(N1, N2) = (N1-N2+1)*(N1-N2+2)*...*N1/FACT(N1)

这是一个利用该知识并计算 COMB(22,11) 的实现，整数溢出的风险要小得多。

unsigned long long comb(int n1, int n2)
{
   unsigned long long res = 1;
   for (int i = (n1-n2)+1; i<= n1; ++i )
   {
      res *= i;
   }

   for (int i = 2; i<= n2; ++i )
   {
      res /= i;
   }

   return res;
}

C++函数计算阶乘returns负值

C++ function to calculate factorial returns negative value

c++

algorithm

integer-overflow

factorial