尝试用数组实现Hanoi算法的递归塔

本文介绍了尝试用数组实现Hanoi算法的递归塔的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

即使这里有很多关于此问题的问题，但没有一个问题帮助我解决了这个问题。我知道递归是什么，我自己可以轻松地以2 ^ n-1的动作解决河内塔，但是我在用Python编写算法时遇到了麻烦。基本情况可行，但我似乎找不到一种将将n-1个磁盘移动到辅助钉子，然后将最大的磁盘移动到目标钉子转换为数组操作的方法，而且我不明白为什么最后一个元素不会在递归调用中将其弹出时从数组中删除。

Even though there's plenty of questions about this problem here, none of them have helped me clear this up. I understand what recursion is and I can easily solve Towers of Hanoi by myself in 2^n-1 moves, but I'm having trouble writing an algorithm for it in Python. The base case works but I can't seem to find a way to translate "move n-1 disks to the auxiliary peg and then the largest disk to the target peg" into array operations, and I don't understand why the last element isn't getting removed from the array when I pop it in the recursive call.

这是程序：

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]

有帮助吗？

推荐答案

我认为问题是您的函数不返回任何内容。您可以使用列表来保存big的内容，big是可修改的对象，因此您可以将函数参数视为指向这些对象的指针。这可能有效，但问题是，通过使用 start [1：] 进行切片，您将创建一个新列表，因此它不再是指向该对象的指针

I think one problem is that your function does not return anything. You use lists to hold the contents of the bigs, which are modifyable objects, so you could see the function arguments as pointers to those objects. This might work, but the problem is that by making a slice with start[1:], you create a new list, so it is no longer a 'pointer' to the original list.

一种解决方法可能是仍然使用输入参数作为指向列表的指针，而不是添加一些额外的整数函数参数，这些参数指示要移动多少磁盘。

One workaround might be to still use the input arguments as pointers to the lists, but than add some extra integer function arguments, which indicate how many disks to move.

这就是我要怎么做：

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 是钉的索引，我将其交换。令人高兴的是，您现在可以打印各个步骤。快速演示：

I do not use 3 different lists, since in your code they get swapped around, so it is hard to visualize what is happening. Instead, I have a single pegs variable, which is a list of lists. In my case, start and target are the indices of the pegs, which I swap around. The nice thing is that you can now print the individual steps. Quick demonstration:

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], []]