C++函数计算阶乘返回负值

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

实际计算阶乘是不明智的——它们增长得非常快。通常，对于组合公式，最好寻找一种方法来重新排序操作以在一定程度上限制中间结果。

例如，让我们看一下(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