| 标题 | 标签 |
|---|---|
| binomialCoefficient(二项式系数) | math,algorithm,beginner(数学,算法,初学者) |
计算从 n 个项目中选择 k 个项目的方法数,不重复且无顺序。
- 使用
Number.isNaN()检查两个值中是否有任何一个为NaN。 - 检查
k是否小于0、大于或等于n、等于1或n - 1并返回适当的结果。 - 检查
n - k是否小于k并相应地切换它们的值。 - 从
2到k循环并计算二项式系数。 - 使用
Math.round()来解决计算中的舍入误差。
二项式系数(Binomial Coefficient)是组合数学中的一个重要概念,通常用于表示从 n 个不同元素中选择 k 个元素的方式数。二项式系数在代数学中也非常重要,出现在二项式定理中。
二项式系数(C(n, k))表示从 n 个元素中选取 k 个元素的组合数。它也可以表示为:
C(n, k) = \binom{n}{k} = \frac{n!}{k!(n - k)!}其中,n!是 n 的阶乘,表示从 1 乘到 n 的所有正整数的积。
- 阶乘 (factorial) 是一个数的所有正整数之积,表示为
n! = n * (n−1) * (n−2) * ... * 1。 - 特别地,
0 != 1。
二项式系数(C(n, k))可以看作是从 n 个元素中选择 k 个元素的方式数。这是一个组合问题,与排列不同,排列考虑了顺序,而组合则不考虑顺序。举个例子:
- 从 3 个不同的球(例如红球、蓝球和绿球)中选取 2 个球的不同组合数就是
C(3,2) = 3 * 2 * 1 / 2 * 1 * (3 - 2) * 1 = 3,可以选择(红球和蓝球)、(红球和绿球)、(蓝球和绿球)。
二项式定理(Binomial Theorem)描述了一个二项式表达式的展开式:
(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k其中,C(n, k)就是二项式系数,表示从n项中选取k项的系数。
例如,计算 C(5,2):
C(5,2) = 5! / (2! \* (5 - 2)!)
计算各阶乘:
5! = 5 * 4 * 3 * 2 * 1 = 1202! = 2 * 1 = 2(5 - 2)! = (3 * 2 * 1) = 6
所以:
C(5,2) = 120 / 2 * 6 = 120 / 12 = 10
因此,C(5,2) = 10。
假设 x = 1 和 y = 2,我们要展开 (1 + 2) ^ 3。
根据二项式定理:
(1 + 2) ^ 3 = \sum_{k=0}^{3} \binom{3}{k} 1^{3-k} 2^k展开每一项:
k = 0: {3}{0} 1^{3-0} 2^0 = 1 * 1 * 1 = 1k = 1: {3}{1} 1^{3-1} 2^1 = 3 * 1 * 2 = 6k = 2: {3}{2} 1^{3-2} 2^2 = 3 * 1 * 4 = 12k = 3: {3}{3} 1^{3-3} 2^3 = 1 * 1 * 8 = 8
因此,展开式为:(1 + 2)^3 = 1 + 6 + 12 + 8 = 27。
可以使用递归或动态规划来计算二项式系数,下面是一个简单的 JavaScript 示例:
// 计算阶乘
function factorial(n) {
if (n === 0) return 1;
let result = 1;
for (let i = 1; i <= n; i++) {
result *= i;
}
return result;
}
// 计算二项式系数
function binomialCoefficient(n, k) {
return factorial(n) / (factorial(k) * factorial(n - k));
}
// 示例:计算 binomialCoefficient(5, 2)
console.log(binomialCoefficient(5, 2)); // 输出: 10递归计算阶乘会有性能问题,特别是对于大的 n 值。你可以使用动态规划来优化二项式系数的计算。
function binomialCoefficientDP(n, k) {
let dp = Array(n + 1).fill().map(() => Array(k + 1).fill(0));
// 基本情况
for (let i = 0; i <= n; i++) {
dp[i][0] = 1; // 任何数选择 0 个元素的组合数都是 1
}
for (let j = 0; j <= k; j++) {
dp[j][j] = 1; // 任何数选择自身个数的组合数也是 1
}
// 填充 DP 表
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= Math.min(i, k); j++) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}
}
return dp[n][k];
}
// 示例:计算 binomialCoefficientDP(5, 2)
console.log(binomialCoefficientDP(5, 2)); // 输出: 10- 二项式系数是组合数学中的一个重要概念,表示从 n 个元素中选择 k 个元素的方式数,计算公式为:
C(n, k) = \binom{n}{k} = \frac{n!}{k!(n - k)!}- 它在二项式定理中有着广泛应用,用于展开表达式
(x + y) ^ n。 - 通过不同的方法(如阶乘法、递归、动态规划等)可以高效地计算二项式系数。
代码如下:
const binomialCoefficient = (n, k) => {
if (Number.isNaN(n) || Number.isNaN(k)) return NaN;
if (k < 0 || k > n) return 0;
if (k === 0 || k === n) return 1;
if (k === 1 || k === n - 1) return n;
if (n - k < k) k = n - k;
let res = n;
for (let j = 2; j <= k; j++) res *= (n - j + 1) / j;
return Math.round(res);
};ts 代码如下:
调用方式:
binomialCoefficient(8, 2); // 28应用场景
以下是一个实战示例:
结果如下:
<iframe src="codes/javascript/html/binomial-coefficient.html"></iframe>