MIT OCW 6.00's Chicken McNugget program ... снова

Question

Я провел немного времени, читая предыдущие вопросы/ответы о задаче MIT OpenCourseWare 6.00 о программе для определения максимального недостижимый количество куриных McNuggets в пакетах из 6, 9 и 20. К сожалению, мне трудно интегрировать эти ответы в код, который я пытался сделать самостоятельно.

Во-первых, здесь фактическая формулировка проблемы установить, что я пытаюсь написать код:

... мы можем написать исчерпывающий поиск, чтобы найти наибольшее количество McNuggets, которые не могут быть куплены в точное количество. Формат поиска должен, вероятно, следовать этому контуру:
• Гипотезировать возможные экземпляры чисел McNuggets, которые нельзя точно купить, начиная с 1
• Для каждого возможного экземпляра, называемого n, проверьте, существуют ли неотрицательные целые числа a , b и c, так что 6a + 9b + 20c = n. (Это можно сделать, просмотрев все возможные комбинации a, b и c)
• Если нет, n нельзя купить в точном количестве, сохраните n
• Когда вы нашли шесть последовательных значений n, которые на самом деле пройти тест на точное решение, последний ответ, который был сохранен (не последнее значение n, у которого было решение), является правильным ответом, так как по теореме вы знаете, что любая сумма больше также может быть куплена в точном количестве. Напишите итеративную программу, которая найдет наибольшее количество McNuggets, которые нельзя купить в точном количестве. Ваша программа должна распечатать ответ в следующем формате (где вместо (n) указано правильное число): «Наибольшее количество McNuggets, которые нельзя купить в точном количестве: (n)»
Подсказка: ваша программа должна следовать выше.

(теорема ссылается в основном говорит, что, как только у вас есть шесть допустимых значений п в строке, вы можете добавить шесть на них на неопределенный срок и не будет не более недопустимые значения п.)

Это мой код:

n = 1         #set first value for trying to solve the equation 
savedn = []       #list for holding values of n w/ no integer solution 
consecutivecount = 0 
while consecutivecount < 6: 
    for a in range(0,n): 
     for b in range(0,n): 
      for c in range(0,n): 
       if 6*a + 9*b + 20*c == n: 
        consecutivecount += 1 
       else: 
        #NOW A MIRACLE HAPPENS!!! 
        consecutivecount = 0  #resets consecutivecount value to zero 
        savedn += [n]    #adds current value of n to list 
       n += 1      #increases value of n to continue test loop 
print 'Largest amount of McNuggets that cannot be bought in exact quantity:',str(savedn[-1])+'.' 

Мои трудности:

1. Как вы можете видеть, я застрял в самом центре этого, где указано. Я вижу другие вопросы/ответы для этой проблемы с помощью bools, но я не уверен, почему кто-то это делает. Действительно ли у меня есть, чтобы использовать bools? И почему? В принципе, я был бы признателен за помощь в эффективной работе для «else».

2. Я не уверен, действительно ли я правильно использовал сохраненный список. Когда я запускал тестовые сегменты этого кода, я знаю, что я явно добавляю значения в список, но некоторое подтверждение, что это правильный способ использования «savedn + = [n]», было бы неплохо.

Я все еще знаю очень мало команд, и я очень ржавый математические навыки, так как и мой последний вопрос из этого курса, пожалуйста, предположим, что я идиот в ответ. С другой стороны, если то, что я пытаюсь сделать выше, просто безнадежно не важно, не стесняйтесь ясно предлагать, как я должен начинать с нуля.

Спасибо и извиниться за длину - другие обсуждения этого вопроса просто не казались достаточно полными, чтобы быть полезными. (И также извиняется за то, что для этого требуется Python 2.5.)

Answer 1

Вы почти там. Предположим, что вопрос «найти решение о том, что нужно делать, чтобы получить« n »McNuggets»? У вас есть ядро, что и мог бы решить этот вопрос с чем-то вроде:

solution = (0,0,0) 
for a in range(0,n): 
    for b in range(0,n): 
     for c in range(0,n): 
      if 6*a + 9*b + 20*c == n: 
       solution = (a,b,c) 

Теперь, все, что вам нужно сделать, это окружить это ведение бухгалтерского учета, как у вас есть:

while consecutivecount < 6: 
    solution = (0,0,0) 
    # ** find a solution like above 
    if solution == (0,0,0): 
     consecutivecount = 0  #resets consecutivecount value to zero 
     savedn += [n]    #adds current value of n to list 
    else: 
     consecutivecount += 1 
    n += 1      #increases value of n to continue test loop 

Так что вы ищите решение для n, и если вы его нашли, вы подсчитываете consecutivecount, и если вы его не нашли, вы сберете еще один недостижимый номер (и сбросите consecutivecount). В любом случае, время переходить к другому n.

Answer 2

Я использовал itertools.чтобы избежать 3 глубоких гнезд для петель. Это означает, что я могу легко выйти из цикла

from itertools import product, count 

v = [6,9,20] 
min_v = min(v) 
miss = 0 

for n in count(1): 
    for w in product(range(n), repeat=len(v)): 
     if sum(i * j for i, j in zip(v, w)) == n: 
      break 
    else: 
     miss = n 
    if n == miss + min_v: 
     break 

print miss 

Это делает тестирование кучу случаев, которые не нужны, как заметил @Joran в комментариях по этому вопросу. Следующий способ избежать тех случаев, создав product несколько иначе

from itertools import product, count 

v = [6,9,20] 
min_v = min(v) 
miss = 0 

for n in count(1): 
    for w in product(*(range(1 + n // i) for i in v)): 
     if sum(i * j for i, j in zip(v, w)) == n: 
      break 
    else: 
     miss = n 
    if n == miss + min_v: 
     break 

print miss 

Если используется параметр шага в диапазоне, это может быть еще более упрощена в этом

from itertools import product, count 

v = [6,9,20] 
min_v = min(v) 
miss = 0 

for n in count(1): 
    for w in product(*(range(0, n + 1, i) for i in v)): 
     if sum(w) == n: 
      break 
    else: 
     miss = n 
    if n == miss + min_v: 
     break 

print miss 

Answer 3

Вот обобщенная версия, которая будет работать для любого количества частей:

def solution_exists(amt, pieces, i=None): 
    """ 
    Return True if any whole multiples of pieces[:i+1] sum to amt, else False 
    """ 
    if i is None: 
     i = len(pieces) - 1 # start with last item 
    p = pieces[i] 
    if i: 
     return any(solution_exists(amt - p*k, pieces, i-1) for k in range(amt // p + 1)) 
    else: 
     return amt % p == 0 

def find_max_unbuyable(pieces): 
    least = min(pieces) 
    n = 0 
    last_unsolved = None 
    consecutive = 0 
    while consecutive < least: 
     n += 1 
     if solution_exists(n, pieces): 
      consecutive += 1 
     else: 
      last_unsolved = n 
      consecutive = 0 
    return last_unsolved 

def main(): 
    pieces = [6, 9, 20] 
    max_unbuyable = find_max_unbuyable(pieces) 
    print("Largest number of McNuggets that cannot be bought in exact quantity: {n}".format(n=max_unbuyable)) 

if __name__=="__main__": 
    main() 

find_max_unbuyable является довольно прямо вперед; это довольно много шаг за шагом из описания проблемы.

solution_exists более активно; это рекурсивный тест выполнимости. Для каждого пакета, начиная с последнего и работая с первым, он вычисляет максимально возможный номер, который можно купить (amt // p), а оставшееся количество штук для покупки (amt - p*k). Затем он призывает себя к уменьшению субасмиссии. Если подзадача решена, то проблема решена, и any сокращает оценку и возвращает значение True. Для базового случая (i == 0, мы смотрим на последний пакет) мы возвращаем True, если оставшаяся сумма равномерно делится на p (amt % p == 0).

Существует два преимущества для написания solution_exists таким образом: во-первых, это более эффективное решение (итерация как можно меньше времени, выполнение последней части как модульного деления вместо другой итерации, короткое замыкание, как только решение найдено); во-вторых, поскольку он рекурсивный, он с радостью будет работать на сколь угодно большом количестве пакетов.