A40993. 求组合数
填空题
中等
知识点
题目描述
求组合数
题目描述
组合数的计算虽说简单但也不乏有些陷阱，这主要是因为语言中的数据类型在表示范围上是有限的。更何况还有中间结果溢出的现象，所以千万要小心。
输入格式
求组合数的数据都是成对（M与N）出现的，每对整数M和N满足0＜m, n≤20，以EOF结束。
输出格式
输出该组合数。每个组合数换行。
样例输入
5 2
18 13
样例输出
10
8568
参考答案
#include<stdio.h>
int res[30][30];
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
//如果我们已经求出过该值，直接输出，可降低时间复杂度
if(res[n][m]){
printf("%d\n",res[n][m]);
continue;
}
for(int i=0;i<=n;i++){//杨辉三角的第1列全部是1
res[i][0]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
res[i][j]=res[i-1][j-1]+res[i-1][j];//递推式
}
}
printf("%d\n",res[n][m]);
}
return 0;
}
上一题
下一题