递归找到产生指定数量的所有硬币组合

我提前致歉。我知道，这个问题之前已经被问到了没有产生我想要/需要的结果的答案。我正在尝试写，做在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)

来源

2012-03-22 sudostack

如果这是家庭作业（我假设它是），请其标记为此类。如果有很多类似的问题，你的问题又有什么不同？ – phihag 2012-03-22 01:06:34

尝试搜索造成问题的更改。维基百科页面上有很多很好的信息。 – 2012-03-22 01:09:30

闻起来像家庭作业 – inspectorG4dget 2012-03-22 01:14:28

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

你要rest这里，逻辑地而不是*rest，因为你必须在每边两个项目。在这里使用*rest会创建一个额外的列表环绕层，然后导致您大概看到的异常。

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

来源

2012-03-22 01:17:08

这非常有帮助！ – sudostack 2012-03-22 02:00:03

这是Python 3.x的一个很好的语法，希望。 – Bartek 2012-03-22 03:47:11

让tuple解包的*语法很好，但是正如前面提到的那样，这里实际上并不需要：/ – 2012-03-22 04:12:24

递归背后的想法很简单：

试图减少问题的大小，每次一个小小的一步。

如果你能做到这一点，你就差不多完成了！从大问题开始，逐渐减小尺寸，直到最终出现一个非常小的问题。无论你喜欢，你都可以解决。

这是如何适用于变更问题？那么，如果你被要求制作n，你可以通过使用一枚硬币来减少问题的大小。如果你继续前进，最终你会得到一个足够小的问题来解决！

来源

2012-03-22 01:17:35 katrielalex

递归找到产生指定数量的所有硬币组合

回答

相关问题