python简单练习：递归解决汉尼塔问题

╰+哭是因爲堅強的太久メ 2023-02-08 15:51 11阅读 0赞

\*\*

## 汉尼塔 ##

\*\*  
这是个比较常见的问题 我就直接说了，应该都懂。

我们如何用递归解决这个问题呢?我们又如何完全解决这一类问题?基本情况又是什么?让我 们从递归调用的最底端入手。假设你有一个五个圆盘组成的塔,最开始在一号杆上。如果你已经知 道如何将有四个圆盘的小塔从一号杆移到二号杆,就可以很容易地将第五个圆盘移动到三号杆,然后将 四个圆盘的塔从二号杆移动到三号杆。但是如果你不知道如何移动有四个圆盘的塔呢?这时又假设 你知道如何将有三个圆盘的塔移到三号杆;然后你就可以将第四个圆盘移动到二号杆,然后再将位 于三号杆的有三个圆盘的塔移到其上。但是如果你不知道如何移动有三个圆盘的小塔又怎么办呢? 那考虑先将有两个圆盘的小塔移动到二号杆,再将第三个圆盘移动到三号杆,最后将两个圆盘的小塔移 动到三号杆会如何呢?但如果你连这个也不会,该如何处理?显然你知道将单个圆盘移到三号杆十 分简单甚至可以说无需思考,似乎这就是这一问题最基础的部分。

*话不多说，直接上代码：*

count = 0
    def hanoi(n, src, dst, mid):
        ''' n:圆盘数量 src:原柱子 mid:过渡柱子 dst:目标柱子 '''
        global count
        if n == 1:
            print('{}号圆盘:{}->{}'.format(n,src,dst))
            '''将1号圆盘从原柱子移到目标柱子 '''
            count += 1
        else:
            hanoi(n-1, src, mid, dst)
            '''改变形参位置，原过渡柱子成为新的目标柱子， 原目标柱子成为新过渡柱子 '''
            print('{}号圆盘:{}->{}'.format(n,src,dst))
            '''将原柱子最上面的n-1号圆盘放到目标柱子上 '''
            count += 1
            hanoi(n-1,mid,dst,src)
            '''改变形参位置，原目标柱子成为新原始柱子， 原原始柱子成为新过渡柱子'''
    hanoi(5,'a','b','c')
    print(count)

运行结果

1号圆盘:a->b
    2号圆盘:a->c
    1号圆盘:b->c
    3号圆盘:a->b
    1号圆盘:c->a
    2号圆盘:c->b
    1号圆盘:a->b
    4号圆盘:a->c
    1号圆盘:b->c
    2号圆盘:b->a
    1号圆盘:c->a
    3号圆盘:b->c
    1号圆盘:a->b
    2号圆盘:a->c
    1号圆盘:b->c
    5号圆盘:a->b
    1号圆盘:c->a
    2号圆盘:c->b
    1号圆盘:a->b
    3号圆盘:c->a
    1号圆盘:b->c
    2号圆盘:b->a
    1号圆盘:c->a
    4号圆盘:c->b
    1号圆盘:a->b
    2号圆盘:a->c
    1号圆盘:b->c
    3号圆盘:a->b
    1号圆盘:c->a
    2号圆盘:c->b
    1号圆盘:a->b
    31
    
    进程已结束，退出代码 0