题解 P2386 【放苹果】

· · 题解

C++代码解析

基本思路：递归 记录 AC

代码呈上：

#include<iostream>//个人不建议使用万能头文件；可能编译出错；
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
int sum[10000];//用来记录每一组数据最后的结果
int apple(int m,int n)//m是苹果数，n是盘子数 
{
    if(m==0||m==1||n==1)//边界：当苹果只有一个或者没有苹果时或者盘子只有一个时，只有一种放法，所以达到边界，返回值；
    return 1;
    if(m<n)//当苹果数少于盘子数，就只有m个盘子作用，所以接下来就计算m个苹果和m个盘子；
    return apple(m,m);
    if(m>=n)//如果苹果数大于等于盘子数，分成两个部分，一种是目前所有的盘子都放一个苹果，另一种是拿一个盘子不放；
    return apple(m-n,n)+apple(m,n-1);
}
int main()
{
    int n,m,s;//其中s是数据的个数；
    cin>>s;
    for(int i=1;i<=s;i++)
    {    
        cin>>m>>n;//m是苹果数，n是盘子数
        sum[i]=apple(m,n);//将每一组的苹果和盘子的到的结果记录在sum数组之中；
    }
    for(int j=1;j<=s;j++)
    cout<<sum[j]<<endl;//输出数据；
    return 0;
}

详细解释思路（当苹果数大于等于盘子数时的分法）：一种是目前所有的盘子都放一个苹果，盘子数不变，即：apple(m-n,n);

另一种是将一个盘子不放，再来进行思考，即：apple(m,n-1);

两种情况的总和就是答案；

接下来就用一个例子来详细解释：

现在有5个苹果和3个盘子；

因为苹果数大于盘子数，所以分成两种：

第一种：目前所有盘子放一个苹果（目前盘子数3个）apple(2,3);

第二种：拿一个盘子不放苹果，剩下的盘子继续考虑，apple(5,2);

apple(2,3):因为苹果数小于盘子数，所以apple(2,2);

apple(2,2):因为苹果数等于盘子数，所以又分为两种：

第一种：目前所有盘子放一个苹果（目前盘子数2个）apple(0,2); 没有苹果，达到边界，返回值1；

第二种：拿一个盘子不放苹果，剩下的盘子继续考虑，apple(2,1); 盘子数只有1个，达到边界，返回值1；

apple(5,2):因为苹果数大于盘子数，所以又分为两种：

第一种：目前所有盘子放一个苹果（目前盘子数2个)apple(3,2);

第二种：拿一个盘子不放苹果，剩下的盘子继续考虑，apple(5,1); 因为盘子数只有1个，达到边界，返回值1；

apple(3,2):因为苹果数大于盘子数，所以又分为两种：

第一种：目前所有盘子放一个苹果（目前盘子数2个)apple(1,2); 苹果数只有1个，达到边界，返回值1；

第二种：拿一个盘子不放苹果，剩下的盘子继续考虑，apple(3,1); 盘子数只有1个，达到边界，返回值1；

所有的值相加得到最后的结果5，记录在数组sum中，最后输出；

以上就是本题所有的讲解，要查看更多内容，学到更多知识，请查看我的博客：https://www.luogu.org/blog/AHacker/