Python学习第四十四天—函数10(递归的应用——汉诺塔)

用递归实现汉诺塔
起源
汉诺塔在1883年时由法国数学家卢卡斯发明的，该数学问题与一个印度传说有关，据说在世界中心贝拿勒斯的圣庙里有一块黄铜板，上面插着三根宝针，印度教主神梵天在创造世界的时候，在其中的一根针上从上往下穿好了由小到大的64枚金片，这就是汉诺塔的原型。有一个僧侣没日没夜的移动，当所有的金片都移动到另外一根针上的时，世界就会在一声霹雳中消灭，梵塔和众生也都将同归于尽。
规则
一次只能移动一枚金片
无论在哪根针上，小片必须在大片的上面
抽象为数学问题
如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移动一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数

汉诺塔

规律：
         1个圆盘的次数：2的1次方减1
         2个圆盘的次数：2的2次方减1
         3个圆盘的次数：2的3次方减1
         。 。 。 。 。
         n个圆盘的次数：2的n次方减1
算法步骤分析：
实现这个算法可以简单分为三个步骤：
把n-1个盘子由A 移到 B；
把第n个盘子由 A移到 C；
把n-1个盘子由B 移到 C；

从这里入手，再加上上面数学问题解法的分析，可以发现
把A上（n-1）个盘子通过借助辅助塔（C塔）移到了B上，
把最大的一个盘子由A移到C上去；
把B上（n-1）个盘子通过借助辅助塔（A塔）移到了C上；

代码实现如下：
def hanoi(n,x,y,z):
    if n == 1
        print(x,'-->',z)    # 如果只有一层，直接将圆盘从x移动到z
    else:
        hanoi(n-1,x,z,y)   # 将x上的（n-1）个圆盘移动到y
        print(x,'-->',z)    # 将最底下的圆盘从x移动z
        hanoi(n-1,y,x,z)   # 将y上的（n-1）个圆盘移动到z

n=int(input("请输入汉诺塔的层数："))
hanoi(n,'A','B','C')

运行后，再互动模式下查看：
请输入汉诺塔的层数：3
A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C

要想理解递归的实现过程，必须分清形参与实参，变来变去的其实是实参。
假设n=3
第一次调用，hanoi(3,”A”,”B”,”C”)
当n=3时，x=”A”，y=”B”，z=”C”
由于n不等于1，将要执行else中的三条语句：
一、第一个语句，hanoi(2,”A”,”C”,”B”)，即当n=2时，x1=”A”，y1=”B”，z1=”C”
n不等于1，同样将要执行else中的三条语句：
1、再次进入递归调用，hanoi(1,”A”,”B”,”C”)，这一次，n终于等于1了，执行第一次打印：A --> C
2、函数返回，执行下一个语句print(x,'-->',z)，继续打印：A --> B
3、接着调用，接着舞，hanoi(1,”C”,”A”,”B”)，n再次等于1，执行第三次打印：C --> B
好了，这一级完成任务了，让它们消失吧！
二、第二条语句，继续，还是打印语句print(x,'-->',z)，打印：A --> C
三、第三条语句，hanoi(2,”B”,”A”,”C”)，当n=2时，x2=”B”，y2=”A”，z2=”C”
好了，我们剩下一个递归函数了。由于n不等于1，同样将要执行else中的三条语句：
1、再次进入递归调用，hanoi(1,”B”,”C”,”A”)，这一次，n又等于1了，执行第二轮的第一次打印：B -->A
2、函数返回，执行下一个语句print(x,'-->',z)，继续打印：B --> C
3、接着调用，接着舞，hanoi(1,”A”,”B”,”C”)，n再次等于1，执行第二轮第三次（也是最后一次）打印：A --> C
好了，这一级完成任务了，让它们消失吧！