首页 > 试题广场 >

放苹果

[编程题]放苹果
  • 热度指数：12131 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

输入描述:
每行均包含二个整数M和N，以空格分开。1<=M，N<=10。


输出描述:
对输入的每组数据M和N，用一行输出相应的K。
示例1

输入

7 3

输出

8
算法知识视频讲解
添加回答
Java
JXhacker头像 JXhacker 
    //该函数表示m个苹果放在n个盘子的方案数
    public static int putApple(int m, int n){
        //三个迭代退出条件
        if (n > m) return putApple(m, m);
        if (n == 1) return 1;
        if (m == 0) return 1;
        //动态规划核心：f(m,n)=f(m,n-1)+f(m-n,n);
        return putApple(m, n - 1) + putApple(m - n, n);
    }

发表于 2019-04-01 16:25:32 回复(0)
Java
七里十一头像 七里十一
import java.util.*;
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();
            System.out.println(apple(m,n));
        }
    }
   
    public static int apple(int m,int n){
        if(m==0||n==1) return 1;
        if(n>m) return apple(m,m);
        else
            return apple(m,n-1)+apple(m-n,n);
    }
}
发表于 2018-07-30 11:48:55 回复(0)
Java
哈士奇头像 哈士奇
import java.util.*;
public class Main{
    static int f(int m, int n){
       if(m<n) return 0;
      if(n==1) return 1;
      if(m==n) return 1;
    
      int counts = 0;
      for(int i = 1;i<=n;i++){
         
          counts+=f(m-n,i);
      }
      
      return counts;
  }

    public static void main(String args[]){
        Scanner ins = new Scanner(System.in);
        int k = ins.nextInt();
        while(k>0){
            int m = ins.nextInt();
            int n = ins.nextInt();
            int count = 0;
            for(int i = 1;i<=n;i++){
               count+=f(m,i);
            }
            k--;
            System.out.println(count);
            }
        }
  }

发表于 2016-08-14 17:20:12 回复(0)
Java
菜鸟葫芦娃头像 菜鸟葫芦娃
设dp(m,n) 为m个苹果，n个盘子的放法数目，则先对n作讨论，
        当n>m：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响。即if(n>m) dp(m,n) = dp(m,m)
        当n<=m：不同的放法可以分成两类：
        1、有至少一个盘子空着，即相当于f(m,n) = f(m,n-1);  
        2、所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即dp(m,n) = dp(m-n,n).
        而总的放苹果的放法数目等于两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n) 


import java.util.Scanner;

/*
 * 设dp(m,n) 为m个苹果，n个盘子的放法数目，则先对n作讨论，
        当n>m：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响。即if(n>m) dp(m,n) = dp(m,m)
        当n<=m：不同的放法可以分成两类：
        1、有至少一个盘子空着，即相当于f(m,n) = f(m,n-1);  
        2、所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即dp(m,n) = dp(m-n,n).
        而总的放苹果的放法数目等于两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n) 

 递归出口条件说明：
        当n=1时，所有苹果都必须放在一个盘子里，所以返回１；
        当没有苹果可放时，定义为１种放法；
        递归的两条路，第一条n会逐渐减少，终会到达出口n==1; 
        第二条m会逐渐减少，因为n>m时，我们会return f(m,m)　所以终会到达出口m==0．
 * 
 * 
 * 
 * */
public class Main {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int cnt = in.nextInt();
for (int i = 0; i < cnt; i++) {
int M = in.nextInt();
int N = in.nextInt();
System.out.println(processdp(M, N));
}
}
in.close();
}

private static int processPutApple(int m, int n) {
// TODO Auto-generated method stub
if (m == 0 || n == 1)
return 1;
if (n > m)
return processPutApple(m, m);
else
return processPutApple(m, n - 1) + processPutApple(m - n, n);
}

static int processdp(int m, int n) {
int[][] dp = new int[m + 1][n + 1];//m个苹果放进n个盘子的最大值
for (int i = 0; i <= m; i++) {
dp[i][1] = 1; //m个苹果放进一个盘子 1种方法
}
for (int i = 0; i <= n; i++) {
dp[0][i] = 1; //0个苹果放进n个盘子 1种方法
}
for (int i = 1; i <= m; i++) {
for (int j =1; j <= n; j++) {
if (j <= i)//苹果比盘子多的情况下
dp[i][j] = dp[i][j - 1] + dp[i - j][j];
else //盘子多,苹果少 必然有空盘子
dp[i][j] = dp[i][i];
}
}
return dp[m][n];
}
}

发表于 2016-07-21 15:10:46 回复(5)
提交观点

问题信息

动态规划
难度：
4条回答 10137浏览

热门推荐

通过挑战的用户

查看代码

相关试题

放苹果

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号