最新消息:点击查看大S的省钱秘笈

POJ 1664 放苹果 C语言版

POJ题解 Slyar 102浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

Description

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

Input

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

Output

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

Sample Input

1
7 3

Sample Output

8

Slyar:今天DS课在讲栈,说实话栈操作没什么写的,栈用的最多的还是递归,于是中午就在POJ上找了一道比较简单的递归题,再次熟悉了一下递归过程。

这是一道排列组合题,可以列出递推式:

1、每个盘子至少放 1 个苹果,然后剩下的 m-n 个苹果随便放。
2、有 1 个盘子没有放苹果,这样 m 个苹果随便放入 n-1 个盘子中。

我们一般说有了递推式就可以使用递归来解题了,直接看代码。

转载请注明:Slyar Home » POJ 1664 放苹果 C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址