Python第60题：汉诺塔：打印移动步骤（递归）

题目

求解经典汉诺塔问题（Hanoi Tower）：有三个柱子 A、B、C，将 n 个盘子从 A 柱借助 B 柱移动到 C 柱，每次只能移动一个盘子且大盘不能压在小盘上方，使用递归打印出全部移动步骤。

输入格式：一行输入一个正整数 n，表示盘子总数。

输出格式：按步输出形如 A->C 的移动路径，每步占一行。

数据范围与约定：1 ≤ n ≤ 10。

思路与算法

1. 分治递归三步法
① 递归将上面 n-1 个盘从 source 移到 helper；
② 直接将底部最大的第 n 号盘从 source 移到 target；
③ 递归将 n-1 个盘从 helper 移到 target。

2. 递归终止条件
当 n == 1 时直接打印一步移动并返回。

完整程序

# 汉诺塔经典递归：将 n 个圆盘借助 aux 从 fr 移动到 to
def hanoi(n, fr, to, aux):
    if n == 1:
        print(f'{fr}->{to}')
        return
    # 第一步：把上面 n-1 个盘子从 fr 挪到 aux
    hanoi(n - 1, fr, aux, to)
    # 第二步：把最大的第 n 号盘子直接从 fr 挪到 to
    print(f'{fr}->{to}')
    # 第三步：把 aux 上的 n-1 个盘子经 fr 挪到 to
    hanoi(n - 1, aux, to, fr)

n = int(input())
hanoi(n, 'A', 'C', 'B')

运行示例

输入：

2

输出：

A->B
A->C
B->C