用C++中的置换(nPr，nCr)函数避免整数溢出

Question

我正在尝试做一些与统计相关的函数，这样我就可以执行一些相关的过程(例如:概率的统计计算，生成任意深度的Pascal三角形，等等)。

我遇到了一个问题，我可能正在处理溢出。例如，如果我想计算(n=30，p=1)的nPr，我知道我可以将其简化为：

30P1 = 30! / (30 - 1)!
     = 30! / (29)!
     = 30! / 29!
     = 30

但是，当使用下面的函数进行计算时，由于整数溢出，我似乎总是会得到无效值。有没有不需要使用库就可以支持任意大数字的变通方法？我在其他关于gamma函数的文章中读了一点，但找不到具体的例子。

int factorial(int n) {
   return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
}


int nCr(int n, int r) {
   return (nPr(n,r) / factorial(r));
   //return factorial(n) / factorial(r) / factorial(n-r));
}


int nPr(int n, int r) {
   return (factorial(n) / factorial(n-r));
}

Answer 1

你看起来是在正确的轨道上，所以你开始吧：

#include <math.h>
#include <stdio.h>

int nCr(int n, int r) {
   if(r>n) {
      printf("FATAL ERROR"); return 0;
     }       
   if(n==0 || r==0 || n==r) {
      return 1;
   } else {
      return (int)lround( ((double)n/(double)(n-r)/(double)r) * exp(lgamma(n) - lgamma(n-r) - lgamma(r)));
   }
}


int nPr(int n, int r) {
   if(r>n) {printf("FATAL ERROR"; return 0;}
   if(n==0 || r==0) {
      return 1;
   } else {
      if (n==r) {
         r = n - 1;
      }
      return (int)lround( ((double)n/(double)(n-r)) * exp(lgamma(n) - lgamma(n-r)));
   }
}

要编译，请执行以下操作：gcc -lm myFile.c && ./a.out

请注意，结果的准确性受到double数据类型的位深度的限制。您应该能够获得良好的结果，但需要注意的是:将上面所有的int替换为long long unsigned并不一定能保证较大的n,r值的结果是准确的。在某些情况下，您仍然需要一些数学库来处理任意大的值，但这应该可以帮助您避免较小的输入值。

Answer 2

这是一种不使用gamma函数进行计算的方法。它依赖于n_C_r = (n/r) * ((n-1)C(r-1))的事实，并且对于任何正值，n_C_0 =1，因此我们可以使用它来编写如下所示的递归函数

public long combination(long n, long r) {
    if(r==0)
        return 1;
    else {
        long num = n * combination(n - 1, r - 1);
        return num/r;
    }
}

Answer 3

我想你有两个选择：

1. 使用了一个大整型库。这样你就不会失去精度(浮点可能在某些情况下可以工作，但对你的函数来说是一个很差的substitute).
2. Restructure，所以它们不会达到很高的中间值。例如，factorial(x)/factorial(y)是从y+1到x的所有数字的乘积。所以只要写一个循环和乘法就行了。这样，只有当最终结果溢出时，才会出现溢出。