实现汉诺(Hanoi)塔求解问题
时间: 2023-11-18 12:04:14 浏览: 37
汉诺塔问题是经典的递归问题,其基本思想是将大问题分解成小问题来解决。以下是 Python 代码实现:
```python
def hanoi(n, A, B, C):
"""
:param n: 盘子数目
:param A: 起始柱子
:param B: 借助柱子
:param C: 目标柱子
"""
if n == 1:
print(f"move disk {n} from {A} to {C}")
else:
hanoi(n-1, A, C, B)
print(f"move disk {n} from {A} to {C}")
hanoi(n-1, B, A, C)
```
其中,n 表示盘子数目,A、B、C 分别表示三个柱子,A 为起始柱子,B 为借助柱子,C 为目标柱子。当 n 为 1 时,直接将起始柱子上的盘子移动到目标柱子上;当 n 大于 1 时,将 n-1 个盘子从 A 移动到 B,再将第 n 个盘子从 A 移动到 C,最后将 n-1 个盘子从 B 移动到 C。
例如,当 n=3,A="A",B="B",C="C" 时,调用函数 `hanoi(3, "A", "B", "C")` 即可输出如下结果:
```
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
```