牛客网NC67汉诺塔问题：递归算法解析（附完整C++代码）

一、问题背景

汉诺塔（Tower of Hanoi）是经典的递归算法问题，源于一个古老的传说。游戏规则：

1. 一次只能移动一个圆盘

2. 大圆盘不能放在小圆盘上面

3. 所有圆盘从起始柱移动到目标柱

二、算法原理

采用分治思想将问题分解：

1. 将n-1个盘子从起始柱移到辅助柱（子问题）

2. 将第n个盘子从起始柱移到目标柱（直接操作）

3. 将n-1个盘子从辅助柱移到目标柱（子问题）

三、关键点解析

1. 递归终止条件：当n=1时直接移动

2. 时间复杂度：O(2^n)，每个盘子需要2次移动

3. 空间复杂度：O(n)，递归调用栈的深度

四、完整代码

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return string字符串vector
     */
    vector<string> getSolution(int n) {
        vector<string> moves;
        hanoi(n, "left", "right", "mid", moves);
        return moves;
    }

    // 递归实现汉诺塔移动步骤
    // n: 当前要移动的盘子数量
    // from: 起始柱子
    // to: 目标柱子
    // aux: 辅助柱子
    // moves: 存储移动步骤的数组
    void hanoi(int n, string from, string to, string aux, vector<string>& moves) {
        if (n == 1) {
            // 基础情况：只有一个盘子时直接移动
            moves.push_bACk("move from " + from + " to " + to);
            return;
        }

        // 第一步：将n-1个盘子从起始柱移到辅助柱
        hanoi(n - 1, from, aux, to, moves);

        // 第二步：将第n个盘子从起始柱移到目标柱
        moves.push_back("move from " + from + " to " + to);

        // 第三步：将n-1个盘子从辅助柱移到目标柱
        hanoi(n - 1, aux, to, from, moves);
    }
};

五、示例演示

当n=3时的移动步骤：

1. left → right

2. left → mid

3. right → mid

4. left → right

5. mid → left

6. mid → right

7. left → right

六、扩展思考

1. 非递归实现方法（使用栈模拟）

2. 图形化演示汉诺塔移动过程

3. 计算最少需要多少步完成游戏（2^n -1）

七、常见误区

1. 忽视递归终止条件导致无限循环

2. 混淆三个柱子的角色转换

3. 错误估计时间复杂度

来源：牛客网NC67汉诺塔问题：递归算法解析（附完整C++代码）