汉诺塔（也叫河内塔）是一个经典的递归数学谜题，由法国数学家爱德华・卢卡斯于 1883 年发明。
游戏有三根柱子（通常命名为 A、B、C）和若干个大小不同的圆盘，初始时所有圆盘按从小到大的顺序叠在起始柱子上（大的在下，小的在上）。
目标：把所有圆盘从起始柱子移动到目标柱子，必须遵守 3 条规则：
（1）每次只能移动一个圆盘；
（2）圆盘只能从一根柱子顶部挪到另一根柱子顶部；
（3）任何时候，小圆盘必须在大圆盘上面（不允许大圆盘压小圆盘）；
汉诺塔问题是学习递归最经典的案例，如果要将 n 个圆盘从 A 移动到 C，思路如下：
（1）先把上面 n-1 个圆盘从 A 移动到 B（借助 C）；
（2）把最底下 1 个最大圆盘从 A 直接移动到 C；
（3）最后把 n-1 个圆盘从 B 移动到 C（借助 A）；
这个过程会不断重复，直到只剩 1 个圆盘（递归终止条件）
下图演示了拥有 3 个圆盘从 A 移动到 C 的过程：
def hanoi(n, source, target, auxiliary):
"""
汉诺塔递归函数
:param n: 要移动的圆盘数量
:param source: 起始柱子
:param target: 目标柱子
:param auxiliary: 辅助柱子
"""
# 递归终止条件：只剩1个圆盘，直接移动
if n == 1:
print(f"移动圆盘 1 从 {source} 到 {target}")
return
# 1. 把 n-1 个圆盘从 起始柱 → 辅助柱（借助目标柱）
hanoi(n - 1, source, auxiliary, target)
# 2. 把最底下的第 n 个圆盘从 起始柱 → 目标柱
print(f"移动圆盘 {n} 从 {source} 到 {target}")
# 3. 把 n-1 个圆盘从 辅助柱 → 目标柱（借助起始柱）
hanoi(n - 1, auxiliary, target, source)
if __name__ == "__main__":
# 圆盘数量
disk_num = 3
print(f"汉诺塔 {disk_num} 个圆盘移动步骤：")
hanoi(disk_num, "A", "C", "B")运行结果：
汉诺塔 3 个圆盘移动步骤：
移动圆盘 1 从 A 到 C
移动圆盘 2 从 A 到 B
移动圆盘 1 从 C 到 B
移动圆盘 3 从 A 到 C
移动圆盘 1 从 B 到 A
移动圆盘 2 从 B 到 C
移动圆盘 1 从 A 到 C
川公网安备51010802032098