0

我提前道歉。我知道之前有人问过这个问题，但答案并没有产生我想要/需要的结果。我正在尝试编写一个在 Python3 中执行以下操作的函数：

我需要一个递归函数，它返回产生指定数量的所有方式（硬币组合）。此函数只能包含两个参数，金额和硬币。我很难将注意力集中在递归上，因此也将不胜感激。谢谢。

这是我目前拥有的：

COINS = dict(
    USA=[100, 50, 25, 10, 5, 1],
    AUSTRALIA=[200, 100, 50, 20, 10, 5],
    UK=[500, 200, 100, 50, 20, 10, 5, 2, 1]
)

def change(amount, coins):
    """
    >>> change(100, COINS['USA'])
    293
    """
    if amount < 0:
        return 0
    elif amount == 0:
        return 1
    else:
        biggestcoin, *rest = coins[0], coins[1:]
        return change(amount-biggestcoin, coins) + change(amount, rest)
4

2 回答 2

3 
biggestcoin, *rest = coins[0], coins[1:]

从逻辑上讲，你想要rest这里，不是*rest，因为你在每一边都有两个项目。在此处使用*rest会创建一个额外的列表包装层，然后会导致您可能看到的异常。

一旦你解决了这个问题：想想如果你不能用每个硬币的 1 个来达到所需的金额会发生什么。change(amount, rest)递归调用最终将发生大于amount零且rest为空的情况。你也需要处理这种情况。

于 2012-03-22T01:17:08.833 回答
1

递归背后的想法很简单：

尝试减少问题的规模，一次一小步。

如果你能做到这一点，你就差不多完成了！从大问题开始，然后一点一点地缩小规模，直到你遇到一个非常小的问题。你可以随心所欲地解决这个问题。

这如何适用于变革问题？好吧，如果你被要求做n，你可以只用一枚硬币来缩小问题的规模。如果你继续前进，最终你会得到一个足够小的问题来解决！

于 2012-03-22T01:17:35.927 回答