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 和阶乘中。他们都必须检测到这种溢出。

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

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

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

Answer 2

在您的代码中，最大值始终为factorial(n)，
因此您只需要检查它n!是否大于2.147.483.647(max int value)。

请注意，存储的最大值可以根据int内存中类型的大小而有所不同（不同的机器可以指定不同的大小）。

但是，int类型变量中的最后一位保留用于存储符号（+或-），因此最大值可以是和的一半65.535，4.294.967.295即类型的32.767和。2.147.483.647int

SIZE_OF_INT(bits)    MAX VALUE(UNSIGNED)     MAX_VALUE(SIGNED)
---------------------------------------------------------------
16                   65.535                  32.767
32                   4.294.967.295           2.147.483.647

价值13！可以超出类型的最大值int（32 位）。

12! = 479.001.600 and
13! = 6.227.020.800

因此，您需要检查nCr(int n, int r)的最大值n始终小于13 (i.e. n<=12)和r<=n。并在factorial(int n): n<=12。