Python-汉诺塔原理分析

jrgf

最近在“廖雪峰的官方网站”学习Python，遇到汉诺塔递归问题百思不得其解，先是百度了汉诺塔原理，然后查看了别人的写的文章，通过整理汇总，希望能够帮助其他人理解。　　汉诺塔原理：（来源于百度百科）
　　汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
　　逻辑推理
　　图片:
　　推理逻辑：
　　首先有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