问题 C: 【基础】放苹果 【递归】
时间限制: 1 Sec 内存限制: 128 MB
提交: 345 解决: 193
[提交][状态][讨论版]
题目描述
描述
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。
输入
输入
第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。
输出
输出
对输入的每组数据M和N,用一行输出相应的K。
样例输入
1
7 3
样例输出
8
提示
[提交][状态]
思路分析:
这道题目不能说很难,具体分析过程是这样的:将m个苹果放在n个盘子上,首先应该想到的就是两种情况 ①.盘子的数量比苹果的数量多(n>m) ②.苹果的数量比盘子的数量多(m>=n)
对于第①种情况来分析的话呢,因为题目允许有空盘子不放,并且5,1,1和1,5,1是同一种分法。 那也就可以这样得出,多余放不到苹果的盘子怎么移动都不会改变放苹果的种类,既然如此,
我们就可以干脆把多余的盘子略去不考虑,既 n>m fn(m,n)=fn(m,m)
对于第②种情况来分析,当苹果的数量大于等于盘子的数量时(m>=n) ,应该想可以分成两种放法,第Ⅰ种是先把所有的盘子装满,再去放剩下的苹果,即fn(m,n)=fn(m-n,n) 第Ⅱ种是递归的去思考,要求m个苹果
放在n个盘子的方法,可以先求m个苹果在n-1个盘子上的放法,一层层往上求,直到只有1个盘子的情况返回1。
综上有,
fn(m,n)=fn(m,m) m<n
fn(m,n)=fn(m,n-1)+fn(m-n,n) m>=n
上代码:
package com.eangaie.main.m1;
import java.util.*;
/** * * @CreateTime 2018年3月21日下午8:01:20 * * @author谢彦杰 * * @since JDK 1.8 * * 文件名称:C.java * * 放苹果 * **/
public class C {
public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); int m, n, num; num = in.nextInt(); while (--num >= 0) { m = in.nextInt();// 苹果 n = in.nextInt();// 盘子 System.out.println(fn(m, n)); } }
static int fn(int m, int n) { if (m == 0 || n == 1) { return 1; } // 当盘子数量比苹果数量多 else if (n > m) { return fn(m, m); } else { return fn(m, n - 1) + fn(m - n, n); } } } |