详细解释思路(当苹果数大于等于盘子数时的分法):一种是目前所有的盘子都放一个苹果,盘子数不变,即: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中,最后输出;
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int t;
int mn[25][2];
int dfs(int m,int n){
if(m==0||m==1||n==1)return 1;
if(m<n)return dfs(m,m);/当苹果数少于盘子数,就只有m个盘子作用,所以接下来就计算m个苹果和m个盘子;
if(m>=n)return dfs(m-n,n)+dfs(m,n-1);
//如果苹果数大于等于盘子数,分成两个部分,一种是目前所有的盘子都放一个苹果,另一种是拿一个盘子不放;
}
int main()
{
scanf("%d",&t);
for(int i=0;i<t;i++)scanf("%d%d",&mn[i][0],&mn[i][1]);
for(int i=0;i<t;i++){
int test=dfs(mn[i][0],mn[i][1]);
printf("%d\n",test);
}
return 0;
}