欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

递归训练-放苹果

程序员文章站 2024-03-17 18:15:28
...

 

问题 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 2018321下午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);

        }

    }

}