c - 检测 nCr 函数中的溢出

Question

我这里有两个函数一起计算 nCr:

int factorial(int n) {
int c;
int result = 1;

 for (c = 1; c <= n; c++)
 {
  result = result*c;

 }

return result;
}




int nCr(int n, int r) {
int result;

 result = factorial(n)/(factorial(r)*factorial(n-r));

 return result;
}

我在执行需要执行的错误检查时遇到了问题。随着 n 变大，我将没有计算 n 的能力!并且此错误检查必须同时存在于 nCr 和阶乘中。他们都必须检测到这种溢出。

目前，当我输入一个太大而无法计算的数字时，我会从命令行返回一个 float 类型错误。

我无法解释此溢出检查。任何帮助将不胜感激，谢谢。

Answer 1

计算二项式系数的更好方法

typedef unsigned long long ull;

ull nCr(int n, int r) {
    ull res = 1;
    if (r > n - r) r = n - r;
    for (int i = 0; i < r; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}