3

我正在自学MIT Open Courseware Introduction to Computer Science and Programming。问题集 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]
4

1 回答 1

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]
于 2013-05-03T04:26:10.700 回答