C ++函数计算阶乘返回负值 [英] C++ function to calculate factorial returns negative value

问题描述

我编写了一个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）
返回1； 
 long int x = 1； 
 if（n> 1）
 x = n * fact（n-1）; 
返回x; 
} 
  

以下行包含在主函数中：

  long int ans = 0; 
 ans = ans +（事实（2 * n）/（事实（n）*事实（n）））; 
 cout<< ans; 
  

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

注意：此功能在n&== 10时效果很好。我尝试了long long int而不是long int，但是它仍然无法正常工作。

解决方案

实际计算阶乘是不明智的-他们成长非常快。通常，使用组合公式时，最好寻找一种重新排序操作的方式，以使中间结果受到一定程度的约束。

例如，让我们来看一下（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; 
} 
回返； 
} 
  

演示

I've written a C++ function to calculate factorial and used it to calculate ²²C₁₁ (Combination). I have declared a variable ans and set it to 0. I tried to calculate

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

where i sent n as 11. For some reason, i'm getting a negative value stored in answer. How can i fix this?

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;
}

The following lines are included in the main function:

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

The answer i'm getting is -784 The correct answer should be 705432

NOTE: This function is working perfectly fine for n<=10. I have tried long long int instead of long int but it still isn't working.

解决方案

It is unwise to actually calculate factorials - they grow extremely fast. Generally, with combinatorial formulae it's a good idea to look for a way to re-order operations to keep intermediate results somewhat constrained.

For example, let's look at (2*n)!/(n!*n!). It can be rewritten as ((n+1)*(n+2)*...*(2*n)) / (1*2*...*n) == (n+1)/1 * (n+2)/2 * (n+3)/3 ... * (2*n)/n. By interleaving multiplication and division, the rate of growth of intermediate result is reduced.

So, something like this:

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

Demo

这篇关于C ++函数计算阶乘返回负值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！