目录
- 1 基础知识
- 2 模板
- 3 工程化
1 基础知识
(一)
组合数
C
n
k
C_n^k
Cnk的计算公式,
C
n
k
=
n
!
k
!
⋅
(
n
−
k
)
!
C_n^k=\frac{n!}{k!\cdot (n-k)!}
Cnk=k!⋅(n−k)!n!
故可以这样计算,
int compute_combination_n_k(int n, int k) {
if (k > n) {
return -1;//输入参数不合法
}
long long a = 1, b = 1, c = 1;
for (int i = 1; i <= n; ++i) {
a = a * i; //计算a时,可能会超出long long范围
}
for (int i = 1; i <= k; ++i) {
b = b * i;
}
for (int i = 1; i <= n - k; ++i) {
c = c * i;
}
long long res = a / b / c;
return res;
}
该计算方法的缺点是,在计算
n
!
n!
n!时,可能会超出long long
范围。
(二)
第(一)中的公式进行简化,有,
C
n
k
=
n
⋅
(
n
−
1
)
⋯
(
n
−
k
+
1
)
1
⋅
2
⋯
k
C_n^k=\frac{n\cdot(n-1)\cdots(n-k+1)}{1\cdot 2\cdots k}
Cnk=1⋅2⋯kn⋅(n−1)⋯(n−k+1)
注意需要满足
k
≤
n
k\leq n
k≤n。
将上述公式转换为代码,如下所示,
int compute_combination_n_k(int n, int k) {
if (k > n) {
return -1; //-1表示无效值。
}
long long a = 1;//表示分子
long long b = 1;//表示分母
for (int i = 1; i <= k; ++i) {
a = a * (n - i + 1); //注意这一步可能会超出long long最大值
b = b * i;
}
long long res = a / b;
return res;
}
上述代码在计算分子时比较容易超出long long
,一般不采取这种计算方法,除非n
比较小。
(三)
组合数的递推公式,
C
n
k
=
C
n
−
1
k
−
1
+
C
n
−
1
k
C_n^k=C_{n-1}^{k-1}+C_{n-1}^{k}
Cnk=Cn−1k−1+Cn−1k
注意需要满足
k
≤
n
k\leq n
k≤n。
利用该公式可以在
O
(
n
)
O(n)
O(n)时间复杂度下求出N
以内的所有组合数,代码如下,
const int N = 2010;
int c[N][N];
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= i; ++j) {
if (!j) {
c[i][j] = 1;
} else {
c[i][j] = c[i-1][j-1] + c[i-1][j];
}
}
}
使用上述计算方法,一般不会超出long long
范围。
2 模板
暂无。。。
3 工程化
暂无。。。