首页 > 试题广场 >

放苹果

[编程题]放苹果
  • 热度指数:149224 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
把m个同样的苹果放在n个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?
注意:如果有7个苹果和3个盘子,(5,1,1)和(1,5,1)被视为是同一种分法。

数据范围:



输入描述:

输入两个int整数



输出描述:

输出结果,int型

示例1

输入

7 3

输出

8
import java.util.*;
public class Main {
    public static int place(int n, int m, int f) {
        int total = 0;
        if (n > 0 && n < f) return 0;
        if (n == 0) return 1;
        if (m == 1) return 1;
        for (int i = f; i <= n; i++) {
            total += place(n-i, m-1, i);
        }
        return total;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            System.out.println(place(n, m, 1));
        }
        sc.close();
        return;
    }
}
发表于 2020-07-21 21:51:05 回复(1)
//下一个盘子放入的苹果不少于前一次放入的苹果,当最后一个盘子可以放入的苹果比前一个多时,
//则是一次正确的放置方法。由于递归的条件,所以当盘子数多余苹果的数目时,盘子数赋值为苹果数, //因为3个苹果放入3个盘子和比3多的盘子情况是一样的
#include<iostream>
using namespace std;

int f(int apple_num,int dish_num,int min_apple)
{
    int result = 0;

    if(apple_num >= min_apple && dish_num==1)
        return 1;

    if((apple_num == 0 && dish_num !=1) || (apple_num != 0 && dish_num ==1) || apple_num<min_apple)
        return 0;

    for(int i=min_apple;i<apple_num;i++)
    {
        result += f(apple_num-i,dish_num-1,i);
    }
    return result;

}

int main()
{
    int apple_num,dish_num;
    while(~scanf("%d %d",&apple_num,&dish_num))
    {
        if(dish_num>apple_num)
            dish_num = apple_num;
        
        cout<<f(apple_num,dish_num,0)<<endl;
    }
    return 0;
}


发表于 2017-09-14 17:01:01 回复(1)
using System;
class test{
    static void Main()
    {
        string input="";
        while((input=Console.ReadLine())!=null)
        {
            string[] str=input.Split(" ");
            int m=int.Parse(str[0]);
            int n=int.Parse(str[1]);
            int result=0;
            result=fenApple(m, n);
            Console.WriteLine(result);
        }
    }
    static int fenApple(int m,int n)
    {
        if(m<0||n<0)
            return 0;
        else if(m==1||n==1)
            return 1;
        else
            return fenApple(m,n-1)+fenApple(m-n, n);
    }
}
发表于 2022-06-25 18:25:47 回复(0)
#include <stdio.h>
#include <string.h>
 
int f(int m, int n);
 int main()
{
    int m, n;
     while (scanf("%d %d", &m, &n) != EOF)
    {
        printf("%d\n", f(m, n));
    }
 
    return 0;
}
 
int f(int m, int n)
{
    int ret;
    if (n == 1)
    {
        ret = 1; //m个果放1个盘子 1种
    }
    else if (m == 0)
    {
        ret = 1; //0个果放n个盘子 1种
    }
    else if (m < n)
    {
        ret = f(m,m); 
        //当m<n:必定有n-m个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响,
        //即if(n>m) f(m,n) = f(m,m) 问题变成m个苹果,m个盘子的问题。即下面的m>=n的情况.
    }
    else if (m >= n)
    {
        ret = f(m - n, n) + f(m, n - 1); 
        //1.至少有一个空盘f(m,n) = f(m,n-1);
        //2.一个空盘都没有f(m,n) = f(m-n,n);(即如果所有盘子都有苹果,相当于可以从每个盘子中拿掉一个苹果,不影响不同放法的数目.
        //分析则有,总的放苹果的放法数目等于1、2两者的和,即 f(m,n) =f(m,n-1)+f(m-n,n))
    }
 
    return ret;
}

发表于 2022-03-30 16:06:54 回复(0)

使用动态规划,设 表示有个苹果,个盘子的情况下,有多少种可能,我们可以知道总共有至多两种情况,个盘子装满和没装满,那么由于所有的苹果和盘子都是相同的,所以在盘子装满的情况下,其等于,而在没装满的情况下,至少有一个盘子没满,那么就是,因此:
状态转移方程为:

#include<iostream>

using namespace std;

int main(){

    int m,n;
    while(cin >>m && cin >> n){
        int dp[m+1][n+1];
        for(int j = 0; j <= n;j++){
            dp[0][j] = 1;
        }
        for(int i = 0; i <= m; i++){
            dp[i][0] = 0;
        }
        for(int i = 1; i<= m;i++){
            for(int j = 1; j<=n; j++){
                dp[i][j] = dp[i][j-1];
                if(i-j >= 0){
                    dp[i][j] += dp[i-j][j];
                }
            }
        }
        cout<< dp[m][n]<<endl;
    }
    return 0;
}
发表于 2021-09-01 06:00:44 回复(0)
/*C++动态规划做法*/
//有点像背包问题
//将最终答案看成一个集合,找到这个集合的划分方法
#include <iostream>
using namespace std;
int dp[20][20];
 int main()
 {
     int m,n;

     while(cin>>m>>n)
     {
         for(int i=0;i<=m;i++)
         {
             for(int j=1;j<=n;j++)
             {
                 if(i==0||i==1||j==1)
                     dp[i][j]=1;
                 else if(i>=j) dp[i][j]=dp[i-j][j]+dp[i][j-1];
                 else dp[i][j]=dp[i][j-1];
             }
         }
         cout<<dp[m][n]<<endl;
     }
     return 0;
 }

发表于 2021-07-20 23:06:38 回复(0)
二维数组解法
s=[[0 for i in range(11)]for j in range(11)]
for i in range(1,11):
    for j in range(1,11):
        if i==j:s[i][j]=s[i][j-1]+1
        elif j>i:s[i][j]=s[i][i]
        else:s[i][j]=s[i-j][j]+s[i][j-1]
while True:
    try:
        a,b=map(int, input().split())
        print(s[a][b])
    except:
        break

编辑于 2021-06-26 12:49:48 回复(1)
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 < 0 || m > 10 || n < 1 || n > 10){
                System.out.println(-1);
            }
            
            //创建二维数组保存状态
            int[][] dp = new int[m+1][n+1];
            for(int i = 0; i <= m; i++){
                dp[i][0] = dp[i][1] = 1;
            }
            
            for(int j = 2; j <= n; j++){
                for(int i = 0; i <= m; i++){
                    if(i < j){
                        dp[i][j] = dp[i][j-1];
                    } else {
                        dp[i][j] = dp[i][j-1] + dp[i-j][j];
                    }
                }
            }
            
            System.out.println(dp[m][n]);
        }
    }
}

发表于 2020-08-16 19:01:34 回复(0)
#include <bits/stdc++.h>
using namespace std;
int func(int m,int n)  
{
    if(m==0||n==1) 
        return 1;    
    if(n>m)
        return func(m,m);
    else
        return func(m,n-1)+func(m-n,n);
}
 
int main(){
    int m, n;
    while (cin >> m >> n){
        cout << func(m, n) << endl;
    }
    return 0;
}

发表于 2020-07-18 14:05:50 回复(0)
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        while(in.hasNext()){
        int m=in.nextInt();
        int n=in.nextInt();
        if(m<1||m>10||n<1||n>10)
            System.out.println(-1);
        else
            System.out.println(count(m,n));
        }
        in.close();
    }
    public static int count(int m,int n){
        //当苹果或盘子数目为1时,显然只有1种情况;
        //而这也是函数出口,m,n回溯到1结束,再小则没有意义
        if(m==1||n==1) return 1;
        
        //当n>m:必定有n-m个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响;
        //舍去多余盘子,从m<=n的情况考虑是等价的
        if(m<n)    
            return count(m,m);
        
        //对应情况m>=n,不同的放法可以分成两类:
        //1.至少一个盘子空着,(m,n)问题转换为(m,n-1)问题;
        //2.不存在空盘子,每个盘子上至少有1个苹果,最多剩下m-n个苹果;
        //相当于把m-n个苹果放到n个盘子有几种方法,即(m,n)转换为(m-n,n)
        
        if(m==n)
            //在盘子等于苹果时,考虑情况2.没有空盘时,每个盘子刚好放一个苹果,只有1种情况
            return count(m,n-1)+1;
            
        else
            return count(m,n-1)+count(m-n,n);
    }
}

发表于 2020-07-08 19:35:43 回复(0)
import sys

def func1(m,n):
    dp=[[0 for x in range(m+3)] for y in range(n)]
    for i in range(1,m+3):
        dp[0][i]=1
    for i in range(n):
            dp[i][2]=1
    for i in range(1,n):
        for j in range(3,m+3):
            dp[i][j]=dp[i-1][j]+dp[i][j-i-1]
    return dp[-1][-1]

while True:
    a = sys.stdin.readline().strip()
    if a == "":
        break
    a_=a.split(" ")
    m=int(a_[0])
    n=int(a_[1])
    #m<n时,肯定有至少n-m个盘子是空的,对结果不产生影响,应当除去
    if m>=n:
        print(func1(m,n))
    else:
        print(func1(m,m))
动态规划,思路跟递归差不多,不过要注意把空盘子拿掉。
发表于 2020-04-08 17:10:44 回复(0)
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int m=sc.nextInt();
            int n=sc.nextInt();
            System.out.println(cal(m,n));
        }
    }
    
    public static int cal(int m,int n){
        int c=0;
        if(n==1){
            return 1;
        }
        for(int i=1;i<=n;i++){
            if(m<=i){
               c+=1;
               break;
            }else{
                c+=cal(m-i,i);
            }
        }
        return c;
    }
}

发表于 2020-03-03 17:07:20 回复(1)
#include <bits/stdc++.h>
using namespace std;
int fun(int n,int m)
{
    if(n==0 || m==1) return 1;
    if(n<m) return fun(n,n);
    else return (fun(n,m-1)+fun(n-m,m));
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n<0 || n>10 || m<1 || m>10) continue;
        cout<<fun(n,m)<<endl;
    }
    return 0;
}

发表于 2018-08-20 11:55:57 回复(0)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>

using namespace std;

int f(int m,int n)
{     if(m==0 || n==1)         return 1;     if(n>m)         return f(m,m);     else         return f(m,n-1) + f(m-n,n);          }
int main()
{     int n,m;     while(cin>>m>>n)      {         if(m<0 || m>10 || n<0 || n>10)             continue;         cout<<f(m,n)<<endl;     }     return 0;
}

发表于 2018-05-27 01:42:53 回复(0)
package interview;
import java.util.Scanner;
//n个相同的苹果 放在 m个相同的盘子里
/** f(n,m)
 * 如果没有空盘子f(n-m,m)
 * 如果有空盘子 f(n,m-1)
 * f(n,m)=f(n-m,m)+f(n,m-1)
 */
public class Main{   
   public static int deal(int n,int m){//n苹果 m盘子
       if(n<0)return 0;
       if(n==0||m==1)return 1;
       return deal(n,m-1)+deal(n-m,m);
   }
   public static void main(String args[]){
       Scanner sc=new Scanner(System.in);
       while(sc.hasNext()){
           int n=sc.nextInt();
           int m=sc.nextInt();
           int res=deal(n,m);
           System.out.println(res);
       }
   }
}

发表于 2017-03-21 21:00:43 回复(0)
NWU头像 NWU
/*
放苹果分为两种情况,一种是有盘子为空,一种是每个盘子上都有苹果。
令(m,n)表示将m个苹果放入n个盘子中的摆放方法总数。
1.假设有一个盘子为空,则(m,n)问题转化为将m个苹果放在n-1个盘子上,即求得(m,n-1)即可
2.假设所有盘子都装有苹果,则每个盘子上至少有一个苹果,即最多剩下m-n个苹果,问题转化为将m-n个苹果放到n个盘子上
即求(m-n,n)

综上所述:
(m,n)=(m,n-1)+(m-n,n);
*/

#include <iostream> 
using namespace std; 

int putapples(int m,int n) 
if(m<0)
return 0;
if(m==1||n==1) 
return 1; 
return putapples(m,n-1)+putapples(m-n,n); 

int main() 
int m,n; 
while(cin>>m>>n)
cout<<putapples(m,n)<<endl;
return 0; 
发表于 2016-02-20 16:05:03 回复(35)
枚举:
#include <iostream>

using namespace std;
int main()
{
int appleNum;
int basketNum;
    while(cin >> appleNum >> basketNum){
    
if (appleNum == 0) { cout << 0 << endl;  }
else if (appleNum == 1) { cout << 1 << endl; }
else if (basketNum == 1) { cout << 1 << endl;  }
    
else if (appleNum == 2) { cout << 2 << endl; }
else if (appleNum == 3 && basketNum == 2) { cout << 2 << endl;  }
else if (appleNum == 3 && basketNum > 2) { cout << 3 << endl;  }
else if (appleNum == 4 && basketNum == 2) { cout <<3 << endl;}
else if (appleNum == 4 && basketNum == 3) { cout << 4 << endl;  }
else if (appleNum == 4 && basketNum > 3) { cout << 5 << endl; }
else if (appleNum == 5 && basketNum == 2) { cout << 3 << endl;  }
else if (appleNum == 5 && basketNum == 3) { cout << 5<< endl;  }
else if (appleNum == 5 && basketNum == 4) { cout << 6 << endl;  }
else if (appleNum == 5 && basketNum > 4) { cout << 7 << endl;  }
else if (appleNum == 6 && basketNum == 2) { cout << 4 << endl;  }
else if (appleNum == 6 && basketNum == 3) { cout << 7 << endl;  }
else if (appleNum == 6 && basketNum == 4) { cout << 9 << endl;  }
else if (appleNum == 6 && basketNum == 5) { cout << 10 << endl; }
else if (appleNum == 6 && basketNum > 5) { cout << 11 << endl;  }
else if (appleNum == 7 && basketNum == 2) { cout << 4 << endl;  }
else if (appleNum == 7 && basketNum == 3) { cout << 8 << endl;  }
else if (appleNum == 7 && basketNum == 4) { cout << 11 << endl;  }
else if (appleNum == 7 && basketNum == 5) { cout << 13 << endl;  }
else if (appleNum == 7 && basketNum == 6) { cout << 14 << endl;  }
else if (appleNum == 7 && basketNum > 6) { cout << 15 << endl;  }
else if (appleNum == 8 && basketNum == 2) { cout << 5 << endl;  }
else if (appleNum == 8 && basketNum == 3) { cout << 10 << endl;  }
else if (appleNum == 8 && basketNum == 4) { cout << 15 << endl;  }
else if (appleNum == 8 && basketNum == 5) { cout << 18 << endl;  }
else if (appleNum == 8 && basketNum == 6) { cout << 20 << endl;  }
else if (appleNum == 8 && basketNum == 7) { cout << 21 << endl;  }
else if (appleNum == 8 && basketNum >  7) { cout << 22 << endl;  }
else if (appleNum == 9 && basketNum == 2) { cout <<5 << endl;  }
else if (appleNum == 9 && basketNum == 3) { cout << 12 << endl;  }
else if (appleNum == 9 && basketNum == 4) { cout << 18 << endl;  }
else if (appleNum == 9 && basketNum == 5) { cout << 23 << endl; }
else if (appleNum == 9&& basketNum == 6) { cout << 26 << endl;  }
else if (appleNum == 9 && basketNum == 7) { cout << 28 << endl;  }
else if (appleNum == 9 && basketNum == 8) { cout << 29 << endl; }
else if (appleNum == 9 && basketNum >  8) { cout << 30 << endl;  }
else if (appleNum == 10 && basketNum == 2) { cout << 6 << endl;  }
else if (appleNum == 10 && basketNum == 3) { cout <<13 << endl; }
else if (appleNum == 10 && basketNum == 4) { cout << 20 << endl;  }
else if (appleNum == 10 && basketNum == 5) { cout << 25 << endl;  }
else if (appleNum == 10 && basketNum == 6) { cout << 29 << endl;  }
else if (appleNum == 10 && basketNum == 7) { cout << 32 << endl;  }
else if (appleNum == 10 && basketNum == 8) { cout << 34 << endl; }
else if (appleNum == 10 && basketNum == 9) { cout << 41 << endl;  }
else if (appleNum == 10 && basketNum > 9) { cout << 42 << endl;  }
    }
    return 0;
}
发表于 2016-05-27 22:02:59 回复(92)
#include <iostream>

using namespace std;

/*  解题分析:
        设f(m,n) 为m个苹果,n个盘子的放法数目,则先对n作讨论,
        当n>m:必定有n-m个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响。即if(n>m) f(m,n) = f(m,m)  
        当n<=m:不同的放法可以分成两类:
        1、有至少一个盘子空着,即相当于f(m,n) = f(m,n-1);  
        2、所有盘子都有苹果,相当于可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,即f(m,n) = f(m-n,n).
        而总的放苹果的放法数目等于两者的和,即 f(m,n) =f(m,n-1)+f(m-n,n) 
    递归出口条件说明:
        当n=1时,所有苹果都必须放在一个盘子里,所以返回1;
        当没有苹果可放时,定义为1种放法;
        递归的两条路,第一条n会逐渐减少,终会到达出口n==1; 
        第二条m会逐渐减少,因为n>m时,我们会return f(m,m) 所以终会到达出口m==0.
*/

int func(int m,int n)  //m个苹果放在n个盘子敏感词有几种方法
{
	if(m==0||n==1)  //因为我们总是让m>=n来求解的,所以m-n>=0,所以让m=0时候结束,如果改为m=1,
		return 1;    //则可能出现m-n=0的情况从而不能得到正确解    
	if(n>m)
		return func(m,m);
	else
		return func(m,n-1)+func(m-n,n);
}

int main(){
    int m, n;
    while (cin >> m >> n){
        if (m < 0 || m > 10 || n < 0 || n > 10) continue;
        cout << func(m, n) << endl;
    }
    return 0;
}


发表于 2016-09-11 11:25:56 回复(18)
递推的方式,利用公式f(m, n)=f(m, n-1)+f(m-n, n)来填表。

将m个苹果放入n个盘子里,包含了2个事件:至少有一个盘子空着的事件A,和所有盘子都不空的事件B(每个盘子都至少有一个苹果)。A∪B即所有情况。A就是求f(m, n-1),B就是f(m-n, n)。事件B表示每个盘子都有一个苹果时再放m-n个苹果,等价于每个盘子都没有苹果时放m-n个苹果,所以可以直接写成 f(m-n, n)。注意m-n可能为负数,此时要返回0。

例如,f(4,4)=f(4,3)+f(0,4),f(0,4)等于1,表示在4个盘子中各放1个苹果

while True:
    try:
        m, n = map(int, input().split())
    except:
        break
    else:
        a = [[0 for i in range(n+1)] for j in range(m+1)]
        for i in range(m+1):
            for j in range(1,n+1):
                if i == 0 or i== 1 or j == 1:
                    a[i][j] = 1
                elif i-j >= 0:
                    a[i][j] = a[i][j-1] + a[i-j][j]
                else:
                    a[i][j] = a[i][j-1]
        print(a[m][n])

发表于 2021-08-21 14:56:30 回复(0)
/*其实这题考的是数学啊,首先当有0个苹果或者是1个盘子的时候,只有一种分法,而其他情况
可以分为两种情况讨论:
   1、m<n,则至少有n-m个盘子是空的,此时就相当于将m个苹果分到m个盘子中,此时(m,n)=(m,m)
   2、m > n,分法是两种情况分法的和,有一个空盘子和没有空盘子,即(m,n) = (m,n-1)+(m-n,n)
*/
def putApple(m,n):
    if m == 0 or n == 1:
        return 1
    if n > m:
        return putApple(m,m)
    else:
        return putApple(m,n-1) + putApple(m-n,n)
        
        
while True:
    try:
        n, m = map(int,input().split())
        print(putApple(n, m))
    except:
        break

发表于 2018-08-31 22:57:47 回复(5)