数据结构（三）

学习数据结构与算法过程中的心得体会以及知识点的整理，方便我自己查找，也希望可以和大家一起交流。

—— 放苹果 ——

1.题目描述

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

1.1输入

第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

1.2输出

对输入的每组数据M和N，用一行输出相应的K。

1.3样例输入与输出

样例输入
1 7 3
样例输出
8

2.代码实现

#include 
   
    int methon(int apple,int plate){
   	//如果没有苹果或者只有一个盘子，那么就只有一种方法。	if(apple==0||plate==1)		return 1;    //如果苹果数量比盘子少，那么就相当于有苹果数量的盘子	if(apple

3.代码说明

首先我们解析问题，有apple个苹果要放入plate个盘子中，首先我们来分情况讨论：

1.当apple < plate的时候，我们不难发现，这个时候一定有盘子是空的，而且根据题目的描述，相同数量不同顺序算作一种，所以我们**即使把这个空的盘子去掉也不影响结果。**目的是将其转化为第2种状态。

即（apple=x，plate=y）=（apple=x，plate=x）

例如：3个苹果放入5个盘子里的放置方法和3个苹果放入4个盘子的结果是一样的，因为根据题意（0,0,0,1,2）和（0,0,1,0,2）算作同一个情况，所以（0,0,0,1,2）和（0,0,1,2）是相同的。同理，3个苹果放入5个盘子里的放置方法和3个苹果放入3个盘子的结果是一样的。

2.当apple >= plate的时候，这种时候我们又要分情况讨论：

2.1当有盘子中放0个苹果的时候，根据上面的道理，去掉一个放0个的盘子对结果没有影响。

即（apple=x，plate=y）=（apple=x，plate=y-1）

2.2 当盘子中都放有苹果时，我们即使在每个盘子中拿走一个苹果也不影响结果，目的是让其不断递归到2.1或者1的状态。

即（apple=x，plate=y）=（apple=x-y，plate=y）

而最后的结果就是2.1和2.2的值相加，

即（apple=x，plate=y）=（apple=x-y，plate=y）+（apple=x，plate=y-1）

将上述方法运用递归即可轻易实现，当然也可以使用动态规划，不过应该需要使用道二维数组，运算与循环步骤相对麻烦。

转载地址：http://nfazi.baihongyu.com/

你可能感兴趣的文章