汉诺塔问题

汉诺塔——经典递归问题（python实现）

问题背景

汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

问题分析

假设总共需要移动n个盘子:

1. 将A柱上的n-1个盘子借助C柱移向B柱
2. 将A柱上仅剩的最后一个盘子移向C柱
3. 将B柱上的n-1个盘子借助A柱移向C柱

图解

代码实现

import math  # 导入math模块，用于计算步数

# 定义一个移动盘子的函数
def move(a, b):
    print(f"将{a}上的盘子移动到{b}")  # 打印移动盘子的信息

# 定义汉诺塔问题的递归函数
def Hanoi(n, a, b, c):
    # 基本情况：如果只有一个盘子，直接将其从a移动到c
    if n == 1:
        move(a, c)
    else:
        # 递归调用：将n-1个盘子从a移动到b，使用c作为辅助
        Hanoi(n - 1, a, c, b)
        # 将剩下的一个盘子从a移动到c
        move(a, c)
        # 递归调用：将之前移动到b的n-1个盘子从b移动到c，使用a作为辅助
        Hanoi(n - 1, b, a, c)

# 从用户那里获取塔的层数
m = int(input('请输入塔的层数:'))
# 计算步数，汉诺塔问题的步数是2的m次方减1
step = int(math.pow(2, m) - 1)
# 调用Hanoi函数开始移动盘子
Hanoi(m, 'A', 'B', 'C')
# 打印总共需要的步数
print(f'一共需要{step}步')

运行结果

请输入塔的层数:3
将A上的盘子移动到C
将A上的盘子移动到B
将C上的盘子移动到B
将A上的盘子移动到C
将B上的盘子移动到A
将B上的盘子移动到C
将A上的盘子移动到C
一共需要7步