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

贾蔷
• 阅读 11

牛客网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++代码)

点赞
收藏
评论区
推荐文章
Patrick Patrick
4年前
【分治法】解决中位数问题、格雷码问题以及分治法直接折半存在的问题讨论————武汉理工大学算法分析实验1
AlgorithmExperiment算法分析课实验分治法的核心思想是将问题分为若干子问题去,使规模一步步缩小,最终分到一步就能得出结果。要注意每个子问题需要性质相同而且相互不重复。采用分治法完成如下任务:i.中位数问题问题描述设X0:n1和Y0:n–1为两个数组,每个数组中含有n个已排好序的数。找出X和Y
Wesley13 Wesley13
3年前
18.12.16 DSA 吉老师的汉诺塔
描述吉老师的面前出现了一座汉诺塔!但是这个汉诺塔好像坏了,盘子并不是按照从大到小的顺序排列的……吉老师非常不开心,立志要把这个汉诺塔修好!吉老师每分钟可以交换挨在一起的两个盘子,吉老师希望用的时间最短,吉老师不会啊,你能帮帮吉老师吗?输入第一行1个整数N。第二行为N个非负整数,按从下到上的顺序给出每个盘子的大小。对于50
Stella981 Stella981
3年前
ECharts 发布第 100 个版本!
最新,ECharts发布了在GitHub上的第100个版本!!(https://oscimg.oschina.net/oscnet/up6d3bca79ee5c2aa99442c6b9b56a70079d2.png)柱状图柱条的背景色曾经,很多有「为柱状图的柱条添加背景色」需求的小伙伴,都是通过添加一个额外的系
Wesley13 Wesley13
3年前
JAVA学习入门篇_递归结构
递归结构递归是一种常见的解决问题的方法,即把问题逐渐简单化。递归的基本思想就是“自己调用自己”,一个使用递归技术的方法将会直接或者间接的调用自己。​利用递归可以用简单的程序来解决一些复杂的问题。比如:斐波那契数列的计算、汉诺塔、快排等问题。​递归结构包括两个部分:​1.定义递归头。解答:什么
贾蔷 贾蔷
1个月前
NOIP 2000 提高组 洛谷1004题(方格取数)解题思路与C++代码解析
一、题目描述简要描述题目:例如,在一个n×n的方格图中,每个格子包含一个正整数。需要选择两条从左上角到右下角的路径,路径可重复经过格子,但两条路径除起点和终点外不能相交。求两条路径数字和的最大值。二、解题思路与算法分析1.问题分析1.问题核心是求解两条不交
贾蔷 贾蔷
1星期前
动态规划实战:洛谷P1220关路灯问题最优解(附C++代码 AC100)
一、问题重述题目描述:在一条笔直的道路上安装了N盏路灯,每盏灯有位置和功率。老张从某起点出发,每秒移动1单位距离,经过的灯可以关闭(节省电量)。要求计算关闭所有灯的最小耗电量。二、算法解析1.问题建模这是一个典型的区间DP问题,需要考虑:位置信息处理耗电量
深度学习 深度学习
1星期前
动态规划进阶:牛客4802题带附件背包问题详解 | 组合优化技巧
一、问题背景与算法思路牛客4802题是一个典型的带附件的背包问题变种,要求在主件和附件存在依赖关系的情况下,选择物品组合使总价值最大化。本文通过动态规划方法,将问题转化为分组背包问题,通过预处理所有可能的组合方式来实现高效求解。二、完整代码实现(带详细注释
菜园前端 菜园前端
2年前
什么是快速排序?
原文链接:什么是快速排序(quickSort)?主要分成两部分实现,分区、递归操作。分区从数组中任意选择一个"基准",所有比基准小的元素放在基准前面,比基准大的元素放在基本后面。递归递归地对基准前后的子数组进行分区。算法步骤1.首先获取数组的第一个值(作为
菜园前端 菜园前端
2年前
什么是动态规划?
原文链接:什么是动态规划?动态规划也是算法设计的一种方法/思想。它将一个问题分解为相互重叠的子问题,通过反复求解子问题,来解决原来的问题。基础案例场景一斐波那契数列当前数等于前面两个数的和。定义子问题:f(n)f(n1)f(n2)
时间复杂度为 O(nlogn) 的排序算法 | 京东物流技术团队
归并排序归并排序遵循分治的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后合并这些子问题的解来建立原问题的解,归并排序的步骤如下:划分:分解待排序的n个元素的序列成各具n/2个元素的两个子序列,将长数组的排序问题转换为短数