汉诺塔问题的递归与非递归 C++ 解法

如果 n 是偶数，起点柱子 A 上的第一步移动圆盘 1 要按 A→B→C→A 的顺序。按照这个规律，我们可以在循环中判断何时结束。

下面这段代码用栈来存储每个柱子上的圆盘，并按照上述规律模拟移动：

#include <iostream>
#include <stack>
using namespace std;

int n;
char s[5] = {'0', 'A', 'B', 'C'};
stack<int> a[5];

void move(int now, int next) {
    a[next].push(a[now].top());
    printf("%d from %c to %c\n", a[now].top(), s[now], s[next]);
    a[now].pop();
}

int main() {
    cin >> n;
    for (int i = n; i >= 1; i--)
        a[1].push(i);   // 初始时 A 柱从底到顶是 n, n-1, ..., 1

    if (n % 2 == 1) {   // 奇数时交换 B 和 C 的标签，保证最终移到 C
        s[2] = 'C';
        s[3] = 'B';
    }

    while (true) {
        // 第一步：移动圆盘 1
        int next;
        for (int i = 1; i <= 3; i++) {
            if (!a[i].empty() && a[i].top() == 1) {
                if (i == 3) next = 1;
                else next = i + 1;
                move(i, next);
                break;
            }
        }

        if (a[2].size() == n || a[3].size() == n) break; // 完成

        // 第二步：在剩余两柱间做合法移动
        int other1, other2;
        switch (next) {
            case 1: other1 = 2; other2 = 3; break;
            case 2: other1 = 3; other2 = 1; break;
            case 3: other1 = 1; other2 = 2; break;
        }
        if (a[other1].empty())
            move(other2, other1);
        else if (a[other2].empty())
            move(other1, other2);
        else {
            if (a[other1].top() < a[other2].top())
                move(other1, other2);
            else
                move(other2, other1);
        }
    }
    return 0;
}

代码的核心就是循环执行两步：移动最小盘，然后做剩下两柱之间的合法移动。当某一辅助柱（B 或 C）的圆盘数达到 n 时，任务完成。奇数个圆盘时交换了 B、C 的标签，最终会全部移到 C 上，符合题目要求。

最后

非递归的栈模拟方法不限于汉诺塔，很多递归问题（如二叉树的遍历、DFS、归并排序等）都可以通过手动维护栈来实现非递归版本。理解这种转换思路，对于把握递归的本质很有帮助。