汉诺塔问题： 古代有一个梵塔，塔内有三个基座，A,B,C，开始时A基座上有64个盘子，盘子的大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从A基座上移动到B基座上，但每次只允许移动一个盘子，且在移动过程中，3个基座上的盘子都始终保持着大盘在下，小盘在上。移动过程中可以利用C基座做辅助。

此问题又被称为“世界末日问题”，因为以最高效的移动（无不必要的移动）方法，以每秒移动一次的速度，64 个盘子也需要近580亿年的时间。

'''
算法：大规模转化为小规模问题，把上面的n-1个盘子看做一个小盘子，那就只有两个盘子，转化成移动两个盘子的问题。
    第一步：把上面n-1个盘子借助B基座先移动到C基座上
    第二步：把最底下那个盘子移动到B基座
    第三步：再把C基座上的n-1个盘子借助A基座移动到B基座上
    
    记作hanoi(n,a,b,c):a，b，c不代表固定的基座，根据移动次数变化
        n：问题的规模，盘子的个数
        a：代表每次移动时的起始基座
        b：代表每次移动时的终点基座
        c：代表每次移动时的辅助基座
        
    则此问题的步骤：
        第一步：hanoi(n-1,a,c,b)
        第二步：把最下面的那个大盘子从起点基座移动到终点基座
        第三步：hanoi(n-1,c,b,a)
'''

def hanoi(n,a,b,c):
    if n > 0:
        hanoi(n-1,a,c,b)
        print("%d号盘子：%s ----> %s" %(n,a,b))
        hanoi(n-1,c,b,a)

def main():
    n = int(input("请输入n的值："))
    hanoi(n,"A","B","C")

if __name__ == "__main__":
    main()

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30

运行结果：

请输入n的值：3
1号盘子：A ----> B
2号盘子：A ----> C
1号盘子：B ----> C
3号盘子：A ----> B
1号盘子：C ----> A
2号盘子：C ----> B
1号盘子：A ----> B

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8