汉诺塔问题的递归解法及Python实现

解答汉塔问题 并用python解释

汉诺塔问题（Tower of Hanoi）是一个经典的递归问题。问题的描述如下：

有三根柱子，A、B、C，A柱子上有n个大小不一的圆盘，圆盘从上到下依次增大。目标是将所有圆盘从A柱子移动到C柱子，移动过程中遵循以下规则：

1. 每次只能移动一个圆盘。
2. 任何时刻都不能将较大的圆盘放在较小的圆盘上。

汉诺塔问题的递归解法

汉诺塔问题的解决方案可以通过递归来实现。基本思路如下：

1. 将前n-1个圆盘从A柱子移动到B柱子，使用C柱子作为辅助柱子。
2. 将第n个圆盘（最大的圆盘）从A柱子移动到C柱子。
3. 将B柱子上的n-1个圆盘移动到C柱子，使用A柱子作为辅助柱子。

Python 实现

下面是用Python实现汉诺塔问题的代码：

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    # Step 1: Move n-1 disks from source to auxiliary, using target as auxiliary
    hanoi(n - 1, source, auxiliary, target)
    # Step 2: Move the nth disk from source to target
    print(f"Move disk {n} from {source} to {target}")
    # Step 3: Move n-1 disks from auxiliary to target, using source as auxiliary
    hanoi(n - 1, auxiliary, target, source)

# 调用函数，假设有3个圆盘
hanoi(3, 'A', 'C', 'B')

代码解释

1. 函数定义：hanoi(n, source, target, auxiliary)，其中n是圆盘的数量，source是源柱子，target是目标柱子，auxiliary是辅助柱子。
2. 基本情况：如果只有一个圆盘（n == 1），直接将其从源柱子移动到目标柱子。
3. 递归步骤：
   • 首先将n-1个圆盘从源柱子移动到辅助柱子。
   • 然后将第n个圆盘从源柱子移动到目标柱子。
   • 最后将n-1个圆盘从辅助柱子移动到目标柱子。

运行结果

当你运行上述代码时，输出将显示每一步的移动过程。例如，对于3个圆盘，输出将是：

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

这表示如何将圆盘从柱子A移动到柱子C。