算法中常用的数学方法

求排列数

$$A_n^m=\frac{n!}{(n - m)!}$$

/**
 * Anm = n! / (n - m)!
 * @param {number} n
 * @param {number} m
 */
var arrangement = function (n, m) {
  let result = 1
  // n的阶乘除以n-m的阶乘 最终的结果就是 (n - 0) * (n - 1) * (n - 2) * ... * (n - m - 1)
  // result *= (n - i) (0 <= i < m)
  for (let i = 0; i < m; i++) {
    result *= (n - i)
  }
  return result
}

求组合数

$$C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m! * (n - m)!}$$

/**
 * Cnm = Anm / m! = n! / m!*(n - m)!
 * @param {number} n
 * @param {number} m
 */
var combination = function (n, m) {
  let result = 1;
  for (let i = 0; i < m; i++) {
    // i + 1 等价与m的阶乘
    // n - i 等价于 n的阶乘
    // n！/（n - m）！ 最终的结果是n的阶乘只做到 n - m  因为从后面 分子分母就可以约掉
    result *= (n - i) / (i + 1);
  }
  return result;
}

卡特兰数

例：96.不同的二叉搜索树 (opens new window)

$$C_0=1 \quad C_{n+1}=C_n * \frac{2(2n + 1)}{n + 2}$$

/**
 * 通项公式：C0 = 1  Cn+1 = (2(2n + 1) / (n + 2)) * Cn
 * @param {number} n 卡特兰数的第几项(n >= 0)
 */
var catalanNumber = function (n) {
  let C = 1
  for (let i = 0; i < n; i++) {
    C = C * 2 * (2 * i + 1) / (i + 2)
  }
  return C
}

海伦公式

$$S=\sqrt{p(p-a)(p-b)(p-c)} \quad p=\frac{a+b+c}{2}$$

/**
 * 已知三边长度求三角形面积
 * S = (p(p-a)(p-b)(p-c)) ^ 1/2  其中 p = (a+b+c)/2 （半周长）
 * @param {number} a
 * @param {number} b
 * @param {number} c
 */
var heron = function (a, b, c) {
  const p = (a + b + c) / 2
  return Math.sqrt(p * (p - a) * (p - b) * (p - c))
}