汉诺塔问题：递归算法解析及C++代码实现

汉诺塔问题：递归算法解析及C++代码实现

汉诺塔问题是一个经典的递归问题，它描述了将一堆圆盘从一根柱子移动到另一根柱子的过程，要求遵循以下规则：

• 有三根柱子，分别标记为'A'、'B'和'C'。
• 'A'柱上放置了n个圆盘，圆盘大小从上到下依次增大。
• 每次只能将一根柱子最顶端的圆盘移动到另一根柱子上。
• 大圆盘不能叠在小圆盘的上面。

目标是将所有圆盘从'A'柱移动到'C'柱，并使用最少的移动次数。

递归解题思路

汉诺塔问题的解决可以使用递归算法。核心思路如下：

1. 将最大的圆盘（第n个圆盘）从'A'移动到'C'。
2. 将剩下的n-1个圆盘从'A'移动到'B'。
3. 将最大的圆盘从'C'移动到'B'。
4. 将n-1个圆盘从'B'移动到'C'。

C++代码实现

#include <iostream>
using namespace std;

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        cout << from << '->' << to << endl;
        return;
    }
    hanoi(n-1, from, aux, to);
    cout << from << '->' << to << endl;
    hanoi(n-1, aux, to, from);
}

int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

代码解析

• hanoi函数接收四个参数：
  • n: 圆盘数量
  • from: 起始柱子
  • to: 目标柱子
  • aux: 辅助柱子
• 当只有一个圆盘时，直接将其从起始柱子移动到目标柱子。
• 否则，递归调用hanoi函数将前n-1个圆盘从起始柱子移动到辅助柱子。
• 将最大的圆盘从起始柱子移动到目标柱子。
• 再次递归调用hanoi函数将n-1个圆盘从辅助柱子移动到目标柱子。

总结

汉诺塔问题是一个经典的递归问题，其解题思路清晰简洁，代码实现也较为简单。通过学习汉诺塔问题的解法，可以加深对递归算法的理解，并掌握使用递归算法解决问题的方法。