当前位置:首页 > 牛客题解 > 牛客网NC67汉诺塔问题:递归算法解析(附完整C++代码)

牛客网NC67汉诺塔问题:递归算法解析(附完整C++代码)

6小时前牛客题解10

截图未命名.jpg 牛客网NC67汉诺塔问题:递归算法解析(附完整C++代码) 汉诺塔问题 递归算法 分治思想 C++实现 牛客网真题 算法复杂度 第1张

一、问题背景

汉诺塔(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. 错误估计时间复杂度


原创内容 转载请注明出处

分享给朋友:

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。