求和：递归是必要的吗？递归算法是什么样的？

Question

def numPens(n):
    """
    n is a non-negative integer

    Returns True if some non-negative integer combination of 5, 8 and 24 equals n
    Otherwise returns False.
    """
    if n < 5:
        return False
    N = n
    while N >= 0:
        if  N % 24 == 0 or N % 8 == 0 or N % 5 == 0: # if N / 24 is equal to 0 then we can buy N pens
            return True
        if N < 5:
            return False    # if N < 5 we cannot buy any pens

        if  N > 24:         # if N is greater than 24 , take away 24 and continue loop
            N -= 24
        elif N > 8:         # if N is greater than 8, take away 8 and continue loop
            N -= 8
        else:
            N -= 5          # else take away 5 and continue loop

我需要为一个测试创建这个函数，我在想这个问题是否可以用递归的方法来解决，或者有什么更有效的解决方案。我刚开始学习编程，所以任何帮助都非常感谢，谢谢。

Answer 1

显然，这是一个递归问题，下面的代码可能是最简单的：

def numPens(n):
    if n < 5:
        return False
    elif n==5 or n==8 or n==24:
        return True
    else:
        return numPens(n-5) or numPens(n-8) or numPens(n-24)

如果你想让它更高效、更稳健，可以自己进行改进。

Answer 2

有一些更高效的算法，它们的时间复杂度是O(1)，也就是说它们的运行时间是固定的，不会随着输入的大小而变化。

比如，你可以把

if n > 40: 
    return True

作为你的基本情况之一！

你还可以通过维护一个查找表来让它变得更高效，这个查找表可以存储其他值（n < 40）。

你之所以能这样做，是因为这个原因：http://en.wikipedia.org/wiki/Coin_problem#n_.3D_2

Answer 3

if  N % 24 == 0 or N % 8 == 0 or N % 5 == 0

如果你去掉上面的取模（%）检查，那么你的算法就叫做贪心算法。它每次都减去能减去的最大数字。你可能注意到了，贪心算法并不总是有效。比如说，对于15，它会算成5 + 5 + 5，这个答案就是错的。

 15 (-8) --> 7 (-5) --> 2 --> False

通过加入取模检查，你改善了贪心算法，因为它现在能正确处理15了。但是它仍然有漏洞：比如说26可以表示为8 + 8 + 5 + 5。

 26 (-24) --> 2 --> False

要正确解决这个问题，你必须放弃贪心的方法。仅仅减去最大的数字并不总是够的。回答你的问题，是的，这里需要一个递归的解决方案。

def numPens(n):
    """
    n is a non-negative integer

    Returns True if some non-negative integer combination of 5, 8 and 24 equals n
    Otherwise returns False.
    """
    # Base case: Negative numbers are by definition false.
    if n < 0:
        return False

    # Base case: 0 is true. It is formed by a combination of zero addends,
    # and zero is a non-negative integer.
    if n == 0:
        return True

    # General case: Try subtracting *each* of the possible numbers, not just
    # the largest one. No matter what n-x will always be smaller than n so
    # eventually we'll reach one of the base cases (either a negative number or 0).
    for x in (24, 8, 5):
        if numPens(n - x):
            return True

    return False

这是解决这个问题最简单的方法，对于小一点的数字效果还不错。但是对于大数字来说，由于它会多次计算同样的数字，所以速度会很慢。一个优化的建议是使用动态规划来消除重复计算。