Python学习 - 汉诺塔的实现思想 （递归函数）

这两天在学习Python的基本知识，学到函数的递归调用时，用汉诺塔来举例子是一个很好的方式，这里把实现思想和代码简单说明一下。

汉诺塔 （hanoi）的由来

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

汉诺塔的原理展示

• A,B,C三个柱子，盘子在A柱子上按金字塔形状从小到大排列
• 每次只能移动一个盘子
• 任何一次移动，必须大盘子在下面，小盘子在上面
• 最后盘子按顺序从放到C上
  

###汉诺塔的移动步骤
####前提条件： 有ABC三个柱子，起初所有的盘子在A柱上（最左边），通过不断的移动，把盘子移到最右边的C柱子上。

实现步骤：

1. 只有一个盘子1
    - 把1从A直接挪到C  (A --> C)
2. 俩个盘子1,2
    - 把1从A挪到B    (A --> B)
    - 把2挪到C       (A --> C)
    - 把1从B挪到C    (B --> C)
3. 三个盘子1,2,3
    - 把上面两个借助C先移到B   (2, A-->C-->B):  这里可以不看最底下个盘子，先看上面的两个盘子，借助C先移到B，这里跟两个盘子的移动是一样的。
	- 把1 移到C  (A --> C)
        - 把2 移到B (A --> B)
	- 把1 移到B (C --> B)
    - 把最底下的盘子3移到C               
	- A --> C 
    - 把 1,2 从B借助A移到C  （1,2 在B柱）(2, B-->A-->C)
        - 把 1 移到A
        - 把 2 移到C
        - 把 1 移到C
4. N个盘子 
     - 把上面N-1个先移到B柱 （N-1，A-->C-->B）
     - 把底下第N个移到C柱    （1，A-->C）
     - 把N-1个盘借助A移到C   (N-1, B-->A-->C)

Python代码的汉诺塔实现方式

# 汉诺塔的实现方式
# n: 代表多少个盘子
# A, B, C 代表 起始盘子A，辅助盘子B，目的盘子C

#表示移动位置，从a到b
def move(a,b):
    print(a,"-->",b)
    
# 汉诺塔实现
def hanoi(n, A, B, C):
    if n == 1:
        move(A,C)
        return None
    if n == 2:
        move(A,B)
        move(A,C)
        move(B,C)
        return None
    if n >= 3:
        hanoi(n-1,A, C, B)    #上面的N-1个盘子从A上，借助C，移到B
        move(A,C)             # 把左边最底下的盘子从A移到C
        hanoi(n-1, B, A, C)   # 在B上个N-1个盘子，借助B移到C
        
# 测试
print("1个盘子")
hanoi(1,"A", "B", "C")
print("2个盘子")
hanoi(2,"A", "B", "C")
print("3个盘子")
hanoi(3,"A", "B", "C")        
print("5个盘子 ")
hanoi(5,"A", "B", "C")

思考：其实这里去掉N=2的实现，结果也是一样的，在这里多写一步N=2， 是为了代码的方便阅读。