1

我被要求做以下事情：如果有可能购买 x、x+1、...、x+5 套 McNuggets，对于一些 x，那么有可能购买任意数量的 McNuggets >= x，给定McNuggets 有 6 包、9 包和 20 包。编写一个迭代程序，找出不能以确切数量购买的最大数量的 McNuggets。

这是我想出的代码，但它陷入了无限循环：

count = 0
n = 1
while count < 6:
    six_consequtive = True
    for a in range(n):
        for b in range(n):
            for c in range(n):
                if 6*a + 9*b + 20*c == n:
                    six_consequtive = False
    if six_consequtive:
        count += 1
    else:
        count = 0

    n += 1

print("Largest number of McNuggets that cannot be bought in exact quantity: %d." % (n - 5))

非常感谢！

4

2 回答 2

0

问题出在哪里似乎很清楚：只有count在可以获得确切数量时才增加。任何时候你不增加count你都会将它重置为 0，并且循环只会在超过 6 时停止。这可能需要一段时间。

你写了一个三重嵌套for循环，所以越大n，这些循环越慢。如果您让它运行足够长的时间，它可能会成功并在某天完成；但是您的基本算法太慢了。

您可以通过使用 print 语句检测循环来了解更多信息。当我尝试它时，我没有得到输出；我认为这可能是由于缓冲问题，所以我编写了一个简单的输出函数，它输出一个字符串，然后刷新以确保我可以立即看到输出。

这是您编辑的程序：

import sys

def out(s):
    sys.stdout.write(s + "\n")
    sys.stdout.flush()

count = 0
n = 1
while count < 6:

    six_consecutive = True
    for a in range(n):
        for b in range(n):
            for c in range(n):
                #out("a: %d b: %d c: %d  n: %d" % (a, b, c, n))
                if 6*a + 9*b + 20*c == n:
                    six_consecutive = False

    out("n == %d  count == %d  six_consecutive == %s" %
            (n, count, str(six_consecutive)))

    if six_consecutive:
        count += 1
    else:
        count = 0

    n += 1

print("Largest number of McNuggets that cannot be bought in exact quantity: %d." % (n - 5))

我还修正了“six_consecutive”的拼写。

那么，你应该如何解决这个问题？我认为你应该把它扔掉，用更好的算法重写。您可能想查看其他人如何解决此问题或类似问题。当给定一组不同面额的硬币时，这让我觉得与如何找零的经典问题非常相似。

注意：找零的经典问题通常假设一组合理的硬币，包括一个价值为 1 的硬币。一个简单的“贪婪”算法，从最大的硬币开始，向下工作，总是会成功。这有点有趣，因为“硬币”集合很奇怪，并且有些值无法找到，所以也许经典的硬币问题并不像我想象的那么重要。

于 2012-06-22T22:27:32.023 回答
0

对不起，我刚刚意识到我的布尔值颠倒了。循环开始时的第一个 Six_consequtive 应分配为 False，第二个为 True。再次，我很抱歉这个愚蠢的问题。

于 2012-06-22T22:28:12.737 回答