首页 > 试题广场 > 放苹果
[编程题]放苹果
  • 热度指数:65957 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

题目描述

把m个同样的苹果放在n个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。

数据范围:0<=m<=10,1<=n<=10。

本题含有多组样例输入。



输入描述:

输入两个int整数



输出描述:

输出结果,int型

示例1

输入

7 3

输出

8
#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)
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 回复(34)
枚举:
#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 回复(84)
/*其实这题考的是数学啊,首先当有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)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
	int M, N;
	while (cin >> M >> N) {
		if (M < 1 || M>10 || N < 1 || N>10) {
			cout << -1 << endl;
			continue;
		}
		vector<vector<int>> dp(M + 1, vector<int>(N + 1, 0));
		for (int i = 1; i <= N; i++) dp[0][i] = 1;
		for (int i = 1; i <= M; i++)
			for (int j = 1; j <= N; j++)
				dp[i][j] = dp[i][j - 1] + (i < j ? 0 : dp[i - j][j]);
		cout << dp[M][N] << endl;
	}
}

发表于 2017-03-17 22:43:56 回复(3)
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();
            if(m<1 || n>10){
                System.out.println(-1);
            }else{
                System.out.println(shareCount(m,n));
            }
            
        }
    }
    public static int shareCount(int m, int n){
        if(m<0){
            return 0;
        }
        if(m==1 || n==1){
            return 1;
        }
        return shareCount(m, n-1)+shareCount(m-n,n);
    }
}

发表于 2016-09-02 21:05:45 回复(2)
递归思想:f(m,n)可以分成两种情况:
1.有一个盘子是空的(这里为什么要说是一个盘子而不是至少一个呢?因为至少一个已经包含在内了,递归实现),此时为f(m,n-1);
2.没有空盘子,此时每个盘子至少有一个苹果,则为f(m-n,n);
已知条件:
1.苹果数量小于0放置方式为0;
2.苹果数量为0/1或者盘子数量为1时放置方式为1;(之前我也是觉得m=0时应该是为0,后来想了想,如果是m(2,2)的话结果应该为2,而m(2,2)=m(2,1)+m(0,2),前者值为1,后者如果为0的话就不正确了,所以当m为0的时候应该是为1的)
3.其余情况使用递归
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();
            System.out.println(count(m,n));
        }
        in.close();
	}
	
	public static int count(int m,int n){
		
		if(m<0)
			return 0;
		if(m == 0 || n == 1)
			return 1;
		return count(m,n-1)+count(m-n,n);
	}
} 
对了,这里还要注意一下,测试用例不止一条,有多条,所以一定要使用in.hasNext()进行while循环,否则结果报错,郁闷得很,使用BufferedReader不知道如何无限输入,如果使用while(true)就跳不出了
发表于 2017-09-14 11:10:19 回复(2)
/*
思路:对于将M个苹果放在N个盘子里,可以分为如下几种情况:
1.N个盘子中都有苹果
2.N个盘子中至少有1个盘子没有苹果
f(m,n)=f(m,n-1)+f(m-n,n);
若N大于M,则肯定有空盘子,不妨把这些空盘子放在一边。转换成求解f(m,m)的问题

*/
#include<iostream>
using namespace std;
int f(int m,int n)
{
    if(m==0 || n==1)
        return 1;
    if(m<n)
        return f(m,m);
    return f(m,n-1)+f(m-n,n);
}
int main()
{
    int m,n;
    while(cin>>m>>n)
        cout<<f(m,n)<<endl;
    return 0;
}

发表于 2017-05-03 20:00:33 回复(2)
/*应用动态规划*/
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int num_apple = sc.nextInt();
			int num_panzi = sc.nextInt();
			calculate(num_apple,num_panzi);

		}
	}
	public static void calculate(int a,int b){
		int[][] count = new int[a+1][b+1];
		for(int i=0;i<=a;i++){
			count[i][1]=1;
			count[i][0]=1;
		}
		for(int j=0;j<=b;j++){
			count[1][j]=1;
			count[0][j]=1;
		}
		for(int i=2;i<=a;i++){
			for(int j=2;j<=b;j++){
				if(i>=j){
					count[i][j] = count[i-j][j]+count[i][j-1];
				}else{
					count[i][j]=count[i][j-1];
				}

			}
		}
		System.out.println(count[a][b]);
	}

}


发表于 2017-04-03 21:02:29 回复(1)
#  解题分析:
#        设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.
#

def putApple(m,n):
    if m==0 or n==1:
        return 1
    elif 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
发表于 2020-07-14 08:55:17 回复(0)
#include <iostream>
using namespace std;

// 排列组合问题
// 当盘子数N小于M时
// 1 一个盘子放完 1种
// 2.2个盘子放 C(m-1,2-1)...
// 2.3个盘子放 C(m-1,3-1)...可怎么去掉重复的结果呢,
// 忘记了,所以用动态规划吧
// dp[m][n] 

//n个相同的苹果 放在 m个相同的盘子里 
  /** f(n,m) 
   * 如果没有空盘子f(n-m,m) 
   * 如果有空盘子 f(n,m-1) 
   * f(n,m)=f(n-m,m)+f(n,m-1) 
   */
int count(int m, int n)
{
    if(m <= 0 || n > 10)
        return -1;
    if(m < n)
        n = m;
    int **dp = new int*[m+1];
	for(int i = 0; i < m+1; i++)
		dp[i] = new int [n+1]();
    for(int i = 0; i < m+1; i++)
    {
        dp[i][1] = 1;  // 把i个苹果放进1个盘子
    }
    for(int j = 0; j < n+1; j++)
    {
        dp[0][j] = 1;   // 把0个苹果放进盘子
    }
    for(int i = 1; i < m+1; i++)  //m代表苹果数
        for(int j = 2; j < n+1; j++)
        {
            if(i-j >= 0)
                // 至少有一个空盘子 + 没有空盘子,
                // 没有空盘子,把苹果先给每个盘子放一个,
                // 重要的是当i = j时有1种方法(所以初始化dp[0][j] = 1),小于没有,大于。。
                dp[i][j] = dp[i][j-1] + dp[i-j][j];   
          
            else
                dp[i][j] = dp[i][j-1];
        }
    int res = dp[m][n];
	for(int i = 0; i < m+1; i++)
		delete [] dp[i];
	delete [] dp;
	dp = nullptr;
    return res;
}

int main()
{
    int m,n;
    while(cin >> m >> n)
    {
        cout << count(m,n) << endl;
    }
	//system("pause");
}

发表于 2017-07-12 08:36:38 回复(1)
#~万物皆可递归~
这题重点在于需要去重
int count;
void divide(int restPlate,int restAplle,int lastDivide){
    if (restPlate==0 && restAplle==0)
        count++;
    else if (restPlate<0)
        return;
    for (int d=lastDivide; d>=0; d--) { //通过每次分配不允许超过上个盘子分配个数去重
        if (restAplle>=d) {
            divide(restPlate-1, restAplle-d, d);
        }
    }
}
 
int main(){
    void divide(int ,int ,int );
    int m,n;
    while (~scanf("%d %d",&m,&n)) {
        count=0;
        divide(n, m, m);
        printf("%d\n",count);
    }
    return 0;
}

发表于 2020-05-18 18:17:41 回复(1)
import java.util.Scanner;

public class Main
{
    public static int fun(int m, int n)
    {
        if (n == 1 || m == 0)
        {
            //当只有一个盘子或没有苹果时,定义为一种方式
            return 1;
        }
        if (n > m)
        {
            //盘子数大于苹果数
            //必然有空的盘子,把空的盘子去掉后放法数目不变
            return fun(m, m);
        }
        else
        {
            //可能有一个盘子空着(拿走,总的放法数目不变),或者都不空(都不空就每个盘子拿走一个苹果,这样放法数目不变)
            return fun(m, n-1) + fun(m-n, n);
        }
    }

    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(fun(m, n));
            //设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.
        }
    }
}
发表于 2020-03-03 13:44:14 回复(1)
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)
def count(m,n):#m为多少个苹果,n为多少个盘子
    #1. 盘子多,苹果少,即n>m,count(m,n)=count(m,m)
    #2. 盘子少,苹果多,即n<=m,又分两种情况:
    #  (1)有至少一个空盘子:count(m,n)=count(m,n-1)
    #  (2)没有空盘子:count(m,n)=count(m-n,n)
    if m==0 or n==1:
        return 1
    if n>m:
        return count(m,m)
    else:
        return count(m,n-1)+count(m-n,n)
        
while True:
    try:
        l=input().split()#['7','3']
        m=int(l[0])
        n=int(l[1])
        print(count(m,n))
    except:
        break


编辑于 2020-02-18 16:36:08 回复(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)
递归求解,记苹果数为m,盘子数为n,则有以下几种情况:
(1) 没有苹果:只有空盘一种解法;
(2) 只有一个盘子:只有将所有苹果都放在这个盘子一种解法;
(3) 苹果比盘子少:相当于将m个苹果放到m个盘子中,进行递归;
(4) 苹果比盘子多,有以下两种情况,解法为下面两种情况的和:
    i) 至少有一个空盘,相当于将m个苹果放入n-1个盘子中,进行递归;
    ii) 每个盘子都有苹果,相当于n个盘子每个盘子先有一个苹果,然后剩下的m-n个苹果放入n个盘子中, 进行递归。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null) {
            int m = Integer.parseInt(line.trim().split(" ")[0]);
            int n = Integer.parseInt(line.trim().split(" ")[1]);
            System.out.println(recur(m, n));
        }
    }
    
    private static int recur(int m, int n) {
        if(m == 0 || n == 1){
            return 1;               // 没有苹果的时候只有空盘一种解法,只有一个盘子时只有所有苹果都放这个盘子一种解法
        }else if(m < n){
            return recur(m, m);     // 苹果比盘子少,则表示m个苹果放m个盘子
        }else{
            // 至少有一个空盘+每个盘子都放了苹果
            return recur(m, n - 1) + recur(m - n, n);
        }
    }
}

编辑于 2021-04-01 12:53:25 回复(0)

法1:采用递归做法
其实这根将一个整数m分成n个整数之和是类似的。

设f[m][n]为将m分成最多n份的方案数,且其中的方案不重复,即每个方案前一个份的值一定不会比后面的大,序列是一个不降序列
当m>=n时f[m][n] = f[m][n - 1] + f[m - n][n]
f[m][n - 1]相当于第一盘子中为0,有空盘子,只用将数分成n - 1份即可。因为0不会大于任何数,相当于f[m][n - 1]中的方案前面加一个为0的盘子。
f[m - n][n]相当于在每个盘子中加一个数1,没有空盘子。因为每个盘子中加一个数1不会影响f[m][n - 1]中的方案的可行性,也不会影响f的定义。所以f[m - n][n]一定是f[m][n]的方案的一部分,即不含有0的方案数。

当m<n的时候,肯定最少有n-m个空盘子,不过幸好,这些空盘子并不影响最后的结果,因为每种方法都带有着些空盘子,剩下的问题就是把m个苹果放到m个盘子有多少种方法了。f[m][n]=f[m][m)] m<n

临界条件,递归出口要定义好
n=1时,所有苹果都放在同一个盘子里 f(m,n)=1
m<=1时,没有苹果,f(m,n)=1

public int fun(int m,int n){
    if(m<=1 || n==1){
        return 1;
    }else if(m<n){
        return fun(m,m);
    }else{
        return fun(m,n-1)+fun(m-n,n);
    }
}

法2:动态规划
当数据规模较大时,递归的方式效率很低。使用动态规划,个人认为重点在于找对状态转移方程。
f[m][n] = f[m][n - 1] + f[m - n][n];
= 1 // m<= 1 || n <= 1

public int fun(int m,int n){
    int[][] arr = new int[m+1][n+1];
    for(int i = 0; i <= m; i++){
        for(int j = 0;j<=n;j++){
            if(i<=1 || j==1){
                arr[i][j] = 1;
            }else if(i<j){
                arr[i][j] = arr[i][i];
            }else{
                arr[i][j] = arr[i][j-1]+arr[i-j][j];
            }
        }
    }
    return arr[m][n];
}
编辑于 2021-01-26 13:22:56 回复(0)
Java:
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(), n = in.nextInt();
            int[][] a = new int[m+1][n+1];
            for (int i = 1; i <= n; i++) a[0][i] = 1;
            for (int i = 1; i <= m; i++)
                for (int j = 1; j <= n; j++)
                    a[i][j] = a[i][j - 1] + (i < j ? 0 : a[i - j][j]);
            System.out.println(a[m][n]);
        }
    }
}

C++:
#include <iostream>

using namespace std;

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

int main() {
    int m, n;
    while (cin >> m >> n) {
        cout << put_apples(m, n) << endl;
    }
    return 0;
}


发表于 2021-01-25 14:11:38 回复(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&nbs***bsp;n == 1:
        return 1
    if n > m:
        return putApple(m, m)
    else:
        return putApple(m, n - 1) + putApple(m - n, n)


while True:
    try:
        m, n = map(int, input().split())
        print(putApple(m, n))
    except:
        break

编辑于 2020-12-09 12:27:29 回复(0)