编写递归函数求解汉诺塔问题
时间: 2023-08-04 22:02:37 浏览: 55
好的,下面是递归函数求解汉诺塔问题的 Python 代码实现:
```python
def hanoi(n, source, target, helper):
# 当只有一个盘子时,直接移动到目标柱子上
if n == 1:
print(f"Move disk 1 from {source} to {target}")
return
# 将 n-1 个盘子从源柱子移动到辅助柱子上
hanoi(n-1, source, helper, target)
# 将第 n 个盘子从源柱子移动到目标柱子上
print(f"Move disk {n} from {source} to {target}")
# 将 n-1 个盘子从辅助柱子移动到目标柱子上
hanoi(n-1, helper, target, source)
# 测试代码
hanoi(3, "A", "C", "B")
```
解释一下代码的逻辑:
- 当只有一个盘子时,直接将它从源柱子移动到目标柱子上;
- 当有 n 个盘子时,先将 n-1 个盘子从源柱子移动到辅助柱子上,再将第 n 个盘子从源柱子移动到目标柱子上,最后将 n-1 个盘子从辅助柱子移动到目标柱子上。
在测试代码中,我们将有 3 个盘子的汉诺塔问题的源柱子命名为 A,目标柱子命名为 C,辅助柱子命名为 B。运行代码后,函数将输出如下结果:
```
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
```
这表示在最少的步骤内,将 3 个盘子从源柱子 A 移动到目标柱子 C。