本文主要是介绍【备战蓝桥杯青少组】第三天 放苹果,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题
OpenJudge - 666:放苹果
描述
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。
输入
第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。
输出
对输入的每组数据M和N,用一行输出相应的K。
样例输入
1 7 3样例输出
8
思路
经典的递归题,类似的还有高位到低位降序的n位数。
为了避免重复,假设每次放的新盘子的苹果数,不能超过已放过的每个盘子里的苹果数
代码
简化版
def place(m,n,pre=[]):k=m if len(pre)==0 else min(m,pre[-1]) # k 为最大可放数# 不可能的情况if (n==0): return 0 # 没有盘子,就没有放法if (n==1 and m>k): return 0 # 苹果太多放不下if (m>n*k): return 0 # 更多的放不下# 唯一解的情况if (n==1 and m==k): return 1if (m==0): return 1if (k==1 and m<=n): return 1if (k>=1 and m==1): return 1# 其他情况return sum([place(m-i,n-1,pre+[i]) for i in range(k+1)]) # pre为之前的盘子,i为新放的盘子的苹果数
cnt=int(input()); data=[]
for i in range(cnt): data.append(list(map(int,input().split())))
for i in range(cnt): print(place(data[i][0],data[i][1]))
完整版
DEBUG=Falsedef place(m,n,pre=[]):k=m if len(pre)==0 else min(m,pre[-1]) # k 为最大可放数# 不可能的情况if (n==0): return 0 # 没有盘子,就没有放法if (n==1 and m>k): return 0 # 苹果太多放不下if (m>n*k): return 0 # 更多的放不下# 唯一解的情况if (n==1 and m==k):ans.append(pre+[m]);if DEBUG: print(ans[-1]);return 1if (m==0):ans.append(pre+[0]*n); if DEBUG: print(ans[-1]);return 1if (k==1 and m<=n):ans.append(pre+[1]*m+[0]*(n-m)); if DEBUG: print(ans[-1]);return 1if (m==1 and k>=1):ans.append(pre+[1]+[0]*(n-1)); if DEBUG: print(ans[-1]);return 1# 其他情况return sum([place(m-i,n-1,pre+[i]) for i in range(k+1)]) # pre为之前的盘子,i为新放的盘子的苹果数
cnt=int(input())
data=[]
for i in range(cnt):data.append(list(map(int,input().split())))
for i in range(cnt):ans=[]print(data[i],"的放法共有:",place(data[i][0],data[i][1]))if(not DEBUG):if(len(ans)>10):print(ans[:10],"...")else:print(ans)
这篇关于【备战蓝桥杯青少组】第三天 放苹果的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!