python汉诺塔问题超级详细教程_汉诺塔问题递归算法实现过程反映出盘子的分布情况 python

作者：weixin_40725706 | 2024-06-10 06:07:32

踩

汉诺塔问题递归算法实现过程反映出盘子的分布情况 python

一、这是一道非常经典的练习题。

问题描述如下：

现在有 n 个圆盘从上往下从小到大叠在第一根柱子上，要把这些圆盘全部移动到

第三根柱子要怎么移动，汉诺塔问题的以下几个限制条件：

1.在小圆盘上不能放大圆盘。

2.在三根柱字之间一回只能移动一个圆盘。

3.只能移动在最顶端的圆盘。

如何输入圆盘的个数，输出移动的过程呢？

二、这种问题肯定是使用递归算法。我们可以想象最简单的模型，三个圆盘。

过程是这样的：三个圆盘按大小命名为为大、中、小。

1.现将A柱上的三个圆盘中的小圆盘放在C柱上。A--->C

2.再将A柱上的中圆盘放在B柱上。A--->B

3.再将C上的小圆盘放在B柱上。C---->B

4.再将A柱上剩余的大圆盘放在C柱上。A---->C

5.再将B柱上面的小圆盘放在A柱上。B---->A

6.再将B柱上面的中圆盘放在C柱上。B---->C

7.再将A柱上面的小圆盘放在C柱上。A----->C

三、再拓展到4个圆盘：小、中、大、超大

1.将A柱上的小、中、大三个圆盘放到B柱。为了不破坏从大到小的规则，所以需要借助C柱。

2.再将剩下超大圆盘放到C柱。（完成1个圆盘了）

3.此时A柱是空的，B柱上有三个圆盘，所以此时的A柱就变成了B柱，B柱变成了A柱。

4.在重复移动三个圆盘的过程就可以了。

我们可以看到这其实是一个循环，知识第一块和第二块的第四次移动开始不同，是反过来的。

四、再拓展到n个圆盘：

1.将A柱上n-1个圆盘借助C柱移动到B柱。

2.将A柱上最大的一个圆盘放到C柱。此时完成了一个圆盘，剩下就是处理n-1个圆盘的问题了。

3.此时n-1个圆盘在B柱，A柱是空的。

4.依旧是借助C柱（因为C柱上面是最大的圆盘，可以放剩下n-1圆盘的任意一个）将n-2个圆盘移动到A柱。这个过程就是将A,B两个柱的功能进行了互换。

五、总结流程：

1.借助C柱现将除最大圆盘外的其他圆盘从A移动到B。(a, c, b)

2.当剩余一个圆盘时，将圆盘从A移动到C(a, b, c)

3.此时b柱有圆盘，A柱为空，调换A,B柱的功能。(b, a, c)

六、代码：


def move(n, a='A', b='B', c='C'):
    if n == 1:
        print('移动{}的一个圆盘到{}'.format(a, c))
        return
    move(n-1, a, c, b) # 移动n-1个盘子，从a移动到b，借助c
    move(1, a, b, c) # 剩下一个盘子从a移动到c
    move(n-1, b, a, c) # 将柱子b上的n-1个圆盘，借助a柱(此时a柱为空)，移动到c
floor = int(input('请输入圆盘层数:'))
move(floor)

以上理解仅供参考，欢迎指正！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/697469