汉诺塔第m步求解：递归分治思想与C++实现-北京尧图网络

1. 题目理解与整体思路拆解1.1 汉诺塔基础回顾汉诺塔问题对我来说算是老朋友了每次刷OJ碰到它都有种“去年今日此门中”的感觉。这道东华OJ-基础题-128题面很直接给你一个经典的汉诺塔游戏三根柱子n个盘子要求输出移动过程中的第m步操作。乍一听好像比“输出全部步骤”要简单但真正动手做起来才会发现这里面藏着一个挺有意思的思维坎。先花30秒回忆一下汉诺塔的规则三根柱子A、B、C初始时所有盘子按从大到小的顺序摞在A柱上一次只能移动一个盘子任何时候大盘子不能压在小盘子上面目标是把整摞盘子挪到C柱。递归解法是每个学编程的人都会背的那套逻辑要把n个盘子从A挪到C先借助C把上面n-1个盘子从A挪到B再把最大的盘子从A挪到C最后借助A把n-1个盘子从B挪到C。这套递归逻辑本身不复杂代码也就五六行。但东华OJ这道题的刁钻之处在于它不问你“总共移动多少步”也不问你“完整移动序列是什么”而是直接指定一个m问第m步到底是“从哪根柱子到哪根柱子”。如果你老老实实生成完整移动序列再取第m项小数据量下完全没问题但题目显然希望你去思考能不能不生成完整序列直接定位到第m步1.2 第m步问题的本质我第一眼看到这个题的时候脑子里冒出来的想法是“这不就是递归模拟吗”。顺着这个思路写代码思路倒是很清晰定义一个递归函数参数带一个计数器cnt每次执行一步移动就cnt加一当cnt等于m时输出当前步骤。这种做法没有任何思维难度本质上就是“模拟剪枝”——即使理论上会遍历很多无效分支但一旦找到第m步就立刻停止递归不会白白浪费大量时间。不过这道题既然标注了“难度中”还专门点明“递归”那就说明单纯的模拟可能不是出题人想考察的重点。我后来仔细琢磨了一下这道题的核心考点其实有两个层次第一层能不能熟练写出汉诺塔的递归过程这是基本功。第二层能不能理解递归过程内在的数学结构也就是“第m步出现在哪个递归子问题里”。打个比方你在电影院找座位一种方式是拿着票从头到尾走一遍把整排座位都数一遍才找到自己的位置另一种方式是直接看票上的排号和座位号穿过大厅拐个弯就到了。第m步的定位问题本质上就是在问你能不能直接从m的值推算出它对应的“排号和座位号”。如果理解了这一层这道题就有很多种完全不同的解法难度也各不相同。我会在下面详细拆解这些路径。无论你选哪一种思路都需要先对“汉诺塔递归过程的分层结构”有一个直觉上的把握这一层想通了代码怎么写都顺手。2. 核心细节解析与递归原理2.1 递归的分治思想每一层都在拆子问题汉诺塔的递归代码几乎是教科书级的“分治思想”案例。我见过不少初学者代码能背下来但问一句“为什么n-1个盘子要借助C柱挪到B柱”就卡住了。其实关键在于角色转换柱子名字虽然是固定的但在每一层递归里它们的“身份”是动态变化的。考虑move(n, from, via, to)这个函数它的含义是把n个盘子从from借助via挪到to。分解步骤是先递归调用move(n-1, from, to, via)把上面n-1个盘子从from挪到via注意此时via是“目标”to是“中转”然后执行一步实际操作把一个盘子从from挪到to最后递归调用move(n-1, via, from, to)把n-1个盘子从via挪到to此时from是“中转”。这里面的关键点是整个n个盘子的移动过程只有中间那一步是“真实移动最大的盘子”其余n-1个盘子的移动全是递归子问题。也就是说一次完整的move(n)调用在全局视角看起来就是第一步到第moveTotal(n-1)步正在处理n-1个盘子的子问题第moveTotal(n-1)1步最大的盘子从from到to 第moveTotal(n-1)2步到第moveTotal(n)步另一个n-1个盘子的子问题。其中moveTotal(k) 2^k - 1也就是k个盘子全部挪完所需的总步数。这个公式怎么来的递推关系是T(1)1T(n)2*T(n-1)1解出来就是2^n-1。n3时是7步n4时是15步n64时是18446744073709551615步这个数量级的概念在后面会派上用场。2.2 移动次序的数学规律第m步落在哪一层还是以三个盘子为例完整的移动序列是第1步A→C1号盘最小的第2步A→B2号盘第3步C→B1号盘第4步A→C3号盘最大的第5步B→A1号盘第6步B→C2号盘第7步A→C1号盘注意第4步这是三盘汉诺塔中唯一一次挪动最大盘3号盘的步骤也是整个过程的“分水岭”。它前面有3步后面有3步两边恰好都是两盘汉诺塔的完整子序列。再往深了想n个盘子的汉诺塔第(2^(n-1))步一定是对最大盘的一次唯一移动。如果你要找的m恰好等于2^(n-1)那答案直接就出来了。如果m小于这个值说明第m步发生在“把n-1个盘子从A借助C挪到B”这个子问题里如果m大于这个值说明第m步发生在“把n-1个盘子从B借助A挪到C”这个子问题里。于是这个题就变成了一个“剥洋葱”的过程每次根据m和目标柱子之间的关系判断当前属于哪个子问题然后进入下一层递归。每一层剥下去n减小1m要么保持不变m在左侧子问题里要么减去左侧子问题的总步数m在右侧子问题里。剥到最底层时n等于1m必然等于1这时候就是那一层唯一的移动操作。这个思路的奇妙之处在于你根本不需要模拟盘子的实际移动过程也不需要记录任何状态。每一步的结果完全由递归的“路径”决定而这个路径又完全由m的数值决定。说白了m就是一张“地图”上的路径编码。2.3 三种解法思路对比针对这道题我梳理出三种常见解法各有优劣适合不同场景解法核心思想时间复杂度优点缺点模拟剪枝法递归模拟完整过程输出到第m步就停止O(2^n)最坏但实际剪枝思路直白不容易写错递归深度大时浪费较多计算二进制映射法根据m的二进制特征确定盘号与移动方向O(log m)常数级复杂度非常巧妙推导过程对新手不友好分治定位法利用moveTotal(n-1)判断m属于左/右侧子问题逐层剥开O(n)逻辑清晰与递归思想贴合需要理解递归子问题结构我个人的建议是如果你是来学递归的一定要把第三种“分治定位法”吃透因为它和汉诺塔递归本身的思维方式完全一致理解了它你对递归的把握会上一个台阶。第二种“二进制映射法”作为扩展阅读了解一下能开阔眼界但不必强行掌握。3. 实操过程与C实现3.1 基础递归框架先写出标准汉诺塔不管用哪种思路一个能正确输出全部移动步骤的汉诺塔递归函数是基本功。下面这段C代码是标准模板我有一个习惯每次用它之前先在纸上手推一遍n3的过程确认输出的7步符合预期再往里面加逻辑。#include iostream using namespace std; // 将n个盘子从 from 借助 via 移动到 to void hanoi(int n, char from, char via, char to) { if (n 1) { cout from - to endl; return; } hanoi(n - 1, from, to, via); cout from - to endl; hanoi(n - 1, via, from, to); } int main() { int n; cin n; hanoi(n, A, B, C); return 0; }你注意看这里的三个字符参数‘A’、‘B’、‘C’在每一层递归中会不断交换位置。第一行输出“A - C”是把A柱最上面的小盘子直接挪到C柱这个我第一次写的时候根本想不通——不是说好借助C把上面的盘子挪到B吗怎么第一步又跑到C上去了这里其实是一个很容易踩的坑三根柱子是环形的不是线性的。当n等于3时move(3, A, B, C)的第一步是move(2, A, C, B)而这又拆成move(1, A, B, C)——把1号盘从A挪到C。整个过程完全符合规则只是“路径”看起来很绕。这也是为什么我建议你运行一遍标准代码把输出结果和手工推导对照起来看比死记代码要有用得多。3.2 求解第m步的完整代码现在回到128题的核心。我采用“分治定位法”来写最终版本。先放出完整代码再逐步讲解#include iostream using namespace std; int cnt; int n; long long m; // 计算k个盘子完成移动所需的总步数 long long totalSteps(int k) { return (1LL k) - 1; } // src: 源柱 via: 中转柱 dst: 目标柱 k: 当前要移动的盘子数量 void findKthStep(int k, char src, char via, char dst, long long m) { if (k 1) { // 只剩一个盘子第m步必然就是它 cnt; if (cnt m) { cout src - dst endl; } return; } long long leftSteps totalSteps(k - 1); if (m leftSteps) { // 第m步在左侧子问题把k-1个盘子从src借助dst挪到via findKthStep(k - 1, src, dst, via, m); } else if (m leftSteps 1) { // 第m步恰好是当前层最大盘子的移动 cnt leftSteps 1; cout src - dst endl; } else { // 第m步在右侧子问题把k-1个盘子从via借助src挪到dst findKthStep(k - 1, via, src, dst, m - leftSteps - 1); } } int main() { cin n m; findKthStep(n, A, B, C, m); return 0; }这段代码的核心逻辑全在findKthStep这个函数里。注意两个细节第一我有一个多余但无害的cnt变量它实际上只在k1的分支里累加而在“m恰好等于leftSteps1”的分支里我直接把它赋值成leftSteps1这样做是为了让代码在逻辑上有一个“位置”的概念方便你对照标准输出理解。去掉cnt也不会影响正确性保留它纯粹是为了可读性。第二moveTotal用(1LL k) - 1来计算注意这里用了long long因为题目里n的上限可能到30甚至更大2的30次方是1073741824而2的40次方就超过一万亿了int根本扛不住。3.3 关键代码详解剥洋葱的每一层我们来手动走一遍n3、m5这个case看看这段代码到底怎么运作的。初始调用findKthStep(3, A, B, C, 5)。leftSteps 2^2 - 1 3。m55 leftSteps1即5 4所以m落在右侧子问题。递归调用变为findKthStep(2, B, A, C, 5-3-11)。注意这里的变化源柱变成了B目标柱变成了C中转柱变成了A而新的m是1。这意味着第5步这个全局步骤在以B为起点、C为终点的两盘汉诺塔子问题里恰好是它的第1步。接着findKthStep(2, B, A, C, 1)。leftSteps 2^1 - 1 1。m1恰好等于leftSteps所以m落在左侧子问题。递归调用变为findKthStep(1, B, C, A, 1)。再往下k1进入出口分支输出“B - A”。与我们前面列出的完整序列一一对照第5步确实是B→A完美命中。你看整个过程代码其实没有真正“移动”任何盘子它只做了一件事根据m的大小判断目标步骤在哪棵子树上然后沿着这条路径走到叶子节点。这就像查字典一样不需要把整本字典背下来只需要根据拼音/部首一路翻到目标页码即可。我额外说一下cnt变量的作用。如果你把cnt删掉然后把出口分支改成直接输出代码也没问题。但我保留它的原因是调试的时候你可以把它打出来和标准汉诺塔的逐步输出对照一旦发现某个分支的cnt值对不上很容易定位是哪一层左侧/右侧判断出了问题。对于竞赛代码来说可调试性也是一个很重要的维度。3.4 补一个模拟剪枝版本的实现方便你对照如果你觉得上面的分治定位法有点绕或者你只是为了快速过题那么模拟剪枝法也能AC。这个版本的优点是代码逻辑完全跟着递归走几乎不可能因为思路问题写错。#include iostream using namespace std; int n; long long m; long long cnt 0; bool found false; void hanoi(int k, char src, char via, char dst) { if (found) return; if (k 1) { cnt; if (cnt m) { cout src - dst endl; found true; } return; } hanoi(k - 1, src, dst, via); if (found) return; cnt; if (cnt m) { cout src - dst endl; found true; return; } hanoi(k - 1, via, src, dst); } int main() { cin n m; hanoi(n, A, B, C); return 0; }这个版本的时间复杂度在最坏情况下是O(2^n)也就是当m接近总步数时前面的步骤全都要模拟一遍。好在找到了之后立刻剪枝返回不会模拟到结尾。对于OJ上通常给的n范围比如n≤302^30大约是10亿最坏情况下C跑这个量级会超时但如果n只有10几这个版本完全够用。所以这里有个策略判断如果题目给了n的上限而且这个上限比较大就不建议用模拟版本。4. 常见问题与排查技巧实录4.1 边界条件m1和mtotalSteps这道题最容易翻车的地方就是边界条件。我一开始写分治定位法的时候m恰好等于leftSteps和恰好等于leftSteps1这两个分支我总是搞混导致提交一次WA一次后来把所有情况列成一张表才彻底理清。假设当前递归层次是k那么整个move(k)过程分成三段区间含义操作1 ~ totalSteps(k-1)左侧子问题进入findKthStep(k-1, src, dst, via, m)totalSteps(k-1)1当前层最大盘的唯一移动直接输出src → dsttotalSteps(k-1)2 ~ totalSteps(k)右侧子问题进入findKthStep(k-1, via, src, dst, m - totalSteps(k-1) - 1)所以在代码里判断顺序很重要先判断m是否≤leftSteps注意这里用小于等于把等号划归到左侧再判断m是否恰好等于leftSteps1最后是剩余情况。如果把第一段写成m leftSteps那么mleftSteps时就会掉到第二个分支输出结果就错了。另一个容易踩坑的点是m的类型。题目说m是一个正整数但没明确说范围。我建议一律用long long接收因为int在32位系统上最大值约21亿而汉诺塔的总步数在n31时就达到21亿以上了。我之前在本地测试时用int没有问题换了一组n35的数据就瞬间溢出输出完全乱掉。这种坑属于“平时遇不到遇到就是WA一整版”的类型。4.2 递归深度与性能分治定位法的递归深度其实只有n层每次递归做的是常数次操作所以时间复杂度是O(n)空间复杂度是O(n)递归栈。这一点比模拟法优秀太多。但要注意n层递归意味着递归栈的深度也在n如果n很大比如30或者40这个深度完全在C的安全范围内不用担心爆栈。真正需要担心的是totalSteps(2)这种计算时用到的位运算。1LL k这种写法在k63的时候会溢出但汉诺塔的n一般不会超过30所以实际场景中基本不会踩到这个坑。不过写代码时养成好习惯用long long且控制k的范围总是没错的。我还遇到过一个问题在Windows的OJ系统上有些老旧编译器不支持1LL这种写法。如果你用Visual C 6.0那种古董环境建议改成(long long)1 k或者干脆写一个循环计算幂值long long power2(int k) { long long res 1; for (int i 0; i k; i) res * 2; return res - 1; }4.3 调试技巧用标准序列验证你的输出我每次写完这道题不会直接交OJ而是先在本地跑一个“全量模式”来验证写一个普通的汉诺塔递归函数输出完整序列然后再调用findKthStep分别查询第1步、第2步……直到最后一步比较两个函数输出的是否完全一致。这一招帮我抓到了无数的分支判断错误。具体做法很简单在main函数里加一个循环for (long long i 1; i totalSteps(n); i)每次调用findKthStep并把输出重定向到一个文件里再用标准递归函数生成完整序列两者逐行diff。如果全对基本可以放心交OJ。我第一次写这个验证脚本的时候真的发现了一个很隐蔽的问题——在k1的出口分支里我忘了把cnt加一导致第m步输出总是比标准序列早了一步。另外我再分享一个我常用的“单步观察”技巧如果你想深入理解递归的走法可以在findKthStep的入口处加一行cerr输出打印当前k、src、via、dst和m的值。运行一次n3的case看看输出的日志顺序你会直观地看到递归是如何一层一层“剥”下去的。这个技巧比单步调试更快也更容易建立直觉。4.4 常见报错与解决方案速查现象可能原因解决方案小数据通过大数据WAint溢出全部改用long long特别是m和totalSteps输出多了前缀步数未正确剪枝/递归把所有步骤都打出来了检查是否在找到目标步后立刻返回避免后续递归输出为空m大于总步数题目保证m合法但可在代码入口处加一个if (m (1LLn)-1) return 0;防御在k1分支输出错误cnt更新顺序不对先cnt再比较或者直接输出src→dst不依赖cnt左侧/右侧子问题判断混乱对totalSteps(k-1)的区间理解不清晰手工推导n3的完整序列用表格方式标注每个步骤属于哪一段5. 从这道题延伸出去的思考5.1 为什么不建议背模板代码我发现很多同学刷OJ时有个习惯碰到递归题就把汉诺塔模板背下来换了个问法就不知道怎么改。这道题就是个很好的反例——同样是汉诺塔如果你只是机械地背下了“三步走”的模板那你大概只能写出模拟剪枝法但如果你理解了“每层递归的三个区间”你就能自然地想到分治定位法。我始终觉得刷题不是为了AC那个绿色的对勾而是为了建立一种“问题结构的直觉”。汉诺塔这个模型非常有意思它其实是一种极其工整的递归结构整体问题分解成两个同构子问题加一个常数操作这正是分治思想最纯粹的体现。理解了这道题像快速排序、归并排序、二叉树遍历这类“递归套递归”的算法你再看就会有“不过如此”的感觉。5.2 二进制映射法的彩蛋最后我再提一嘴前面说过的二进制映射法它算是这道题的一个彩蛋。汉诺塔问题和二进制的关联非常经典n个盘子的汉诺塔总步数是2^n-1而每一步移动的盘号恰好等于“当前步数m的二进制表示中从最低位开始第一个1的位数”。比如m5二进制是101从最低位往上数第0位是1所以这一步动的是1号盘最小盘。再比如m6二进制是110第0位是0、第1位是1所以动的是2号盘。这个规律我第一次知道的时候真的被惊艳到了。但我要提醒你这个规律虽然优美推导起来却需要花不少功夫而且和“借助中转柱”的过程中盘子的移动方向也有一套循环规律。对我来说这种发现属于“拿到AC之后锦上添花的彩蛋”不建议你在比赛时花时间现场推导。如果你感兴趣可以在一个n4的完整序列上手动标记每个步骤的盘号和方向你会看到那个规律像钟表一样精确地循环着。这也是我特别喜欢汉诺塔这道题的原因——它不只是一道OJ题更像是一个藏着数学玩具的小盒子。

汉诺塔第m步求解：递归分治思想与C++实现

相关推荐

非标自动化设计中的多轴建模与iRobotCAM应用

基恩士CV-X400接入PROFIBUS DP：GSD文件安装与I/O映射实战指南

京东销量预测源码拆解：特征工程与RNN/GBDT融合实践

更多资讯

端到端自动驾驶算法全解析：从原理到工程落地

从扫码到具身支付：机器狗如何打通AI交易闭环

C#/VB与三菱FX5U PLC通过SLMP协议实现以太网通讯交互

T型NPC光伏并网系统设计与仿真实践

紧急车辆警报器声音数据集构建：采集、清洗与识别模型训练

Android代码混淆技术：R8核心机制与Gradle配置详解

今日更新

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？