首页 > 试题广场 >

放苹果

[编程题]放苹果

热度指数：151319 时间限制：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

输出

算法知识视频讲解

查看答案及解析

Python3

在开会的发呆爱好者很自信

# 跟AI磨了一个小时，他终于开窍了

from itertools import combinations_with_replacement

from collections import Counter

def distinct_combinations_of_apples(total_apples, num_bowls):

# 直接生成所有可能的组合，每个盘子中的苹果数视为独立事件

# 使用 combinations_with_replacement 保证了某个盘子可以有0个或多个苹果

valid_combinations = list(combinations_with_replacement(range(total_apples + 1), num_bowls))

# 去除不符合题意的组合（总和不足 total_apples 的）

valid_combinations = [combo for combo in valid_combinations if sum(combo) == total_apples]

# 将组合转化为排序后的元组，再转化为计数，从而去除顺序的影响

counted_combinations = Counter(tuple(sorted(combo)) for combo in valid_combinations)

# 返回去重后的组合数

return len(counted_combinations)

# 示例，7个苹果放入4个盘子

int_two = input().split()

m = int(int_two[0])

n = int(int_two[1])

print(distinct_combinations_of_apples(m, n)) # 输出对应的结果数

编辑于 2024-04-02 23:37:14 回复(0)

Python3

1bit都不剩了

理解为求满足以下条件数列的数量：

①不增加

②指定长度

③指定和

# 苹果和盘都是无序的
# 不递增数列的数量
def getNonIncreaseListNum(head_cap,sum,size):
    if(sum < 0): return 0
    if(head_cap*size<sum): return 0
    if(sum == 0): return 1
    if(size == 1): return 1
    list_num = 0
    for head_fig in range(head_cap,-1,-1):
        list_num += getNonIncreaseListNum(head_fig,sum-head_fig,size-1)
    return list_num
input_str = input()
m,n = list(map(int,input_str.split()))
way_num = getNonIncreaseListNum(m,m,n)
print(way_num)

发表于 2023-07-26 16:18:00 回复(0)

Python3

想润的考拉在度假

a,b = map(int,input().split())

n,s = [],set()

def dfs():

if sum(n) == a:

if len(n) == b:

t = n

elif len(n) < b:

t = n+([0]*(b-len(n)))

s.add(''.join(map(str,sorted(t))))

return

for i in range(a+1):

if sum(n)+i <=a and len(n)<b :

n.append(i)

dfs()

n.pop()

dfs()

print(len(s))

发表于 2023-07-01 18:33:25 回复(1)

Python3

牛客503925442号

n, m = map(int, input().split(' '))

res = []
temp = []


def iter_counts(n1, m):
    if m == 0:
        sum = 0
        for each in temp:
            sum += each
        if sum != n:
            temp.pop(len(temp)-1)
            return
        if sorted(temp) not in res:
            res.append(sorted(temp))
        temp.pop(len(temp) - 1)
        return
    for i in range(n1+1):
        temp.append(i)
        if m > 0:
            iter_counts(n1-i, m-1)
    temp.pop(len(temp) - 1)

try:
    iter_counts(n, m)
except Exception:
    pass
print(len(res))

发表于 2023-05-15 14:24:43 回复(0)

Python3

AlfredP

inputs=input().strip().split(' ')

mm=int(inputs[0])
nn=int(inputs[1])


# f[m][n]=f[m][n-1]+f[m-n][n] if m>=n
# f[m][n]=f[m][m] if m<n

f = [[1 for i in range(nn+1)] for j in range(mm+1)]
for m in range(2,mm+1):
    for n in range(2,nn+1):
        if m>=n:
            f[m][n]=f[m][n-1]+f[m-n][n]
        else:
            f[m][n]=f[m][m]
print(f[-1][-1])

发表于 2023-04-26 16:56:47 回复(0)

Python3

hippie20191120142593

#想了挺久才想明白
apple,pz = map(int,input().split())
def solution(a,p):
    if a == 0&nbs***bsp;p == 0&nbs***bsp;a == 1&nbs***bsp;p == 1:
        return 1
    elif a < p:
        return solution(a,a)
    return solution(a,p-1) + solution(a-p,p)
print(solution(apple,pz))

发表于 2023-04-01 00:58:28 回复(0)

Python3

hym1874

import sys

m,n= map(int,input().split(' '))

def f(m,n):

if m<0 or n<0:

return 0

elif m ==1 or n ==1:

return 1

else:

return f(m,n-1)+f(m-n,n)

print(f(m,n))

发表于 2023-03-09 18:38:10 回复(0)

Python3

再多看一眼就会爆炸

m,n=map(int,input().split())
def apple(m,n):
    if m==1&nbs***bsp;n==1 :
        return 1
    elif m==0:
        return 1
    elif m<0:
        return 0
    else:
        return apple(m,n-1)+apple(m-n,n)

print(apple(m,n))

发表于 2023-03-05 05:33:39 回复(0)

Python3

在做的机考肯定是必过呀

def apple(m,n):

if m < 1 or n ==1:

return 1

elif m < n:

return apple(m,m)

else:

return apple(m,n-1) + apple(m-n,n)

m,n = map(int,input().split())

print(apple(m,n))

发表于 2023-02-21 18:18:12 回复(2)

Python3

ssssuperstone

用“不降原则”来避免重复，即前一个盘子的数目要不少于后一个盘子的数目。f(m-n)就相当于在每个盘子里放一个苹果后再来摆放剩余的苹果。

m,n=map(int,input().split(' '))
def f(m,n):
    if m<2&nbs***bsp;n==1:
        return(1)
    elif m<n:
        return(f(m,m))
    else:
        return(f(m,n-1)+f(m-n,n))
print(f(m,n))

发表于 2023-02-14 16:55:40 回复(0)

Python3

牛客368065820号

m, n = map(int, input().split())


def app(a, b):
    if a < b:
        return app(a, a)
    if a <= 1:
        return 1
    return sum([app(a - i, i) for i in range(1, b + 1)])


print(app(m, n))

发表于 2023-02-03 23:45:31 回复(0)

Python3

牛客947768359号

def f(m,n):
    if (m<0&nbs***bsp;n<0)&nbs***bsp;(m==1 and n==0):
        return 0
    elif n==1&nbs***bsp;(m==1 and n>0):
        return 1
    else:
        return f(m,n-1)+f(m-n,n)
    
line = input().split(' ')
m , n = int(line[0]), int(line[1])
print(f(m,n))

发表于 2022-04-05 01:45:40 回复(0)

Python3

溪云初起日沉阁

其实还是没太懂。。。n-1和m-n

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

m,n =map(int,input().strip().split())
print(f(m, n))

发表于 2022-03-17 11:28:10 回复(0)

Python3

八月好菜

0 个苹果放入n个盘子，结果是0还是1？

发表于 2021-12-04 11:14:57 回复(1)

Python3

BoyangXu

递推的方式，利用公式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)

Python3

深圳达文西

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

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

发表于 2021-08-08 19:28:24 回复(0)

Python3

DAXIONGMAO

import sys
def f(a,p):
    if(a < p):
        return f(a,a)
    elif(p == 1&nbs***bsp;a <= 1):
        return 1
    else:
        return f(a,p-1) + f(a-p,p)
        
for line in sys.stdin:
    a,p = line.split(' ')
    a = int(a)
    p = int(p)
    print(f(a,p))

发表于 2021-07-29 11:43:42 回复(0)