放苹果（递归）

太过爱你忘了你带给我的痛 2022-06-10 13:44 229阅读 0赞

1664:放苹果

总时间限制:

1000ms

内存限制:

65536kB

描述

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

输入

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

输出

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

样例输入

1
    7 3

样例输出

来源

lwx@POJ

## 解题思路：   设f(m,n)为将m个苹果放入n个盘子的方法数目： ##

##    一、当盘子数目大于苹果数目时：f(m,n)=f(m,m) ##

##    二、当盘子数目小于等于苹果数目时，递归有两种情况： ##

##    1. 有空盘：至少有一个空盘，所以可以先拿出一个盘子不放苹果，f(m,n-1)   2. 无空盘：先将所有盘子都放满苹果，再将剩余的m-n个苹果放入n个盘子中，f(m-n,n); ##

##    递归边界：   无盘子时，返回0；   无苹果时，返回1. ##

#include<iostream>
    using namespace std;
    int f(int m,int n)//把m个苹果放进n个盘子的方法总数
    {
    	if(m<n) return f(m,m);//如果盘子数目多于苹果数，f(m,n)=f(m,m)
    	if(m==0) return 1;//如果苹果数目为零，只有1种方法
    	if(n==0) return 0;//如果盘子为空，方法数为0
    	return f(m,n-1)+f(m-n,n);//有空盘和无空盘 
    }
    int main()
    {
    	int t,m,n;
    	cin>>t;
    	while(t--)
    	{
    		cin>>m>>n;
    		cout<<f(m,n)<<endl;
    	}
    	return 0;
    }

没有空盘的情况：

思路分析：

先将苹果编号为b1,b2,b3...bn

一、 当m>=n:

1. 如果bn独占一个盘子，先将bn放进一个盘子，再将剩余的m-1个苹果放进n-1个盘子中，方法数为：f(m-1,n-1).

2. 如果bn和其他苹果共用一个盘子，现将除bn以外的m-1个苹果放进n个盘子中，再将bn放进其中一个盘子。方法数为f(m-1,n)\*n.

边界条件：

m==0,返回0

n==0,返回0

m==n,返回1（一个盘子放一个苹果）

二、 当m<n:

肯定有空盘，返回0

#include<iostream>
    using namespace std;
    int f(int m,int n)//把m个苹果放进n个盘子的方法总数
    {
    	if(m<n) return 0;//盘子数多，肯定有空盘，不符合条件
    	if(m==0||n==0) return 0;
    	if(n==1||m==n) return 1; 
    	return f(m-1,n-1)+f(m-1,n)*n;//编号为bn的苹果独占一个盘子和共用一个盘子的情况 
    } 
    int main()
    {
    	int t,m,n;
    	cin>>t;
    	while(t--)
    	{
    		cin>>m>>n;
    		cout<<f(m,n)<<endl;
    	}	
    	return 0;
    }