丢番图方程实现

Question

我被要求做以下几点： 如果有可能购买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)) 

非常感谢您！

Answer 1

看起来很清楚问题是什么：只有在可以获得确切数量时才增加count。任何时候你不增加count你重置为0，并且只有当这超过6时，循环才会停止。这可能需要一段时间。

你写了一个三重嵌套for循环，所以较大的n得到，这些循环得到较慢。如果让它运行得足够久，有可能会有一天成功完成;但是你的基本算法太慢了。

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

这是你的程序，以便编辑：

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的硬币。一个简单的“贪婪”算法，从最大的硬币开始并继续工作，将始终成功。这更有趣一点，因为“硬币”的设置很奇怪，而且有些值无法找到，所以也许经典的硬币问题并不像我想象的那么相关。

Answer 2

对不起，我刚刚意识到我有颠倒的布尔值。循环开始的第一个six_consequtive应该被分配False和第二个True。 再次，我非常抱歉，这个愚蠢的问题。