Перебор диофантова уравнения по списку самого себя в python

Question

Я изучаю MIT Open Courseware Введение в информатику и программирование. Задача 2 включает диофантовы уравнения, основанные на подсчете сумм блоков куриных самородков (6, 9 или 20).

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

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

Итак, возьмите формулу сумм: x=0, a=x+6, b=x+9, c=x+20каждый из которых добавляется в список, который теперь выглядит следующим образом: [6,9,20], Что я тогда хочу сделать, это иметь x перейти к следующему наибольшему значению в списке, создавая новые значения для других переменных, которые также добавляются в список. Следующее значение для x было бы 6, изменяя другие переменные и получая список, который выглядит следующим образом: [6,9,20,12,15,26], Затем, 9, и так далее.

Моей первой проблемой были дубликаты и порядок списка, вызывающий бесконечные циклы. Я исправил это, добавив строку, которая создала набор списка, который снова превратился в список. Это работало в основном.

Но, и здесь есть проблема, он не заполняет список всеми возможными значениями. Например, он не помещает 48 в список, что является очевидным кратным 6.

Я предполагаю, что моя проблема связана с тем фактом, что я перебираю список, который постоянно редактируется и / или добавляется.

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

## Name some initial variables in diophantine equations
x=0
a, b, c= x+6, x+9, x+20

## Create a list to catch values, aka fish
fish = [a,b,c]
## Here goes
while x <= 60:
    for i in fish:
        x = i
        fish = list(sorted(fish))
        a, b, c= x+6, x+9, x+20
        ## option to see what its doing
        print x,a,b,c
        ## catch the values into the list
        fish.append(a)
        fish.append(b)
        fish.append(c)
        ## get rid of duplicate numbers in the list
        fish = list(set(fish))
        a, b, c= x+6, x+9, x+20


else:
    print fish
## Create new list of values NOT caught by the equation

lastMissingFish = list(set(range(0,50))-set(fish))

## Print the last number not reached by the equation
print lastMissingFish [-1]

Answer 1

Модификация той же коллекции, по которой вы выполняете итерацию, почти всегда не очень хорошая идея, поскольку итерация ожидает, что базовая коллекция не будет изменена. В частности, перебор списка в Python при его изменении, кажется, дает... странные результаты. Попробуйте изменить его для явного индексирования списка и увеличения индекса, например, так:

## Create a list to catch values, aka fish
fish = [0]
## Here goes
x, i = 0, 0
while x <= 60 and i < len(fish):
        x = fish[i]
        a, b, c = x+6, x+9, x+20
        ## catch the values into the list
        fish.append(a)
        fish.append(b)
        fish.append(c)
        ## get rid of duplicate numbers in the list.
        fish = sorted(set(fish))
        i = i + 1

Для справки, вот как бы я решил это. Все числа, которые мы хотим добавить к набору, - это те, которые можно выразить как кратное 6 +, кратное 9 +, кратное 20. Итак, давайте просто переберем их все, а затем создадим список из нашего набора с все элементы меньше или равны максимальному:

def solvechickenboxes(max, x, y, z):

    sums = set()

    for a in range((max/x)+1):
        for b in range((max/y)+1):
            for c in range ((max/z)+1):
                sums.add(a*x + b*y + c*z)

    return [x for x in sums if x <= max]

solvechickenboxes(50, 6, 9, 20)

[0, 6, 9, 12, 15, 18, 20, 21, 24, 26, 27, 29, 30, 32, 33, 35, 36, 38, 39, 40, 41
, 42, 44, 45, 46, 47, 48, 49, 50]