分苹果
时间限制:1000 ms | 内存限制:65535 KB
难度:2
- 描述
-
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(注意:假如有3个盘子7个苹果,5,1,1和1,5,1 是同一种分法。)
- 输入
- t,表示测试组数(t<=10) 然后t行,每行包含两个数M,N.(1<=M,N<=10)
- 输出
- 输出不同的分法
- 样例输入
-
1 7 3
- 样例输出
-
8
- 上传者
- TC_常红立
写了好久递归真的好难啊,不过这个题貌似有很多好的写法,大神的代码看不懂
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #include<cmath> #include<ctime> #include<queue> #include<stack> #include<string> using namespace std; //#include<windows.h> //#include<conio.h> #define Max(a,b) a>b?a:b #define Min(a,b) a>b?b:a #define mem(a,b) memset(a,b,sizeof(a)) #define malloc(sb) (sb *)malloc(sizeof(sb)) int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}}; int sou(int bn,int a,int pan) { if(pan==1) return 1; if(pan==2) { int k=0; for(int i=1; i<=a; i++) { int w=a-i; if(w<i) break; if(w>bn) continue; k++; } return k; }//当盘数为2的时候计算 int ke=0; for(int i=pan-1; i<=a; i++) { int w=a-i; if(w<1) break; if(w<=bn) ke+=sou(w,i,pan-1);//当盘数为3的总数7的时候可以看成是5,4,3和两个盘子的时候的结果,往后找 } return ke; } int main() { int T; cin>>T; while(T--) { int m,n,guo=0; cin>>m>>n; for(int i=1; i<=n; i++) guo+=sou(m,m,i);//这个包括从1开始的值 cout<<guo<<endl; } }