c - 使用 C 中的置换 (nPr, nCr) 函数避免整数溢出

Question

我正在尝试做一些与统计相关的功能，这样我就可以执行一些相关的程序(即:概率的统计计算，为任意深度生成帕斯卡三角形等)。

我遇到了一个可能要处理溢出的问题。例如，如果我想计算 (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

这是一种不使用 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;
    }
}