与Project Euler 31有一些问题

Question

我一直在努力从Project Euler解Problem 31。我几乎完成了，但是我的代码给了我一个错误的答案。我爸爸给出了正确的答案，而我爸爸给了我一个完全错误的答案

coins = (1,2,5,10,20,50,100,200)
amount = 200
def ways(target, avc):    
    target = amount
    if avc <= 1:
          return 1
    res = 0
    while target >= 0:
        res = res + ways(target, avc-1)
        target = target - coins[avc]
    return res
print(ways(amount, 7))

这就是我得到的答案

284130

答案应该是73682。 编辑：感谢所有回答我问题的人。多亏了你们，我才明白了这一点

Answer 1

我认为有几种方法可以改善解决问题的方式：

• 将任务描述复制到源代码中。这将使你更加独立于互联网资源。这样你就可以脱机工作了。即使页面已关闭或完全消失，也会使其他人了解您试图解决的问题

• 使用一个IDE，它可以正确地突出显示语法，并提示代码可能有什么问题。IDE将告诉您@aronquemarr在评论中提到了什么：

  

• 还有一种东西叫做幻数。代码中的许多数字都可以解释，但是为什么要从7开始呢？。这个数字来自哪里？问题描述中没有出现7

• 使用更好的命名，以便更好地理解代码的功能。avc代表什么？如果你认为它是available_coins，那是不对的。有8种不同的硬币，而不是7种

• 如果仍然不起作用，请将问题简化为更简单的问题。从你能想到的最简单的硬币开始，例如，只提供一种类型的硬币，并将数量设置为2美分。应该只有一个解决方案

• 为了确保这个简单的结果永远不会中断，引入断言或单元测试。当您更改代码以处理更大的数据集时，它们将帮助您。它们还将改变您编写代码的方式。在您的例子中，您会发现从外部作用域访问变量coins可能不是一个好主意，因为当您切换到下一个级别时，它会破坏您的断言。所需的更改将使您的方法更加独立和健壮

• 然后，使用两种不同的硬币等来增加难度

  我在这个问题上使用的第一个断言示例：

  # Only 1 way of making 1 with only a 1 coin of value 1
  assert(find_combinations([1], 1) == 1)
  # Still only 1 way of making 1 with two coins of values 1 and 2
  assert(find_combinations([1,2], 1) == 1)
  # Two ways of making 2 with two coins of values 1 and 2
  assert(find_combinations([1,2], 2) == 2)
  

• 一旦结果不再符合您的期望，请使用调试器并逐步完成代码。在每行之后，对照您认为应该是的值检查调试器中的值

  有一次，调试器将是您最好的朋友。你永远无法想象没有它你是怎么做的。你只需要学会如何使用它

Answer 2

首先，读Thomas Weller's answer。他们就如何改进编码和解决问题给出了一些极好的建议

其次，您的代码有效，并在以下更改后给出正确答案：

• 按照建议，删除target = amount行。在每次调用时（甚至在递归调用时），您都将函数的参数改为全局amount。排除了答案是3275的问题后，仍然不是正确答案
• 您必须记住的另一件事是Python是0索引的。因此，最简单的case条件应该是if avc <= 0: ...（而不是<=1）

做了这两个更改后，代码给出了正确的答案。以下是您的代码和这些更改：

coins = (1,2,5,10,20,50,100,200)
amount = 200
def ways(target, avc):
    if avc <= 0:
        return 1
    res = 0
    while target >= 0:
        res = res + ways(target, avc-1)
        target = target - coins[avc]
    return res
print(ways(amount, 7))

最后，有很多关于Euler项目的答案out there。在自己解决了问题之后，看看其他人做了什么可能会有用。作为参考，我以前并没有真正解决过这个项目，所以我必须先解决这个问题Here是我的解决方案。我在上面添加了一堆注释来解释它的功能

编辑

我刚刚注意到一些非常令人担忧的事情：只有当coins的第一个元素为1时，您的代码（修复后）才能工作。所有其他元素都可以洗牌：

# This still works ok
coins = (1,2,200,10,20,50,100,5)
# But this does not
coins = (2,1,5,10,20,50,100,200)

要确保始终如此，您只需执行以下操作：

coins = ... # <- Some not necessarily sorted tuple
coins = tuple(sorted(coins))

原则上还有一些其他问题。您的解决方案因非唯一值coins而中断，这些值不包括1。前者可以通过使用sets来修复，后者可以通过修改if avc <= 0:的大小写来修复（检查目标是否被剩余硬币整除）。下面是一段实现了这些更改的代码。我还重新命名了变量和函数，使其更易于阅读，并使用coins作为参数，而不是avc指针（顺便说一句，我无法停止阅读avec）：

unique = lambda x: sorted(set(x)) # Sorted unique list
def find_combinations(target, coins):
    ''' Find the number of ways coins can make up the target amount '''
    coins = unique(coins)
    if len(coins)==1: # Only one coin, therefore just check divisibility
        return 1 if not target%coins[0] else 0 
    combinations = 0
    while target >= 0:
        combinations += find_combinations(target, coins[:-1])
        target -= coins[-1]
    return combinations

coins = [2,1,5,10,20,50,100,200] # <- Now works
amount = 200

print(find_combinations(amount, coins))