汉诺塔

汉诺塔（Tower of Hanoi）是一个经典的数学谜题与递归算法应用场景。它由三根柱子（通常标记为A、B、C）和若干个不同大小的圆盘组成，开始时所有圆盘按照从大到小的顺序堆叠在一根柱子（比如A柱）上，目标是将所有圆盘从起始柱子移动到另一根柱子（比如C柱），移动过程需遵循以下规则：
1.每次只能移动一个圆盘。
2.大圆盘不能放在小圆盘上面
汉诺塔问题非常适合用递归的思想来解决，具体思路如下：
1.递归的终止条件：当只有一个圆盘时，直接将这个圆盘从起始柱子移动到目标柱子即可，这就是递归的最底层情况，也就是递归终止条件。
2.递归的拆解步骤：
首先，我们需要把 n - 1 个圆盘从柱子 A 借助柱子 C 移动到柱子 B，这相当于解决了一个规模更小的汉诺塔问题（把上面 n - 1 个圆盘看成一个整体来移动），调用自身函数来处理这个子问题。
接着，将剩下的那个最大的圆盘从柱子 A 直接移动到柱子 C。
最后，再把 n - 1 个圆盘从柱子 B 借助柱子 A 移动到柱子 C，同样是调用自身来处理这个子问题。

#include
#include
using namespace std;

// 函数用于移动圆盘，参数分别表示圆盘数量、起始柱子、中间柱子、目标柱子
void hanoiTower(int n, string from, string via, string to) {
    if (n == 1) {
        // 当只有一个圆盘时，直接从起始柱子移动到目标柱子
        cout << "将圆盘 1 从 " << from << " 移动到 " << to << endl;
        return;
    }
    // 先把 n - 1 个圆盘从起始柱子借助目标柱子移动到中间柱子
    hanoiTower(n - 1, from, to, via);
    // 再把最大的圆盘从起始柱子移动到目标柱子
    cout << "将圆盘 " << n << " 从 " << from << " 移动到 " << to << endl;
    // 最后把 n - 1 个圆盘从中间柱子借助起始柱子移动到目标柱子
    hanoiTower(n - 1, via, from, to);
}

int main() {
    int numDisks;
    cout << "请输入圆盘的数量：";
    cin >> numDisks;
    // 调用函数开始解决汉诺塔问题，初始柱子为 "A"，中间柱子为 "B"，目标柱子为 "C"
    hanoiTower(numDisks, "A", "B", "C");
    return 0;
}