,将辅助柱上的 num-1 圆盘移动到目标柱上,整个过程的实现可以借助起始柱 hanoi(n
时间: 2024-09-29 09:01:56 浏览: 35
汉诺塔是一个经典的递归问题,它涉及到三个柱子和若干个大小不等的圆盘。游戏的目标是从第一个柱子(源柱)将所有圆盘按照从小到大的顺序移到第三个柱子(目标柱),过程中任何时候都不能让大盘的圆盘放在小盘上面。
当 n=1(只有一个圆盘)时,非常简单,直接从源柱移动到目标柱即可。如果有更多圆盘(num-1个),则需要遵循递归策略:
1. 将前 n-1 个圆盘从源柱 A 移动到辅助柱 C,通过中间柱 B 辅助。
2. 将第 n 个圆盘从源柱 A 直接移动到目标柱 D。
3. 再次将步骤 1 中的 n-1 个圆盘从辅助柱 C 按照原路径移动回目标柱 D,此时目标柱上已经有了 n 个圆盘。
这个过程可以用递归函数描述,例如在 Python 中,可以这样实现:
```python
def hanoi(n, source, auxiliary, target):
if n > 0:
# Step 1: Move n - 1 disks from source to auxiliary
hanoi(n - 1, source, target, auxiliary)
# Step 2: Move the nth disk directly to target
print(f"Move disk {n} from {source} to {target}")
# Step 3: Move the n - 1 disks from auxiliary to target
hanoi(n - 1, auxiliary, source, target)
# Call the function with initial parameters
hanoi(num-1, 'A', 'B', 'D')
```
阅读全文