计算组合数 C(n,m)
最编程
2024-04-08 16:49:43
...
#include<cstdio>
#pragma warning(disable:4996)
//组合数C(n,m)的计算
//方法1：通过定义式计算，因为涉及阶乘结果大，long long型只能接收n<=20的数据范围
long long C(long long n, long long m) {
long long ans = 1;
for (long long i = 1; i <= n; i++) { //先计算n!，得ans
ans *= i;
}
for (long long i = 1; i <= m; i++) { //然后ans除以m!，得ans
ans /= i;
}
for (long long i = 1; i <= n - m; i++) { //然后ans除以(n-m)!，得最终结果ans
ans /= i;
}
return ans;
}
//方法2原始递推版本，不涉及阶乘，但会有很多C(n,m)重复计算
long long C(long long n, long long m) {
if (m == 0 || m == n) return 1;
return C(n - 1, m) + C(n - 1, m - 1);
}
//方法2改进递推版本，消除重复计算，计算所有C(n,m)的时间复杂度O(n^2)
const int n = 60;
void calC() {
for (int i = 0; i <= n; i++) {
res[i][0] = res[i][i] = 1; //初始化边界C(n,0)=C(n,n)=1
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= i/2; j++) {
res[i][j] = res[i - 1][j] + res[i - 1][j - 1]; //递推计算C(i,j)=C(i-1,j)+C(i-1,j-1)
res[i][i - j] = res[i][j]; //C(i,i-j)=C(i,j)
}
}
}
//方法2改进递归版本，消除重复计算，单次计算C(n,m)的时间复杂度不超过O(n^2)，总时间与具体数据有关
long long res[60][60] = { 0 }; //存储C(n,m)结果
long long C(long long n, long long m) {
if (m == 0 || m == n) return 1;
if (res[n][m] != 0) return res[n][m]; //如果C(n,m)已经计算过，则直接返回该结果
return res[n][m] = C(n - 1, m) + C(n - 1, m - 1); //C(n,m)没有计算过，则递归计算并将结果存入res中
}
//方法3使用定义式的变形进行计算，时间复杂度O(m)，它支持的数据范围比方法2小一些
long long C(long long n, long long m) {
long long ans = 1;
for (long long i = 1; i <= m; i++) { //按照公式进行m次乘法和除法
ans = ans * (n - m + i) / i; //注意必须先乘再除
}
return ans;
}
上一篇： Qt小案例