1 
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

我必须为测试创建这个函数，我只是想知道问题是否可以递归排序或者什么是最有效的解决方案，我是编程新手，所以任何帮助都会很棒，谢谢。

4

6 回答 6

6 
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

这是解决问题的最直接的方法，并且对于较小的数字相当有效。对于大量数字，由于它多次评估相同数字的方式，它会很慢。留给读者的优化是使用动态规划来消除重复计算。

于 2013-03-22T16:08:53.853 回答
3

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

例如，您可以添加

if n > 40: 
    return True

作为您的基本案例之一！

您可以通过维护其余值 (n < 40) 的查找表来提高效率。

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

于 2013-03-22T17:04:24.667 回答
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)

如果您需要更高效和更健壮，您可以自己改进。

于 2013-03-22T16:19:18.267 回答
1

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)
于 2013-03-22T17:00:59.137 回答
0 
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)
于 2013-03-22T17:14:24.587 回答
0

http://en.wikipedia.org/wiki/Recursive给出的递归的非正式定义将递归定义为：“当过程的步骤之一涉及调用过程本身时，递归是过程所经历的过程。” 另一方面，迭代被定义为：“迭代是指重复一个过程以接近预期目标、目标或结果的行为。过程的每次重复也称为“迭代”，一次迭代的结果被用作下一次迭代的起点。” http://en.wikipedia.org/wiki/Iteration

As you can see the two processes are very similar. Any loop that is not infinite will be iterative, and could be written in a recursive manner, and any recursive call could be written as an iterative loop. However in many cases one method or the other is much easier to implement.

于 2013-03-22T17:38:34.947 回答