汉译英： Towers of Hanoi Python - 理解递归

Question

汉译英： Towers of Hanoi Python - 理解递归

5

我完全是Python的新手，目前正在学习关于汉诺塔和递归的教程。我以为我理解了递归，直到他们给了这个例子：

def moveTower(height,fromPole, toPole, withPole):
    if height >= 1:
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole)
        moveTower(height-1,withPole,toPole,fromPole)
    #print(withPole)

def moveDisk(fp,tp):
    print("moving disk from",fp,"to",tp)


moveTower(3,"A","B","C")

以下是解决三个圆盘汉诺塔问题的正确移动步骤：

从A移动圆盘到B 从A移动圆盘到C 从B移动圆盘到C 从A移动圆盘到B 从C移动圆盘到A 从C移动圆盘到B 从A移动圆盘到B

您的问题是，它是如何做到这一点的？有人可以看一下代码行，以便我了解它如何打印正确的移动步骤吗？我主要困惑于fp和tp的值如何从A更改为B再到C。抱歉如果这是一个比较广泛的问题！任何帮助都将不胜感激！

- heather

也许这个答案有帮助：https://dev59.com/MHM_5IYBdhLWcg3wzmgw#1223334 - AbcAeffchen

我建议将 print(height, fromPole, toPole, withPole) 放在顶部，看看会发生什么！ - jonrsharpe

非常感谢所有回答我的人！现在我对自己的理解更有信心了 :) - heather

5个回答

2

以下是它的功能。起始位置为：

A|321
B|
C|

然后使用moveTower(2,fromA,toC, withB)，结果如下：

A|3
B| 
C|21

那么，moveDisk(fromA, toB) 的作用是

A|
B|3
C|21

最后，moveTower(2,fromC,toB)结束了游戏

A|
B|
C|321

那是河内塔的通常解决方案：将高度为h-1的塔移动到withPole，将最大的盘子移动到endPole，然后再将高度为h-1的塔移动到endPole。这样做是因为你可以将高度为h-1的塔上的每个盘子都放在最大的盘子上。要执行moveTower(height-1,w,x)，你可以把所有剩余的盘子都放在三个塔中。所以你将会先执行moveTower(height-2,y,z)，然后将第二大的盘子移到它应该在的位置，最后再次移动高度为height-2的塔。编辑：在此链接中的图表最能描述我想说的话（“图片胜过千言万语”）。如果你知道如何移动一个高度为height-1的塔，只需按照算法中描述的三个步骤执行即可。moveDisc是“基础情形”（爬上第一步），而moveTower是递归（如何从步骤n转移到n+1）。

- fredtantini

0

你应该打印每个 moveTower 调用以查看其参数的变化。递归通常通过参数传播更改。序列号有助于显示顺序（当然，控制台上的打印也是有序的）。

def seq_nummer():
    num = 0
    while True:
        num += 1
        yield num

seq_num = seq_nummer()

def moveTower(height, fromPole, toPole, withPole):
    print("seq: %d" % seq_num.next())
    print("height: %d, fromPole: %s, toPole: %s, withPole: %s" % (height, fromPole, toPole, withPole))
    if height >= 1:
        moveTower(height-1, fromPole, withPole, toPole)
        moveDisk(fromPole, toPole)
        moveTower(height-1, withPole, toPole, fromPole)

def moveDisk(fp,tp):
    print("moving disk from",fp,"to",tp)

moveTower(3,"A","B","C")

- dilbert

0

moveTower(height-1,fromPole,withPole,toPole)

将初始柱上除了一个盘子以外的所有盘子移动到中间柱上，使用第三个柱子。

moveDisk(fromPole,toPole)

将最后一个圆盘从初始柱移动到目标柱。现在，最后一个圆盘已经处于正确的位置，不需要再移动。

moveTower(height-1,withPole,toPole,fromPole)

将所有盘子从中间的柱子移动到最终的柱子，必要时使用第一个柱子。

- Abhishek Bansal

0

该主题已在此处讨论过，但如果一个人不熟悉该概念，则递归方法可能会令人困惑。算法的工作方式是首先通过缓存针递归地移动除了最后一个盘子之外的所有盘子（一个较小的问题实例），然后“实际”将最后一个盘子移动到目标针，然后将塔移动到初始针。实际上，在依赖递归的情况下，底部的盘子被移动到目标针，这是直接移动无法完成的。在递归调用中，三个针改变角色，以便始终使空针成为缓存。如果您将针不是排成一行而是排成一个圆圈来想象，那么这一点就最容易理解了。与其他问题不同的是，递归调用先于“实际”移动。

该问题可以看作是此问题的重复。

- Codor

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- pentadecagon · Accepted Answer

在这种简单的情况下，您可以通过使用适当的print进行可视化，例如：

def moveTower(height,fromPole, toPole, withPole):
    if height >= 1:
        print( "    "*(3-height), "moveTower:", height, fromPole, toPole )
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole,height)
        moveTower(height-1,withPole,toPole,fromPole)
    #print(withPole)

def moveDisk(fp,tp,height):
    print("    "*(4-height), "moving disk", "~"*(height), "from",fp,"to",tp)


moveTower(3,"A","B","C")

输出结果为：

moveTower: 3 A B
     moveTower: 2 A C
         moveTower: 1 A B
             moving disk ~ from A to B
         moving disk ~~ from A to C
         moveTower: 1 B C
             moving disk ~ from B to C
     moving disk ~~~ from A to B
     moveTower: 2 C B
         moveTower: 1 C A
             moving disk ~ from C to A
         moving disk ~~ from C to B
         moveTower: 1 A B
             moving disk ~ from A to B