KY61 放苹果（用Java实现）

描述

把 M 个同样的苹果放在 N 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
注意：5、1、1 和 1、5、1 是同一种分法，即顺序无关。

输入描述：

输入包含多组数据。

每组数据包含两个正整数 m和n（1≤m, n≤20）。

输出描述：

对应每组数据，输出一个整数k，表示有k种不同的分法。

示例1

输入：

7 3

输出：

8

代码如下：

import java.util.Scanner;/** 放苹果：把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？* 		（用K表示）5，1，1和1，5，1 是同一种分法。* 递归求解：* 	边界情况是，苹果数量为1，或盘子数量为1，或苹果数量为0* 	当苹果数量m>=盘子数量n时有两种可能：* 		有一个盘子空出：* 		没有盘子空出：* 	当苹果数量m<盘子数量n时：* 		有盘子空出*/
public class PutApple {public class PutApple {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()) {int m = scanner.nextInt();	//苹果的数量int n = scanner.nextInt();	//盘子的数量System.out.println(putApple(m, n));}}public static int putApple(int m,int n) {if (m == 0||m == 1||n == 1) {	//判断边界//苹果个数为0时，只有一种情况//苹果个数为1时，只有一种情况//只有一个盘子时，只有一种情况return 1;}else if (m>=n) {	//苹果的数量 >= 盘子的数量//1、有一个盘子为空时，问题就转化成了将m个苹果放在n-1个盘子问题//2、盘子都不为空，问题就转化成将m-n个苹果放在n个盘子上return putApple(m, n-1)+putApple(m-n, n);}else if (m<n) {	//苹果的数量 < 小于盘子的数量//1、有一个盘子为空时，问题就转化成了将m个苹果放在n-1个盘子问题return putApple(m, n-1);}return -1;}
}}