组合数公式

组合恒等式

若表示在 n 个物品中选取 m 个物品，则如存在下述公式：

C(n,m)=C(n,n-m)=C(n-1,m-1)+C(n-1,m)

所以可以用递推算组合数

例题：

题目描述
开学了，学校又迎来了好多新生。ACMer想为新生准备一个节目。来报名要表演节目的人很多，多达N个，但是只需要从这N个人中选M个就够了，一共有多少种选择方法？

输入
测试实例包括多组测试数据，每组数据占一行。
每组数据包含两个整数N（来报名的人数,1<=N<=30），M（节目需要的人数0<=M<=30）

输出
每组数据输出一个整数，每个输出占一行

样例输入
3 2
5 3
4 4
3 6
8 0
样例输出
3
10
1
0
1

代码
#include<iostream> #include<cmath> using namespace std; int cs(int n,int m){ if
(m==0) return 1; if(m==1) return n; if(m>n/2) return cs(n,n-m); if(m>1) return
cs(n-1,m-1)+cs(n-1,m); } int main(){ int n,m; while(cin>>n>>m){ if(n<m) cout<<0
<<endl;else cout<<cs(n,m)<<endl; } }

• « 上一篇：完全图解Seq2Seq Attention模型
• » 下一篇：java随笔——HashMap与红黑树