openjudge-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

样例输出

这个题目采用递归解决，我们首先对于问题分析一下，如果盘子的数目大于苹果的数目，那肯定要有一些盘子是什么也不放的。

所以还剩下 n-m 个盘子，其余的盘子都是一样的，所以不做处理。

然后对问题进行分类，要么就有盘子不放苹果，要么就在每个盘子上面全放上苹果。

对于这两种情况：不放苹果的话就 return f（m，n-1），然后这个递归就会从盘子数目从1到n-1递归求解有多少种方案数。

这个过程实际上是先求当前的有的不放 + 所有都放的情况，然后要求这个就要先求之前的有的不放 + 所有都放的数目，直到回到递归的边界条件得到一个确定的值，这时候边界的值就知道了，是一个确定的数，那上一层的递归就也可以通过一个确定的数相加得到确定的值，假设上一层是有两个递归的的，，一个有的不放，一个所有都放。所以最底层的边界就要有四个值，每个递归两个。其实这样的话，这一层就已经相当于是最顶层了，这就是要求的结果了，因为，每次递归下去都是二层递归，所以当递归数目为2的时候，就是最顶层了。

至于所有都放，自己体会一下。

说完了问题的分类，就该说递归的终止了，因为题目允许盘子不放入苹果，所以，当苹果数目为零，但是盘子数目不为零的时候，他的方案数就为 1 。

但是当盘子的数目为零的时候，就没有方案数了，就是零。

注意递归的求解就是一定要有边界条件。

#include <iostream>

using namespace std;

int f(int m,int n)

{

	if (n>m)

		return f(m,m);

	if (m==0)

		return 1;

	if (n==0)

		return 0;

	return f(m,n-1)+f(m-n,n);

 }

int main()

{

	int t;

	int m,n;

	cin>>t;

	while (t--) {

		cin>>m>>n;

		cout<<f(m,n)<<endl;

	}

	return 0;

}

巴特西

openjudge-1664 放苹果

最新文章

热门文章