我们 cnblogs new swa imp str 过程 输入
题目描述:
把 M 个同样的苹果放在 N 个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用 K 表示)5,1,1 和 1,5,1 是同一种分法。输入每个用例包含二个整数 M 和 N。0<=m<=10,1<=n<=10。<=n<=10<=m<=10 样例输入 7 3 样例输出 8
题目分析:
本题实际上是一个划分问题,借助于递归这个强大的工具,我们可以比较容易地进行解决,具体分析思路如下:
1,我们用 f(m, n) 来表示 m 个苹果,n 个篮子的情况;
2,出口条件:当 m <= 1 时 f(m, n) = 1, 当 n = 1 时 f(m, n) = 1;
3,当 n > m 时,无论怎么放置,总会有 (n - m) 个篮子为空,那么去掉这些篮子也不会对总的放置种类有什么影响,即 f(m, n) = f(m, m);
当 n <= m 时,又分为两种情况:
3-1,所有的篮子都不会为空,此时相当于每个篮子都至少会有一个苹果,那么去掉这些苹果,总的放置种类也不会改变,即即 f(m, n) = f(m - n, n);
3-2,至少有一个篮子不会为空,那么去掉这个篮子,总的放置种类也不会改变,即即 f(m, n) = f(m, m - 1);
那么总的放置种类数相加即可。
4,根据 3 中的分析,递归过程中 f(m, n) 参数 1 和参数 2 都会不断减小,一定会到达出口条件,符合递归的条件。
代码 (Java 实现):
- 1 import java.util.Scanner;
- 2 3 public class layApple {
- 4 public static void main(String[] args) {
- 5 int[] paras = getInput();
- 6 System.out.println(findNumsOfLaying(paras[0], paras[1]));
- 7
- }
- 8 public static int[] getInput() {
- 9@SuppressWarnings("resource") 10 Scanner reader = new Scanner(System. in );
- 11 int[] paras = new int[2];
- 12 paras[0] = reader.nextInt();
- 13 paras[1] = reader.nextInt();
- 14
- return paras;
- 15
- }
- 16 17 public static int findNumsOfLaying(int m, int n) {
- 18
- if (m == 0 || n == 1) {
- 19
- return 1;
- 20
- }
- 21
- if (n > m) {
- 22
- return findNumsOfLaying(m, m);
- 23
- } else {
- 24
- return findNumsOfLaying(m - n, n) + findNumsOfLaying(m, n - 1);
- 25
- }
- 26
- }
- 27
- }
华为 OJ 之放苹果
来源: http://www.bubuko.com/infodetail-2023888.html