用数组实现河内递归塔算法的尝试
用数组实现河内递归塔算法的尝试
提问于 2014-12-20 15:34:43
尽管这里有很多关于这个问题的问题，但没有一个问题能帮我解决这个问题。我理解递归是什么，我可以轻松地用2^n-1移动求解河内塔，但是我很难用Python为它编写算法。基本情况是可行的，但我似乎找不到一种方法将“将n-1磁盘移动到辅助peg，然后将最大的磁盘移动到目标peg”转换为数组操作，而且我不明白为什么在递归调用中弹出最后一个元素时没有从数组中删除它。
这是一个方案：
peg_a = [1,0]
peg_b = []
peg_c = []
def hanoi(start,aux,target):
print(start,aux,target)
if len(start) == 1:
target.append(start.pop())
print(start,aux,target)
else:
hanoi(start[1:],target,aux)
target.append(start.pop())
print(start,aux,target)
hanoi(peg_a, peg_b, peg_c)这就是印出来的东西：
[1, 0] [] []
[0] [] []
[] [] [0]
[1] [0] [0]有什么帮助吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2014-12-20 15:40:47
我认为一个问题是，您的函数不返回任何内容。您可以使用lists来保存bigs的内容，这些bigs是可修改的对象，因此您可以将函数参数视为指向这些对象的指针。这可能有效，但问题是，通过使用start[1:]创建一个切片，可以创建一个新的列表，因此它不再是指向原始列表的“指针”。
一个解决办法可能是仍然使用输入参数作为指向列表的指针，而不是添加一些额外的整数函数参数，这些参数指示要移动多少磁盘。
我就是这样做的：
def hanoi(pegs, start, target, n):
assert len(pegs[start]) >= n, 'not enough disks on peg'
if n == 1:
pegs[target].append(pegs[start].pop())
print '%i -> %i: %s' % (start, target, pegs)
else:
aux = 3 - start - target # start + target + aux = 3
hanoi(pegs, start, aux, n-1)
hanoi(pegs, start, target, 1)
hanoi(pegs, aux, target, n-1)我不使用3种不同的列表，因为在您的代码中它们会被交换，所以很难想象正在发生的事情。相反，我有一个pegs变量，它是一个列表列表。在我的例子中，start和target是我交换的钉住汇率的指数。好的是，您现在可以打印各个步骤。快速演示：
pegs = [[4, 3, 2, 1], [], []]
hanoi(pegs, 0, 1, 4) 有结果
0 -> 2: [[4, 3, 2], [], [1]]
0 -> 1: [[4, 3], [2], [1]]
2 -> 1: [[4, 3], [2, 1], []]
0 -> 2: [[4], [2, 1], [3]]
1 -> 0: [[4, 1], [2], [3]]
1 -> 2: [[4, 1], [], [3, 2]]
0 -> 2: [[4], [], [3, 2, 1]]
0 -> 1: [[], [4], [3, 2, 1]]
2 -> 1: [[], [4, 1], [3, 2]]
2 -> 0: [[2], [4, 1], [3]]
1 -> 0: [[2, 1], [4], [3]]
2 -> 1: [[2, 1], [4, 3], []]
0 -> 2: [[2], [4, 3], [1]]
0 -> 1: [[], [4, 3, 2], [1]]
2 -> 1: [[], [4, 3, 2, 1], []]Stack Overflow用户
发布于 2014-12-20 15:48:49
您的代码有两个问题：
- 虽然一开始这似乎是个聪明的主意，但使用
start[1:]不起作用，因为您正在创建列表的副本，因此不再修改原始列表(请参阅Bas的答案)。 - 您缺少了
else部件中的第二个递归调用，将光盘从aux挂钩堆叠到targetpeg。
要解决第一个问题，最简单的方法是添加一个an参数，指示要从start迁移到target的磁盘数量。
def hanoi(n, start, aux, target):
if n == 1:
target.append(start.pop())
else:
hanoi(n - 1, start, target, aux)
target.append(start.pop())
hanoi(n - 1, aux, start, target)或更短：
def hanoi(n, start, aux, target):
if n > 0:
hanoi(n - 1, start, target, aux)
target.append(start.pop())
hanoi(n - 1, aux, start, target)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/27581683
复制相关文章
相似问题
腾讯云开发者
