二项式系数函数 C++ 的不同输出

Question

我用两种方法计算二项式系数。一个是

int fac(int n) {
if ( n < 2 ) return 1; // return 1 when n=0,1
int ret = 1;
for(int i=2; i <= n; ++i)
    ret *= i;  // calculate factorial
return ret;
}
int choose_fac(int n, int k) {
  return fac(n)/fac(k)/fac(n-k);
}

另一个是：

int choose_dp(int n, int k) {
  int C[n+1][k+1];
  int i, j;
  for (i = 0; i <= n; i++) {
        for (j = 0; j <= min(i, k); j++) {
            if (j == 0 || j == i) C[i][j] = 1;
            else C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
  }
  return C[n][k];
}

所以当我运行在 (15,5) 上时，第二个给出正确答案而第一个给出 4。我知道对于 choose_fac 计算时 int 超出范围15！，但如果这是原因，为什么 choose_dp 没有 return 一个错误的答案，因为它们都使用 int 来定义函数？

非常感谢！

E.

Answer 1

第一个溢出 int。

当你调用fac(15)来计算choose_fac(15, 5)函数应该计算的值时，1,307,674,368,000大大超出了int的范围。计算的最终结果 15 choose 5 将在 int 的范围内，因为两个相对较大的阶乘相除，但中间结果中的错误阻止了此计算成功完成。

第二个函数使用动态规划，没有这个问题，因为它没有显式计算阶乘。这种计算二项式系数的方法称为 Pascal's Triangle.

Answer 2

当你 return fac(n)/fac(k)/fac(n-k);它是从左到右评估的。 (((fac(n)) /fac(k))/fac(n-k)) 第一次评估 fac(n) 给出溢出错误。

二项式系数函数 C++ 的不同输出

Different output for binomial coefficient function C++

c++

int

range

long-integer