如何使用递归函数进行硬币兑换？

Question

我尝试在Python中使用递归函数。我有一个场景，我生活在一个有5枚和7枚硬币的国家。我想象着去购物，拿到剩下的硬币。我试着从24岁到1000岁，我想知道：

• 对于24:[5,5,7,7]
• 对于25：[5,5,5,5,5]
• 第26条：[5,7,7,7]

我得到错误：'TypeError:'int'对象不可编辑'

你能帮我解决我的问题吗

amount = range(24,1000)
def change(amount):
    for i in amount:
        for s in range(1,100):
            for j in range(1,100):
                if i == (5*s + 7*j):
                    list = [s,j]
                    print(list)
                else:
                    coins = change(i - 5)
                    coins.append(5)

change(amount)

Answer 1

代码可以如下所示：

def change(start, end):

    for i in range(start, end):

        ...

change(24,1000)

Answer 2

首先，错误的原因是您使用两种不同类型的参数调用change：在“测试用例”（最后一行）中，您使用range调用它，而当您递归时，您使用int调用它range是可iterable的，但是int是不可iterable的

然而，我认为重新思考整个算法会对您有所帮助。通常，递归比等价的非递归算法具有更少的循环。例如，这两种算法都打印出从1到x的数字，但第二种算法没有循环：

def nonrecursive(x):
    for i in range(1, x+1):
        print(i)

def recursive(x):
    if x > 1:
        recursive(x-1)
    print(x)

当您可以用一个更简单问题的答案来编写问题的答案时，递归会很有帮助。递归函数一直试图解决“更简单”的问题，直到它必须解决一个简单的问题

因此，递归函数通常有两个部分：一个或多个递归案例，将一个问题转化为另一个问题；一个或多个基本案例，通常是我们算法解决的“最小”问题

那么，这个问题的基本情况是什么？我想说基本情况是0-改变0的方法是不使用硬币：[]

现在递归的情况是什么？我想说实际上有两个-如果你有一个解决方案change(x)，那么change(x+5)的解决方案是同一个解决方案，再加上一个5硬币；类似地，change(x+7)的解决方案与另一个7硬币的解决方案相同

现在看看你能不能把这些整合成一个完整的解决方案。作为提示，您不需要任何for或while循环

Answer 3

对于这种解决方案，关键的见解是，每一笔金额都可以表示为一套参考硬币或一套参考硬币加上一定数量的填充硬币。例如，如果金额为42，则可以表示为28+7+7或27+5+5+5

注：参考金额需要是从24开始到30的连续整数，以允许填充硬币的值为7。这是一个棘手的部分

解决方案：

def coin_count(amount, filler_coin_value=5):
    reference = {
        24: (7, 7, 5, 5), 
        25: (5, 5, 5, 5, 5),
        26: (7, 7, 7, 5), 
        27: (5, 5, 5, 5, 7), 
        28: (7, 7, 7, 7),
        29: (7, 7, 5, 5, 5),
        30: (5, 5, 5, 5, 5, 5)
    }
    coins = []
    while not amount in reference:
        amount -= filler_coin_value
        coins.append(filler_coin_value)
    coins.extend(reference[amount])
    
    return coins

虽然上述解决方案可行，但可以通过用一些（公认的棘手的）数学替换while循环来优化它

def coin_count_optimized(amount, filler_coin_value=5):
    reference = {
        24: (7, 7, 5, 5), 
        25: (5, 5, 5, 5, 5),
        26: (7, 7, 7, 5), 
        27: (5, 5, 5, 5, 7), 
        28: (7, 7, 7, 7),
        29: (7, 7, 5, 5, 5),
        30: (5, 5, 5, 5, 5, 5)
    }
    filler_count, off_by = divmod((amount - 24), filler_coin_value)
    coins = [filler_coin_value] * filler_count
    coins.extend(reference[24 + off_by])
    
    return coins

两种方法的时间比较：

import time

start_time = time.time()
for amount in range(24, 1000):
    coin_count(amount)
print("coin_count", time.time() - start_time)

start_time = time.time()
for amount in range(24, 1000):
    coin_count_optimized(amount)
print("coin_count_optimized", time.time() - start_time)

输出：

coin_count 0.022232770919799805
coin_count_optimized 0.0019953250885009766