如何递归地将任何大额写成 5 和 7 个硬币的总和?

Question

我正在上一门离散数学课程，我不知道如何在 Python 中制作一个递归函数，该函数将任何大量转换为 5 和 7 硬币的总和。

我尝试了 3 和 5 硬币，它正在工作，但对于 5 和 7- 它没有，我没有找到一些关于它的东西，比如规则或其他东西。

def change(amount) :
assert( amount>= 12 )
if amount==12 :
return [5,7]
if amount==14 :
return [7,7]
if amount==15:
return [5,5,5]
coins=change(amount-7)
coins.append(7)
return coins

我希望所用硬币的输出，但它就是不起作用，当我发送它时它说"运行时错误"。

Answer 1

这里的问题不在于python代码，而在于算法。如评论中所述，总是先删除 7 可能会导致您在无限递归的情况下。

如果"金额"足够大(我猜高于 35 个有效，但您可能想做数学运算以找到确切的限制(，您可以像这样进行：

def change(amount):
if (amount % 5 == 0):
return [5] * int(amount/5)
elif (amount % 7 == 0):
return [7] * int(amount/7)
else:
coins = change(amount-5)
return coins.append(5)

这适用于足够大的值，因为在最多 7 次删除 5 后，您将始终得到一个 7 的倍数的结果。

应该有更聪明的方法可以做到这一点，但它应该有效。

---

知道最小值为23，另一种方法(非递归(是查看模5除法(amount % 5(，并给出5个不同的解决方案。

如果是 0，amount可以除以 5，所以它只是一个 5 的列表;如果是 1，去掉 3*7 = 21，剩下的就是 5 的列表;依此类推。以下代码为您提供了所有大于 23amount的正确答案。然后，如有必要，您只需处理剩余的情况。

def change(amount):
d = amount % 5
if d == 0:
return [5] * int(amount/5)
elif d == 1:
return [7] * 3 + [5] * int((amount-21)/5)
elif d == 2:
return [7] + [5] * int((amount-7)/5)
elif d == 3:
return [7] * 4 + [5] * int((amount-28)/5)
elif d == 4:
return [7] * 2 + [5] * int((amount-14)/5)

Answer 2

只是为了好玩，它可能会帮助你查看一个实际上是递归的变革程序。

# amount paid and cost due in dollars.
def process(paid,cost):
amount = int((float(paid)-float(cost))*100)
names = ['penny','nickle','dime','quarter','halfdollar','dollar','2Piece','5Spot','Tenner','Dub','Fifty','CNote']
made = {k:0 for k in names}
return(makeChange(amount,made))
def makeChange(amount,made):
# coin and bill values in cents 
coins = [1,5,10,25,50,100,200,500,1000,2000,5000,10000]
coins.reverse()
names = ['penny','nickle','dime','quarter','halfdollar','dollar','2Piece','5Spot','Tenner','Dub','Fifty','CNote']
names.reverse()
decode = {coins[n]:names[n] for n,k in enumerate(coins)}
i = 0
if(amount>0):
while(coins[i]>amount):
i+=1
amount-=coins[i]
made[decode[coins[i]]]+=1
else:
return(made)
return(makeChange(amount,made))
test = process(20,11.73)
for k in test:
if(test[k]!=0):
print(k+":"+str(test[k]))

Answer 3

由于 24、25、26、27、28 都可以用 5 和 7 表示，我们可以创建一个算法，在每次递归调用期间将数量减少 5。最后，递归将实现 if else 语句中列出的基本条件之一。代码如下所示

def change(amount):
if amount == 24:
return [5, 5, 7, 7]
if amount == 25:
return [5, 5, 5, 5, 5]
if amount == 26:
return [7, 7, 7, 5]
if amount == 27:
return [5, 5, 5, 5, 7]
if amount == 28:
return [7, 7, 7, 7]
coins = change(amount-5)
coins.append(5)
return coins