Python-汉诺塔原理分析

发布时间：2019-09-12 07:59:42编辑：auto阅读（1518）

            最近在“廖雪峰的官方网站”学习Python，遇到汉诺塔递归问题百思不得其解，先是百度了汉诺塔原理，然后查看了别人的写的文章，通过整理汇总，希望能够帮助其他人理解。

            汉诺塔原理：（来源于百度百科）

            汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

            逻辑推理

            图片:![](https://s1.51cto.com/images/blog/201801/20/7746b0650de5e627d7efc396a8749d2a.jpg?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=)

            推理逻辑：

            首先有3个柱子(A   B   C) ,A柱子有N个圆盘，假如我们圆盘按照L1-Ln表示，要将A中圆盘移动到其他柱子中去，假如为C，需要几步。规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

            假如n=1 

                         则圆盘为L1 ,只需将圆盘从A→C,共一步

            假如n=2

                        则圆盘为L1,L2 ,则需要将先将L1从A→C,然后将L2从A→B,最后将L1从C→B,共3步。

            假如n=3

                        则圆盘为L1,L2 ,L3, 先将L1从A→C,然后将L2从A→B,L1从C→B,然后将L3从A→C,然后将L1从B→A,将L2从B→C,再将A→C。

                ...

                简单思考：

                上面只是一个移动过程，如果没有图片很难理解 ，我们可以简单思考下，将所有盘片看成L1-L(n-1)和Ln两个部分。如果有n个盘片需要移动，则：

                    # 子目标1：将前n-1个盘子从a移动到b上

                    # 子目标2：将最底下的最后一个盘子从a移动到c上

                    # 子目标3：将b上的n-1个盘子移动到c上

                    实际上n-1个圆盘本身又是一个递归，一直可以分解成n=1为止。

    下面贴上代码

    # 汉诺塔思想笔记

    # 认识汉诺塔的目标：把A柱子上的N个盘子移动到C柱子

    # 递归的思想就是把这个目标分解成三个子目标

    # 子目标1：将前n-1个盘子从a移动到b上

    # 子目标2：将最底下的最后一个盘子从a移动到c上

    # 子目标3：将b上的n-1个盘子移动到c上

    # 然后每个子目标又是一次独立的汉诺塔游戏，也就可以继续分解目标直到N为1

def move(n, a, b, c):

if n == 1:

    print(a, '-->', c)

else:

    move(n-1, a, c, b)# 子目标1

    move(1, a, b, c)# 子目标2

    move(n-1, b, a, c)# 子目标3

n = input('enter the number:')

move(int(n), 'A', 'B', 'C')

​ 代码解释如下“

/**

我把3个盘子的汉诺塔全部通过代码演示，按缩进原则，每一个缩进即进一个递归函数，每打印一次即中止当前递归,也就是每个print

说明:

1.n = 3, n = 2, n = 1是每次执行if(n == 1)的结果，这里就不写判断了，相信童鞋们也能看懂，也就是n不等与1时就减1进入递归

2.请注意a,b,c柱每次进入函数的顺序，不要被形参带错路了，看准每次函数参数的实参 

**/

move(3, "a", "b", "c")

n=3:

//开始从a上移动n-1即2个盘子通过c移动到b,以腾出c供a最后一个盘子移动

move(2, "a","c","b")

n=2:

//开始进行n=2的一个递归，把当前a('a')柱上的n-1个盘子通过c('b'）移动到b('c')

    move(1, "a", "b", "c")

    n=1:

    //n=2的第一个递归完成,打印结果，执行当前子函数剩余代码

        print("a", "->", "c") 

    move(1, "a", "c", "b")

    n=1:

        print("a", "->", "b")

    move(1, "c", "a", "b")

    n=1:

        print("c", "->", "b")

　   //到这里完成了a柱上面的n-1即是2个盘子的移动

    //开始把a柱上最后一个盘子移动到c柱上

move(1, "a", "b", "c")

n=1:

    print("a", "->", "c")

    //到这里完成移动a柱上的最后一个盘子到c柱上 

move(2, "b", "a", "c")

n=2:

//开始进行n=2的第二个递归,即把当前b('b')的盘子(n-1个)通过a('a')移动到c('c')上

    move(1, "b", "c", "a")

    n=1:

    //n=2 的第二个递归完成，打印结果并执行当前子函数的剩余代码

        print("b", "->", "a")

    move(1, "b", "a", "c")

    n=1:

        print("b", "->", "c")

    move(1, "a", "b", "c")

    n=1:

        print("a", "->", "c")

        //到这里把b上的盘子通过a移动到c,

//整个代码执行完毕,汉诺塔移动完成

好吧，我承认我不会用这个博客，好多格式都没有表现出来。

​    ​你们可以参考以下几个地方：

​    ​百度百科-汉诺塔原理：https://baike.baidu.com/item/%E6%B1%89%E8%AF%BA%E5%A1%94/3468295?fr=aladdin
​    ​廖雪峰的官方网站-Python：https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000/001431756044276a15558a759ec43de8e30eb0ed169fb11000
​    Python技术交流：http://bbs.fishc.com/thread-61965-1-1.html​

​    ​递归经典案例分析：http://blog.csdn.net/hikobe8/article/details/50479669

关键字：