解释这个河内塔解决方案(写在python)

Explain this Towers of Hanoi solution (written in python)

我正在尝试理解河内塔问题的这个特殊解决方案。这是一个递归解决方案。

A = [5, 4, 3, 2, 1]
B = []
C = []

def move(n, source, target, auxiliary, frm):
print('n here : ', n)
if n > 0:
    print('frm : ', frm, n)

    # move n - 1 disks from source to auxiliary, so they are out of the way
    move(n - 1, source, auxiliary, target, '1')

    # move the nth disk from source to target
    target.append(source.pop())

    print('n:', n)

    # Display our progress
    print(source, target, auxiliary, '##############', sep = '\n')

    # move the n - 1 disks that we left on auxiliary onto target
    move(n - 1, auxiliary, target, source, '2')

# initiate call from source A to target C with auxiliary B
move(5, A, C, B, '0')

你可以在这里看到 https://repl.it/JUzY/0

打印第一行#########后,n = 0的值变为2,这是怎么发生的?我错过了一些递归的概念吗?帮助我理解这一点。

您需要了解范围。你说 "the value of n = 0, but suddenly it becomes 2"。但是"n"不止一个,因为n的scope就是method。每次调用 move 时,该方法调用都有自己的 n 实例和自己的值。

在脚本的底部,您调用 move(5, A, C, B, '0')。在该调用中,n == 5。要做的第一件事是调用 move(n - 1, source, auxiliary, target, '1')。在 那个 调用中,n == 4。但是当它最终returns时,原来函数调用中的n仍然是5.


了解递归如何工作的一个好方法是使用纸张手动执行程序。我将使用 Post-It note 进行函数调用,并使用 notebook 进行输出。你也有你的 "model",以列表 A,B,C 的形式。由于元素四处移动,您可以用纸片或拼字游戏块来表示这些元素。

从首字母 move(4, A, C, B, '0') 开始。 (我从 4 开始,因为步数增长很快)。由于我们是调用一个函数,所以取一个新的post-it来表示函数调用,并在上面写上:

n = 4
source = A
target = C
auxiliary = B
frm = '0'

现在按照 move 的代码进行操作。在这个上面写任何 print 输出。

当您接到 move(n - 1, source, auxiliary, target, '1') 的电话时,请在 post-it 上记下您所在的行号,然后获取一个新的 post-it,并写入其中的值:

n = 4     (because 4 - 1)
source = A
target = B  (caller's auxiliary)
auxiliary = C (caller's target)
frm = '1'

将这个 放在 之前的 post 之上。被掩盖的 post- 它被再次揭露之前,您不得查看它。继续这样做,你最终会得到一堆五个 post-its。

第五个post-它有n = 0。现在,当您单步执行它的代码时,因为它以 if n > 0: 开头,所以会立即调用 returns。这个函数调用结束了,把那个post-it撕了扔掉。 n等post中的值对其他post-中的没有影响。

您记下了所在的行号,因此继续从该行手动执行代码。您将产生一些输出,然后再次调用 move——也使用 post-its 进行此移动,再次覆盖当前的 post-it 并增加您的堆栈,直到您进行调用使用 n == 0 并且可以从堆栈中删除一个项目。

如果你继续这样做,你会看到堆栈增长和收缩几次,你会到达原来的 post-它一次,打印它,然后再次增长堆栈,然后到达原来post-再说一遍,终于写完了。


post 的堆栈 - 它指出的是程序运行时的 执行堆栈 的精确模型。当您看到堆栈跟踪(即使是非递归程序)时,这就是它们所代表的。每个 post-它是一个 堆栈帧 ,局部变量的范围仅限于该堆栈帧。


Hanoi的递归解可以用英文表示为:

  • 要移动大小为零的堆栈,什么也不做
  • 通过辅助将更大的堆栈从 src 移动到目标:
    • 首先将n-1个圆盘从src移动到辅助(让他们离开)
      • 按照我们这样做的方式来做。
    • 然后将显示的光盘移动到目的地
    • 然后将n-1个圆盘从辅助移动到目标,使用src作为备用挂钩
      • 像我们这样做一样