如何使用 JavaScript 求两个整数的二项式系数？

什么是二项式系数？

二项式系数就是二项式定理中的系数，表示了二项式多项式的各项之间的关系。二项式系数也是组合数学中的一个重要概念，表示从 $n$ 个不同的元素中取出 $k$ 个元素的组合个数。

具体来说，如果有一个二项式 $(a+b)^n$，它展开后得到的式子为：

$(a+b)^n = C_n^0a^n + C_n^1a^{n-1}b + C_n^2a^{n-2}b^2 + \cdots + C_n^ra^{n-r}b^r + \cdots + C_n^nb^n$

其中，$C_n^r$ 就是从 $n$ 个元素中取出 $r$ 个元素的组合数，可以用以下公式计算：

$C_n^r = \frac{n!}{r!(n-r)!}$

为了方便计算，上式可以写成下面的递推公式：

$C_n^r = C_{n-1}^{r-1} + C_{n-1}^r$

JavaScript计算二项式系数的方法

方法一：使用递归

通过二项式系数递推公式，我们可以写出下面的递归函数：

function binomialCoeff(n, k) {
  if (k == 0 || k == n) {
    return 1;
  } else {
    return binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k);
  }
}

该函数的参数 $n$ 和 $k$ 分别表示从 $n$ 个元素中取出 $k$ 个元素的组合数，函数返回值为 $C_n^k$。此函数的时间复杂度为 $O(2^n)$，因为每次递归都会调用两次自身。

递归方法的优点：

代码简单易懂，易理解。

递归方法的缺点：

时间复杂度很高，在 $n$ 比较大的时候运算速度非常慢。

递归深度太深，在 $n$ 较大时可能会导致栈溢出。

方法二：使用循环

为了降低时间复杂度，我们可以使用循环来代替递归。具体来说，我们可以用一个二维数组来存储每个 $C_n^k$ 的值，然后用循环来计算。

function binomialCoeff(n, k) {
  let C = new Array(n + 1);
  for (let i = 0; i <= n; i++) {
    C[i] = new Array(k + 1);
  }
  for (let i = 0; i <= n; i++) {
    for (let j = 0; j <= Math.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];
}

该函数的时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。

循环方法的优点：

时间复杂度较低，可以在较短的时间内计算出大量的二项式系数。

空间复杂度也比较低，因为只需要用一个二维数组来存储所有的 $C_n^k$ 值。

循环方法的缺点：

代码比递归复杂一些。

应用实例

下面是一个使用循环方法计算二项式系数的例子：

let n = 5;
let k = 2;
let result = binomialCoeff(n, k);
console.log("C(" + n + ", " + k + ") = " + result); // C(5, 2) = 10

该例子计算的是从 $5$ 个元素中取出 $2$ 个元素的组合个数，即 $C_5^2$ 的值为 $10$。