首页 > 试题广场 >

放苹果

[编程题]放苹果

热度指数：159853 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。

数据范围： $0 \le m \le 10 \$ ， $1 \le n \le 10 \$ 。

输入描述:

输入两个int整数

输出描述:

输出结果，int型

示例1

输入

7 3

输出

算法知识视频讲解

Python

牛客955058829号

二维数组解法

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)

Python

D-flmx

搞了半天，原来map（）里面写了int（），而不是int

发表于 2021-05-11 01:02:23 回复(1)

Python

牛客诶谁

import sys


# 使用递归方法
def rec_func(m, n):
    # 如果只有一个盘子，或者只有0-1个苹果，就只有一种方法
    if n == 1&nbs***bsp;m == 0&nbs***bsp;m == 1:
        return 1
    # 如果盘子数量大于苹果数量，说明最少有n-m个盘子是空的，可以拿掉n-m个盘子
    if n > m:
        return rec_func(m, m)
    # 盘子数量小于等于苹果数量
    else:
        # 分两种情况，最少有一个盘子是空的，或者每个盘子至少一个苹果
        return rec_func(m, n-1) + rec_func(m-n, n)


# 使用动态规划
def dp_func(m, n):
    # m+1列，n行的列表，用于存储结果
    dp = [[0]*(m+1)]*(n+1)
    # 只有一个盘子时，结果为1
    for i in range(m+1):
        dp[0][i] = 1
        dp[1][i] = 1
    # 只有0-1个苹果时，结果为1
    for i in range(n):
        dp[i][0] = 1
        dp[i][1] = 1
    
    # 从第2行第2列开始遍历
    for i in range(2, n+1):
        for j in range(2, m+1):
            if i > j:
                dp[i][j] = dp[j][j]
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-i]
    return dp[n][m]


for line in sys.stdin:
    m = int(line.split()[0])
    n = int(line.split()[1])
#     print(rec_func(m, n))
    print(dp_func(m, n))

发表于 2021-05-02 16:05:03 回复(1)

Python

牛客622181604号

# 感谢评论区大佬

def f(m, n):

if m <= 1 or n <= 1: # 起点最好带两个值算一下，因为会影响后面取值
return 1
if m < n:
return f(m, m) # 盘子多于苹果时，必然会有盘子空着。
# 由于与顺序无关，所以可以去除必然会空余的那n-m个盘子，
# 只留下m个盘子
else:
return f(m, n-1)+f(m-n,n) # 分解为子问题：m个苹果放在n-1个盘子里，
# 或者n个盘子里至少各有一个苹果，从而只需
# 要考虑剩下的m-n个怎么放进n个盘子
# 但此时又出现一个问题：m-n可能小于零，即盘子太多了。
# 所以需要前一步的判断

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

发表于 2021-04-07 16:29:23 回复(0)

Python

天君添桢

while True:
try:
m_n = input().strip().split()
m, n = int(m_n[0]), int(m_n[1])
dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
for i in range(1, n + 1):
dp[0][i] = 1
dp[1][i] = 1
for j in range(m + 1):
dp[j][1] = 1
for i in range(2, m + 1):
for j in range(2, n + 1):
dp[i][j] = dp[i][j - 1] + (0 if i < j else dp[i - j][j])

print(dp[m][n])

except:
break

发表于 2021-03-19 10:30:15 回复(0)

Python

星凌九天

def put(m,n):
if n==1:
return 1
elif m<n:
return put(m,n-1)
else:
return put(m,n-1)+put(m-n,n)
while True:
try:
m,n=map(int,input().split())
print(put(m,n))
except:
break

发表于 2021-03-15 10:22:44 回复(0)

Python

_土司空

while True:
    try:
        m,n = map(int,input().split())#m是苹果数。n是盘子数
        a = [[0 for j in range(m+1)]for i in range(n+1)]
        for i in range(1,n+1):
            if i == 1:
                for j in range(1,m+1):
                    a[i][j] = 1
            else:
                for j in range(1,m+1):
                    if j < i:

                        a[i][j] = a[i-1][j]
                    elif j == i:
                        a[i][j] = a[i-1][j]+1
                    else:
                        a[i][j] = a[i-1][j]+a[i][j-i]

        print(a[n][m])
    except:
        break

发表于 2021-03-05 21:21:49 回复(0)

Python

JeremyStar

# 思路：
# 其实这题考的是数学啊，首先当有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 回复(1)

Python

乐观的lishan

# 2020年11月14日09:04:38
def divide(m, n):
#   0<=m<=10,  1<=n<=10
#   最多只有1个苹果，或只有1个盘子时，只有1种分法
    if m <= 1&nbs***bsp;n == 1:
        return 1
#   至少有2个苹果，且苹果数小于盘子数（一定有空盘）  
    elif m < n:
        return(divide(m, n-1))
#   至少有2个苹果，且苹果数大于等于盘子数（不一定有空盘）      
#   1、把m个苹果放在n-1个盘子（有空盘）
#   2、先在n个盘子中均放1个苹果（无空盘），再把剩下的m-n个苹果放在n个盘子中
    else:
        return(divide(m, n-1) + divide(m-n, n))

while True:
    try:
        data = input().split()
        m = int(data[0])
        n = int(data[1])
        print(divide(m, n))
    except:
        break

发表于 2020-11-14 10:00:52 回复(0)

Python

混分兽

提供一个python的递归思路，不用费太多的脑子去想，思路比较自然，避免递归过深要适度加上一些剪枝的操作：

def helper(plate,apple,start_number):
    if plate==1:
        return 1
    total_count=0
    for j in range(start_number,apple):
        if j*(plate-1)<=apple-j:
            total_count+=helper(plate-1,apple-j,j)
    return total_count

while True:
    try:
        apple,plate=list(map(int,input().split()))
        print(helper(plate,apple,0))
    except:
        break

发表于 2020-09-14 23:18:20 回复(3)

Python

牛客902100313号

def putapple(m,n):
if (m < 0):
return 0
if (m == 1) | (n == 1) | (m == 0):
return 1
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-09-14 17:28:34 回复(0)

Python

牛客276152761号

动态规划+递归，有多个样例输入

python3:

while True:
    try:
        m, n = map(int, input().split())
        res = 0
        def deiapples(k, l):
            global res
            if k < 0:
                return
            if l <= 1 or k <= 1:
                res = res + 1
                return
            for i in range(l):
                x = k - (l-i)
                deiapples(x, l-i)
        deiapples(m, min(m, n))
        print(res)
    except:
        break

编辑于 2020-09-09 16:16:00 回复(0)

Python

JaquesJames

参考链接：http://blog.csdn.net/kongming_acm/article/details/6208243

设f[m][n]为将m分成最多n份的方案数，且其中的方案不重复，即每个方案前一个份的值一定不会比后面的大。

f[m][n] = f[m][n - 1] + f[m - n][n]（且当m== 0 || n == 1时，方案数为1，当m < n时，相当于m个苹果放进m个盘子）

f[m][n - 1]相当于第一盘子中为0，只用将数分成n - 1份即可。因为0不会大于任何数，相当于f[m][n - 1]中的方案前面加一个为0的盘子，而且不违背f的定义。所以f[m][n - 1]一定是f[m][n]的方案的一部分，即含有0的方案数。
f[m - n][n]相当于在每个盘子中加一个数1。因为每个盘子中加一个数1不会影响f[m][n - 1]中的方案的可行性，也不会影响f的定义。所以f[m - n][n]一定是f[m][n]的方案的一部分，即不含有0的方案数。

def apple_dev_num(m, n):
    if m == 0 or n == 1:
        return 1
    elif m < n:
        return apple_dev_num(m, m)
    else:
        return apple_dev_num(m, n-1) + apple_dev_num(m-n, n)

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

编辑于 2020-08-22 21:01:17 回复(0)

Python

调包王

# a代表苹果数，b代表盘子数
def func(a,b):
    # 如果苹果没了，或者只剩一张盘子，返回1
    if a == 0&nbs***bsp;b == 1:
        return 1
    # 如果盘子数大于苹果数，最多只能相同数量的盘子，一盘一个
    if b > a:
        return func(a,a)
    else:
        # 不然 返回func(a,b-1)代表少放一个盘子的情况，和func(a-b,b)把目前苹果全放入盘子的情况
        return func(a,b-1) + func(a-b,b)


while True:
    try:
        temp = input().split()
        if temp:
            a,b = int(temp[0]),int(temp[1])
            print(func(a,b))
    except:
        break

发表于 2020-08-05 14:48:53 回复(0)

Python

君临天下201804050931706

# 解题分析：
#        设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时，所有苹果都必须放在一个盘子里，所以返回１；
#        当没有苹果可放时，定义为１种放法；
#        递归的两条路，第一条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)

Python

最爱大麦茶

def f(m,n):
    if m < 0&nbs***bsp;n < 0:
        return 0
    elif m ==0&nbs***bsp;n == 1:
        return 1
    elif n>m:
        return f(m,m)
    else:
        return f(m,n-1)+f(m-n,n)

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

发表于 2020-06-11 23:03:20 回复(0)

Python

朝夕_

def apple(a,b):
  if a == 0&nbs***bsp;b == 1:
    return 1
  elif a < b:
    return apple(a,a)
  else:
    return apple(a,b-1) + apple(a-b,b)
while True:
  try:
    c,d = map(int,input().split())
    print(apple(c,d))
  except:
    break

发表于 2020-02-20 19:21:30 回复(0)

Python

谢小橙

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)

Python

完善信息

python dp版

while True:
    try:
        m, n = input().strip().split()
        m, n = int(m), int(n)
        n = min(m, n) # n > m 与 n == m 相等

        dp = [[0] * (n+1) for _ in range(m+1)]
        # dp[0][0] = 0, dp[0][j] = 1 (for j in [1,n]), dp[i][0] = 0 (for i in [1, m])
        for j in range(1, n+1):
            dp[0][j] = 1

        for i in range(1, m+1):
            for j in range(1, n+1):
                dp[i][j] = dp[i][j-1] + dp[i-j][j]

        # print(dp)
        print(dp[m][n])

    except:
        break

发表于 2019-10-05 19:09:20 回复(1)