经典递归问题--放苹果POJ【1664】
浏览数：13 /
时间：2015年06月11日
放苹果
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 25025 | Accepted: 15925 |
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
8
这个题目用常规的模拟思想会感觉很麻烦，但是用递归的思想 会把整个问题分解成一些简单小问题，最后求的解。
假如现在有m个苹果n和盘子，分析一下只有下面几种情况：
【1】苹果比盘子少，那么该问题就和m个苹果m个盘子的问题一样，问题规模被减小，解法不变。
【2】苹果比盘子多，这时侯的解由两部分构成：所有盘子都有苹果+不是所有盘子都有苹果。其中不是所有盘子都有苹果这种情况和至少有一个盘子空着这种情况是一样的，这样问题就变成了m个苹果放在n-1个盘子里！问题规模减小，解法同样不变。而所有盘子都有苹果说明每个盘子至少有一个苹果，说明有n个苹果是固定的，变数是剩下的m-n个苹果！那么这个问题和m-n个苹果放在n个盘子里是一致的！问题规模减小，解法不变。如果问题规模减小到只剩一个盘子或者没有苹果了，那么解法就一种，我们要返回1。综上我们可以用递归来解决这个问题。
代码：
#include<iostream>
using namespace std;
int count(int m,int n)//m apples
{
if(m==0||n==1) return 1;
if(n>m) return count(m,m);
return count(m-n,n)+count(m,n-1);
}
int main()
{
int cnt=0;
int apples=0,dishes=0;
while(cin>>cnt)
{
while(cnt--)
{
cin>>apples>>dishes;
int ans=count(apples,dishes);
cout<<ans<<endl;
}
}
return 0;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
