放鸡蛋_鸡蛋篮子问题1

时间：2014-11-10 11:34:11 收藏：0 阅读：159

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

这道题有一系列的问题，这一题求的是有多少种放法，还有一题是打印每一种放法。我个人感觉前一种比较简单。

直接上代码O(∩_∩)O

 1 // 这道题用递归的方法 （m表示鸡蛋的数量，n表示篮子的数量） 
 2 // 当只剩下一个篮子或者一个鸡蛋时，肯定只有一种情况，所以 return 1； 
 3 // 当m=n时，可以拆解为m个篮子都有鸡蛋+ 少于m个篮子有鸡蛋的情况 
 4 // 当 m < n时， 实际可用的篮子 最多只有m个，等价于m = n的情况（去掉多余的篮子） 
 5 // 当m > n时， 分成全部篮子都有鸡蛋（每个篮子都有一个，再把剩下的m-n个分到n个篮子中） 
 6 // 以及 没有把所有篮子都用上的情况
 7 
 8  
 9 #include <iostream> 
10 #include <cstdlib>
11 using namespace std;
12   int ways(int eggs, int baskets);
13 
14   int main() {
15     int t;
16     cin >> t;
17     while (t--) {
18       int m, n;
19       cin >> m >> n;
20       int k = ways(m, n);
21       cout << k << endl;
22     }
23  // system("pause");
24   return 0;
25   }
26   int ways(int eggs, int baskets) {
27     if (baskets == 1 || eggs == 1) return 1;
28     if (baskets >= eggs)
29       return 1 + ways(eggs, eggs - 1);
30     else
31       return ways(eggs - baskets, baskets) + ways(eggs, baskets - 1);
32   }

View Code

原文：http://www.cnblogs.com/tonyyangsysu/p/4086675.html