邮票拼图

  • Z时代
  • 2024-01-10
  • 分类：问答

我的老师给了我一套问题，让我们考虑递归。其中之一，我们被赋予一个价值（邮资的成本）和一个可用的邮票列表。该练习涉及编写一个递归函数，该函数返回邮票的最小长度列表，其总数等于邮资的总和值。邮票拼图

解决这个问题的正确方法就是让程序比较每一种可能性并返回最小长度的程序。如果是这种情况，我不确定如何为它编写程序，更不用说使用递归，因为我一般都是Python和编程的新手。根据教师提供的线索，我想出了这样的事情：

stampList=[1,4,7] 
postage=10 
def pickStamps(postage): 
    if postage==0: #base case 1 
     return "" 
    if postage<0: #base case 2 
     return none 
    else: 
     x=postage 
     for i in range(len(stampList)-1): 
     x=x-stampList[i] 
     return pickStamps(x)

我试图有蟒蛇开始邮资的价值，减去结合每种面额才能到零，但我不确定如何将每种可能性都列入清单。在问题中提出，编写另一个函数可能是明智的，该函数接受一个列表列表的参数，并返回列表中最小长度元素的索引，但我不确定如何实现该列表。有人能告诉我如何编写这样的代码或解释解决这个问题的最佳方法吗？谢谢！

回答：

试想一下，你有已经工作的功能：

def pick_stamps(postage): 
    '''Returns list of stamps needed to cover postage'''

鉴于你有这个功能，你可以用它来实现您的版本：

def my_pick_stamps(postage): 
    if postage == 0: 
     return [] 
    else: 
     stamp = max(stamp for stamp in stamps 
        if stamp <= postage) 
     return [stamp] + pick_stamps(postage - stamp)

当然，一旦你实现你可以使用你的版本，并用my_pick_stamps代替pick_stamps。

回答：

def ways(wallet, stamp_values, postage): 
    amount = sum(wallet) 
    if amount == postage: 
     return [wallet] 
    elif amount > postage: 
     return [] 
    else: 
     next_stamp = wallet[-1] if wallet else max(stamp_values) 
     new_stamps = stamp_values[stamp_values.index(next_stamp):] 
     gen = (ways(wallet + [c], new_stamps, postage=postage) for c in new_stamps) 
     return sum(gen, [])

试驾：

>>> combos = ways([], stamp_values=(7,4,1), postage=10) 
>>> combos 
[[7, 1, 1, 1], 
[4, 4, 1, 1], 
[4, 1, 1, 1, 1, 1, 1], 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]] 
>>> min(combos, key=len) 
[7, 1, 1, 1]

注意该解决方案实际上是在你的例子非唯一，即7,1,1,1和4,4,1,1都是相同的长度。假设我们有一个价值3的新邮票，我们应该期望看到一个独特的解决方案，然后（7 + 3 == 10与两个邮票）。

>>> ways([], stamp_values=(7,4,3,1), postage=10) 
[[7, 3], 
[7, 1, 1, 1], 
[4, 4, 1, 1], 
[4, 3, 3], 
[4, 3, 1, 1, 1], 
[4, 1, 1, 1, 1, 1, 1], 
[3, 3, 3, 1], 
[3, 3, 1, 1, 1, 1], 
[3, 1, 1, 1, 1, 1, 1, 1], 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

以上是 邮票拼图 的全部内容， 来源链接： utcz.com/qa/260391.html

回到顶部