汉诺塔递归写法
时间: 2025-06-08 11:47:12 浏览: 19
### 汉诺塔递归算法实现
汉诺塔问题是一个经典的递归问题,其核心在于通过分解问题来逐步解决问题。以下是基于C++和Python两种编程语言的汉诺塔递归算法实现。
#### C++ 实现
在C++中,可以通过定义一个`hanio`函数来实现汉诺塔问题的递归解决方案:
```cpp
#include <iostream>
using namespace std;
void hanio(int n, char A, char B, char C) {
if (n == 1) {
cout << "Put " << n << " from " << A << " to " << B << endl;
} else {
hanio(n - 1, A, C, B); // 将前n-1个盘子从A借助C移动到B
cout << "Put " << n << " from " << A << " to " << B << endl; // 移动第n个盘子
hanio(n - 1, C, B, A); // 将剩余的n-1个盘子从C借助A移动到B
}
}
int main() {
int num = 0;
cout << "Please input the number of disks:" << endl;
cin >> num;
hanio(num, 'A', 'B', 'C');
system("pause");
return 0;
}
```
上述代码展示了如何利用递归来解决汉诺塔问题[^3]。程序的核心逻辑是将较大的问题拆分为较小的问题,并逐层处理直到最简单的情况(即只有一个盘子时的操作)。
#### Python 实现
同样,在Python中也可以优雅地实现汉诺塔递归算法:
```python
def hanoi(n, source, auxiliary, target):
if n == 1:
print(f"Move disk 1 from {source} to {target}")
else:
hanoi(n - 1, source, target, auxiliary) # 将前n-1个盘子从源柱借助辅助柱移动到中间柱
print(f"Move disk {n} from {source} to {target}") # 移动第n个盘子
hanoi(n - 1, auxiliary, source, target) # 将剩余的n-1个盘子从中间接力柱借助源柱移动到目标柱
if __name__ == "__main__":
num_disks = int(input("Enter the number of disks: "))
hanoi(num_disks, 'A', 'B', 'C')
```
这段代码清晰地体现了递归的思想,其中每次调用都会进一步缩小问题规模直至达到基本情况[^4]。
#### 关键点分析
1. **递归终止条件**:当盘子数量为1时,直接将其从起始位置移动到目标位置。
2. **递归过程**:对于超过一个盘子的情况,先将顶部的\(n-1\)个盘子移动到辅助柱上;接着把当前最大的盘子放到目标柱上;最后再把之前放在辅助柱上的\(n-1\)个盘子转移到目标柱上。
3. **参数传递**:每一次递归调用都需要重新指定三个柱子的角色——起点、终点以及过渡使用的辅助柱。
问题
阅读全文
相关推荐

















