0

我是编程新手，并试图使用基本的 Python 在 Project Euler 上 解决这个问题。

本质上，我尝试使用基于在每个阶段选择的最大值的递归，并使用列表来维护未来选择的可能选项。

代码很短，如下所示：

def func(n,l):
    if n<0:
        return 0
    if l==[1] or n==0:
        return 1
    else:
        j=0
        while l != []:
            j=j+func(n-l[0],l) 
            del l[0]
        return j

print func(200,[200,100,50,20,10,5,2,1])

例如，如果我们有 

func(5,[5,2,1])

递归将其拆分为

func(0,[5,2,1]) + func(3,[2,1]) + func(4,[1])

但是代码似乎永远不会通过。它要么说有list-index-out-of-range错误，要么说有maximum-recursion-depth错误（即使对于非常小的玩具实例）。我找不到错误。任何帮助都感激不尽。

4

3 回答 3

3

在 Python 中，列表通过引用而不是值传递给函数。对您的程序最简单的修复是将递归调用更改为func(n - l[0], l[:]). 这样，列表将按值传递。

于 2013-03-28T08:09:57.920 回答
1

您没有考虑到的一件事是：

j=j+func(n-l[0],l)

不复制l.

因此，所有递归调用都func在同一个列表上进行。当最里面的调用删除最后一个元素l并返回时，它的调用者将尝试del l[0]并得到一个IndexError.

于 2013-03-28T08:07:25.893 回答
1

在每次递归时，做出以下 2 个决定：

  1. 从可用的硬币类型中取出第一枚硬币（比如f），然后检查我们是否可以从这些硬币中制造（nf）。这导致了一个子问题 func(n - f, l)
  2. 忽略第一个硬币类型，并检查我们是否可以从剩余的硬币类型中得到 n。这导致了一个子问题 func(n, l[1:])

组合的总数应该是两个子问题的总和。所以代码是：

def func(n, l):
    if n == 0:
        return 1
    if n < 0 or len(l) == 0:
        return 0
    if l == [1] or n == 0:
        return 1

    return func(n - l[0], l) + func(n, l[1:])

每个递归的副本l由l[1:]. 这可以在下一次递归之前被pop元素省略并在append之后恢复。

def func(n, l):
    if n == 0:
        return 1
    if n < 0 or len(l) == 0:
        return 0
    if l == [1] or n == 0:
        return 1

    full = func(n - l[-1], l)
    last = l.pop()
    partial = func(n, l)
    l.append(last)
    return full + partial
于 2013-03-28T08:27:28.740 回答