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

目前，当我输入一个对于计算来说太大的数字时，我得到一个从命令行返回的浮点型错误。

对于这个溢出检查，我遇到了麻烦。任何帮助都将不胜感激，谢谢。

Answer 1

在您的代码中，最大值始终为factorial(n)，

所以你只需要检查n!是否不大于2.147.483.647 (最大整数值)。

请注意，根据内存中int类型的大小，存储的最大值可能不同(不同的机器可以指定不同的大小)。

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

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。

Answer 2

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

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