首页 > 代码库 > 放鸡蛋_鸡蛋篮子问题1

放鸡蛋_鸡蛋篮子问题1

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
17 3
Sample Output
8

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

直接上代码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     else31       return ways(eggs - baskets, baskets) + ways(eggs, baskets - 1);32   }  
View Code

 

放鸡蛋_鸡蛋篮子问题1