在python中迭代丢番图方程的列表

Question

我在自学MIT Open Courseware Introduction to Computer Science and Programming。Problem Set 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语言中对列表进行迭代，同时修改它，似乎会产生have...quirky结果。尝试将其更改为显式索引列表并增加索引，如下所示：

## 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的倍数。因此，让我们迭代所有这些数字，然后在集合中创建一个列表，其中所有元素都小于或等于max：

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]