python汉诺塔的递归流程理解

小鱼儿 2022-01-28 04:15 184阅读 0赞

### 首先我们要了解它的规则： ###

**汉诺塔**（港台：**河内塔**）是根据一个传说形成的数学问题：

有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

1.  每次只能移动一个圆盘；
2.  大盘不能叠在小盘上面。

提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。

问：如何移？最少要移动多少次？

首先这是个递归的算法，在写代码的时候要进行循环嵌套，如果想了解代码执行过程的可以一步一步跟着调试，但是你首先宏观上要理解这个算法。

![20190523104202404.gif][]

这个在网上找的一个大佬做的图，先不去理解其他的，只数用了多少步，你会发现最快需要7步完成操作。

想想一下现在最左边柱子又多了一个盘子，这时最少需要多少步？

![20190523105312930.jpg][]

不需要想其他东西，就想象突然间又多了个盘子，要把所有盘子移动中间空的柱子上需要多少步？

首先把左边大盘子移到中间需要1步，这时候把右边三个移到中间和第一个图其实是一样的，需要7步，再加上右边三个盘子之前是从最左边移过来的，也需要7步，所以这时候需要7+1+7=15步。

这个时候可能大家就不理解啦，为啥要加上之前的7步，其实可以想想成最开始左边是4个盘子，只有先把上面的三个先移开，才移动对下面最大的一个，考虑到汉诺塔的规则（小盘子必须放在大盘子上面），只能先把上面3（就是n-1）层,移动到第二个柱子上，才能把最后1个盘子移动到第3个柱子。

咱们总结下规律：

三层需要：7

四层需要：a4=a3+1+a3=2xa3+1=15

五层需要：a5=a4+1+a4=2xa4+1=31

六层需要：a6=a5+1+a5=2xa5+1=63

这样总结下来算法的公式应该是![equation_tex_a_n_3D2a_7Bn-1_7D_2B1][]

### 代码实现 ###

这里使用python写的，就给大家讲一下

def move(n,a,b,c):
        if n==1:
            print(a,'-->',c)
        else:
            move(n-1,a,c,b)
            move(1, a, b, c)
            move(n-1,b,a,c)

其实咱们可以把A、B、C三个柱子宏观的抽象为分为三类：操作区a、缓冲区b、目标区c

我们的目的：将 **操作区** 的数移动到 **目标区** 里，所以函数执行只有一句话：操作区--->目标区

第一步：将 **操作区a** 前n-1个数移动到 **缓冲区b** 里，这时 **缓冲区b** 就是我们这一步的目标区；所以是move(n-1,a,c,b)

第二步：将 **操作区a** 的最后一个数移动到 **目标区c** 里，即move(1, a, b, c)

**注意**： 这时，**操作区a**的东西已经全部移动到**缓冲区b**和**目标区c**里了，**操作区a**已经为空了。 所以现在，**缓冲区b就成为了新的操作区（里头有m=n-1个数），而之前的操作区a成为了新的缓冲区**

执行返回结果
    # A --> C 
    # A --> B 
    # C --> B 
    # A --> C 
    # B --> A 
    # B --> C
    # A --> C

调试

有的同学可能想要了解下代码执行的过程，可以使用python的调试工具

python  -m  pdb   test.py

具体用法可以点击链接[https://blog.csdn.net/q\_l\_s/article/details/53376689][https_blog.csdn.net_q_l_s_article_details_53376689]

参考：

[https://www.zhihu.com/question/24385418][https_www.zhihu.com_question_24385418]

[https://www.liaoxuefeng.com/wiki/1016959663602400/1017268131039072][https_www.liaoxuefeng.com_wiki_1016959663602400_1017268131039072]

[20190523104202404.gif]: /images/20220128/0e83f856aff34c1d8fbd04061d2d2312.png
[20190523105312930.jpg]: /images/20220128/407db75506b04d32bde1d34c9329b1ae.png
[equation_tex_a_n_3D2a_7Bn-1_7D_2B1]: /images/20220128/bf1c3048bac647978864d41fb7d5cbb3.png
[https_blog.csdn.net_q_l_s_article_details_53376689]: https://blog.csdn.net/q_l_s/article/details/53376689
[https_www.zhihu.com_question_24385418]: https://www.zhihu.com/question/24385418
[https_www.liaoxuefeng.com_wiki_1016959663602400_1017268131039072]: https://www.liaoxuefeng.com/wiki/1016959663602400/1017268131039072