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")

打印正确的移动以解决 3 个圆盘的河内塔问题： 将磁盘从 A 移动到 B 将磁盘从 A 移动到 C 将磁盘从 B 移动到 C 将磁盘从 A 移动到 B 将磁盘从 C 移动到 A 将磁盘从 C 移动到 B 将磁盘从 A 移动到 B

我的问题是，它是如何做到的？！有人可以检查代码行，以便我了解它如何打印正确的动作吗？我主要对fpand的值如何tp从AtoB变为 to感到困惑C。对不起，如果这是一个广泛的问题！任何帮助将不胜感激！

4

5 回答 5

3

在这个简单的例子中，您可以通过使用适当的 s 来可视化发生的情况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
于 2014-04-16T11:22:34.523 回答
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)您可以将所有剩余的圆盘放在所有 3 个塔中。

因此，您将moveTower(height-2,y,z)移动第二大圆盘到其目的地，并再次移动塔高 2。

编辑：此链接中的图表最好地描述了我想说的（“一张图片值一千字”）。

如果您知道要移动塔height-1，只需执行算法中描述的 3 个步骤。moveDisc是“基本情况”（爬上第一步）， moveTower 是递归（如何从 stepn到n+1）。

于 2014-04-16T11:20:39.180 回答
0

The topic is covered here, however the recursive approach can be confusing if one is not familiar with the concept. The algorithm works by first recursively moving all but the last disc (a smaller problem instance) via the cache peg away, then "actually" moving the last disk to the destination peg and then moving the tower to the initial peg. In effect, relying on the recursion, the disk at the bottom is moved to the destination peg, which is impossible to do directly as is is no valid move. In the recursive call, the three pegs change the roles such that always an empty peg becomes the cache. This is understood best if you imagine the pegs not to be arranged in the line but in a circle. Unlike other problems, here the recursive call comes first and then the "actual" movement is done.

The question can be seen as a duplicate of this question.

于 2014-04-16T11:19:49.013 回答
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")
于 2014-04-16T11:26:03.277 回答
0 
moveTower(height-1,fromPole,withPole,toPole)

使用第三个极点将除一个之外的所有圆盘从初始极点移动到中间极点。

moveDisk(fromPole,toPole)

将最后一个圆盘从初始极点移动到最终极点。现在最后一个光盘处于正确位置，不需要移动。

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

将所有圆盘从中间极移动到最终极，如果需要，使用第一个极。

于 2014-04-16T11:27:12.640 回答