10-python下汉诺塔的递归实现

汉诺塔简介：

大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

def print_move(char):  # 打印移动步骤
    global count
    count += 1
    if count < 20:  # 移动次数太多就不打印出来了
        print(char,",",end="")
    
def hanoi(n,char="a-->c"):
    if n == 1:
        print_move(char)
        
    elif char == "a-->c":   # 如果本层是a向c移动
        hanoi(n-1,"a-->b")   # 那么上一层a向b移动
        print_move("a-->c")    # 上一层移动完成后 移动本层
        hanoi(n-1,"b-->c") # 本层移动完成后 上一层移动到本层之上
        
    elif char == "b-->c":  # 如果本层是b向c移动      
        hanoi(n - 1, "b-->a") # 那么上一层要b向a移动
        print_move("b-->c")   # 上一层移动完成后 移动本层
        hanoi(n - 1, "a-->c")  # 本层移动完成后 移动上一层
        
    elif char == "b-->a":
        hanoi(n - 1, "a-->c")
        print_move("b-->a")
        hanoi(n - 1, "c-->a")  # 本层移动完成后 移动上一层
        
    elif char == "a-->b":
        hanoi(n - 1, "a-->c")
        print_move("a-->b")  # 上一层移动完成后 移动本层
        hanoi(n - 1, "c-->b")  # 本层移动完成后 移动上一层
        
    elif char == "c-->b":
        hanoi(n - 1, "c-->a")
        print_move("c-->b")  # 上一层移动完成后 移动本层
        hanoi(n - 1, "a-->b")  # 本层移动完成后 移动上一层
        
    elif char == "c-->a":
        char = "c-->b"  # 上一层向b移动
        hanoi(n - 1, char)
        print_move("c-->a")  # 上一层移动完成后 移动本层
        hanoi(n - 1, "b-->a")  # 本层移动完成后 移动上一层


count = 0 # 用于统计移动次数
n = int(input("请出入汉诺塔的层数"))
hanoi(n)
print("")
print("总共移动了%d步"%count)

运行效果：
请出入汉诺塔的层数4
a-->b ,a-->c ,b-->c ,a-->b ,c-->a ,c-->b ,a-->b ,a-->c ,a-->c ,b-->a ,c-->a ,b-->c ,a-->b ,a-->c ,b-->c ,
总共移动了15步

最后编辑于：2018.07.25 19:14:28