求和:需要递归,递归算法是什么样的？

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

这是解决问题最直接的方法,对于小数字也能很好地工作.对于大数字,由于它多次评估相同数字的方式,它将很慢.留给读者的优化是使用动态编程来消除重复计算.