NOI--放苹果

27:单词翻转

题目:放苹果

描述

把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

样例输出

8

解题:

m个苹果放在n个盘中里，分类讨论：

1、如果m < n ,至少会有n-m个盘子是空的，所以忽略这些盘子，f(m, n) = f(m, m)

2、如果m >= n,因为有的盘子为空有的不为空，所以总分法 = 有空盘子 + 无空盘子，有空盘子时，至少有一个空盘子所以等于f(m,n-1),没有空盘子时候，至少每个盘子里都会放一个苹果还剩m-n个苹果放在n个盘子里f(m-n,n).

AC代码:

#include<bits/stdc++.h>
using namespace std;

int f(int x, int y) {
	if(x == 0) return 1;
	if(y == 0) return 0;
	if(x < y) return f(x, x);
	if(x >= y) return f(x, y - 1) + f(x - y, y);
}

int main() {
	int t, m, n;
	cin>>t;
	while(t--) {
		cin>>m>>n;
		int ans = f(m, n);
		cout<<ans<<endl;
	}
	return 0;
}