课程题目 : 1020. 放鸡蛋

Description

把M个同样的鸡蛋放在N个同样的篮子里，允许有的篮子空着不放，问共有多少种不同的放法？（用K表示）5，1，1和1，5，1 是同一种分法。

Input

第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

Output

对输入的每组数据M和N，用一行输出相应的K。

Sample Input

1
7 3

Sample Output

思路：（这里用m表示鸡蛋数量，用n表示篮子数量）

题目用了递归的思想，当只剩下1个篮子或者只剩下1个鸡蛋时肯定只有1种情况。

当m=n时，可以拆解为m个篮子都有鸡蛋（1种）加上少于m个篮子有鸡蛋的情况

当m<n时，实际上用的上的篮子只有m个，可以等价为m=n的情况(去掉多余的篮子)

当m>n时，拆解为2种情况，第一种是全部篮子都有鸡蛋（假设每个篮子都有1个），再把剩下的m-n个分到n个篮子中，

第二种情况是没有把全部篮子用上

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int find_num_of_ways(int num_of_eggs,int num_of_baskets); //传进鸡蛋的数量与篮子的数量返回放置鸡蛋方法的种数
 5 
 6 int main(){
 7     int t;
 8     cin>>t;
 9     while(t--){
10         int num_of_eggs,num_of_baskets;
11         cin>>num_of_eggs>>num_of_baskets;
12         cout<<find_num_of_ways(num_of_eggs,num_of_baskets)<<endl;
13     }
14     return 0;
15 }
16 int find_num_of_ways(int num_of_eggs,int num_of_baskets){
17     if(num_of_baskets==1||num_of_eggs==1) //只有1个篮子或1个鸡蛋时只有1种放置方法
18         return 1;
19     if(num_of_baskets>=num_of_eggs) //篮子多余鸡蛋时等于每个篮子放一个鸡蛋的情况（1种）加上把鸡蛋放到比鸡蛋数量少1个篮子的情况数
20         return 1+find_num_of_ways(num_of_eggs,num_of_eggs-1);
21     else
22         return find_num_of_ways(num_of_eggs-num_of_baskets,num_of_baskets)//每个篮子放一个鸡蛋后剩下num_of_eggs-num_of_baskets个鸡蛋放到num_of_baskets个篮子里
23                 +find_num_of_ways(num_of_eggs,num_of_baskets-1);//不是全部篮子用上的情况
24 }