题目描述:
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。
Java实现:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int m = sc.nextInt();
int n = sc.nextInt();
if (m < 1 || m > 10 || n < 1 || n > 10)
System.out.println("-1");
System.out.println(count(m, n));
}
}
private static int count(int m, int n) {
if (m < 0) {
return 0;
} else if (m == 0 || m == 1 || n == 1) {
return 1;
} else {
return count(m, n-1) + count(m-n, n);
}
}
}
关键点:
怎样想得到递归操作呢?分为两种情况,所有盘子都放count(m-n, n),不是所有盘子都放,即至少有一个盘子不妨count(m, n-1)