面试题：Python递归解决汉诺塔问题

Question

汉诺塔问题是一个经典的递归问题。有三根柱子A、B、C，在A柱上从下往上按照大小顺序摞着N个圆盘。要求把圆盘从A柱全部移到C柱，每次只能移动一个圆盘，并且在移动过程中，三根柱子上的圆盘都要保持大盘在下，小盘在上。请用Python的递归函数实现该过程，并打印出每一步的移动步骤。

Answer 1

def hanoi(n, source, target, auxiliary):
    if n > 0:
        # 将 n-1 个圆盘从 source 移动到 auxiliary，以 target 为辅助柱
        hanoi(n - 1, source, auxiliary, target)
        print(f"Move disk {n} from {source} to {target}")
        # 将 n-1 个圆盘从 auxiliary 移动到 target，以 source 为辅助柱
        hanoi(n - 1, auxiliary, target, source)


# 测试
n = 3  # 圆盘数量
hanoi(n, 'A', 'C', 'B')