求和:递归是必要的吗?递归算法是什么样的?

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

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

这是解决问题的最直接的方法，并且对于较小的数字也能很好地工作。对于较大的数字，由于多次计算相同数字的方式，它将很慢。留给读者的优化方法是使用动态规划来消除重复计算。

Answer 2

有更有效的(O(1))算法

例如，您可以添加

if n > 40: 
    return True

作为基本用例之一!

你可以让它更有效率，通过维护一个查找表的值(n <40)。

你可以这样做的原因是:http://en.wikipedia.org/wiki/Coin_problem#n_.3D_2

Answer 3

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

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 4

n=5a+8b+24c <=> n=5a+8(b+3c)，因此你可以有一个函数:

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

Answer 5

def numPens(n):
    global cantidad
    cantidad = cantidad + 1
    if n < 5:
        return False
    elif n%5==0 or n%8==0 or n%24==0:
        return True
    else:
        return numPens(n-5) or numPens(n-8) or numPens(n-24)

Answer 6

在http://en.wikipedia.org/wiki/Recursive给出的递归的非正式定义将递归定义为:"递归是当过程的一个步骤涉及调用过程本身时，过程所经历的过程。"另一方面，迭代被定义为:"迭代意味着为了达到预期的目标、目标或结果而重复一个过程的行为。"过程的每次重复也称为"迭代"，并且一次迭代的结果用作下一次迭代的起点。http://en.wikipedia.org/wiki/Itteration

正如你所看到的，这两个过程非常相似。任何非无限的循环都是迭代的，可以用递归的方式编写，任何递归调用都可以写成迭代循环。然而，在许多情况下，其中一种方法更容易实现。