成都网站建设 哪家比较好,国内十大管理咨询公司,韩国小游戏网站,jsp网站开发实例视频教程题目描述
把 m 个同样的苹果放在 n 个同样的盘子里#xff0c;允许有的盘子空着不放#xff0c;问共有多少种不同的分法。#xff08;5,1,15,1,1 和 1,1,51,1,5 是同一种方法#xff09;
输入格式
第一行是测试数据的数目 t#xff0c;以下每行均包括二个整数 m 和 n允许有的盘子空着不放问共有多少种不同的分法。5,1,15,1,1 和 1,1,51,1,5 是同一种方法
输入格式
第一行是测试数据的数目 t以下每行均包括二个整数 m 和 n以空格分开。
输出格式
对输入的每组数据 m 和 n用一行输出相应的结果。 #includeiostream
using namespace std;
int dfs(int a, int b)
{if (a 1 || a 0 || b 1){return 1;}else if (a b){return dfs(a, a);}else if (a b){return dfs(a - b, b) dfs(a, b - 1);}
}
int main()
{int num;int a, b;int sum[1000];int count 0;cin num;while (num--){cin a b;int resdfs(a, b);sum[count] res;count;}for (int i 0; i count; i){cout sum[i] endl;}return 0;
}对输入的ab 分为三种情况考虑
1 苹果数为1 或者 0 盘子数为1盘子数不会为0因为到1就返回了但是苹果会 返回 1
2苹果小于盘子数量 用苹果个数的盘子考虑即可
3苹果个数大于等于盘子个数分两种情况考虑放满盘子和不放满盘子这样就包含了所有情况
