第一次在东华OJ上看到128这道题我心里想的是汉诺塔这不是递归入门题吗直接一个递归把所有移动打印出来不就完了。结果交上去不是超时就是WA翻车翻得明明白白。后来我才意识到这道题问的根本不是“怎么把汉诺塔移完”而是“整棵递归执行树的第m个动作到底是什么”。它考的是你能不能精确命中递归过程中的某一个瞬间而不是把整棵递归树从头到尾完整走一遍。这篇文章就围绕这个“命中瞬间”展开用C实现递归解法再把几种不同的优化思路一并讲透。1. 题目拆解当汉诺塔不再问“总共几步”而是问“第m步发生了什么”1.1 经典汉诺塔模型回顾汉诺塔问题的标准描述是三根柱子A、B、Cn个大小不同的圆盘初始全部套在A柱上按照从大到小、自下而上的顺序排列。目标是把所有盘子移动到C柱并且整个过程只能遵守两条规则一次只能移动一个盘子大盘任何时候都不能压在小盘上面。经典问题的答案是移动步数为2^n - 1当n3时一共7步n4时15步n10时1023步。很多入门教程都会给一个最简单的递归打印程序把每一步移动打印出来。但东华OJ这道题加了一个限制条件只输出第m步发生了什么。这个改动让题目从“枚举全过程”变成了“定位执行序列中的某一个原子操作”。这个区别很重要。如果题目让你把所有步骤都输出那么全模拟就是标准答案没有任何问题。可如果只问你第m步你再从头到尾生成一遍所有移动就多做了大量无用功。当n20时全模拟要输出超过100万步勉强还能跑n30时直接超过10亿步全模拟在OJ上基本就是超时警告。所以这道题的本质是要求你理解递归执行过程中“步数”这个维度的分布规律。1.2 为什么这道题被标记为“难度中”很多人看到“递归”两个字就觉得是送分题实际上这道题有四个隐藏难点。第一个难点是计数位置。每一步移动在递归代码里到底是在哪里发生的是进入递归函数的时候还是递归调用结束之后如果计数位置放错整个输出全部错位。第二个难点是提前终止。全模拟递归会把2^n - 1步全部跑完就算你在第m步输出了结果递归也不会自动停下来它还会继续执行子问题。第三个难点是递归参数轮换。汉诺塔递归的精髓在于柱子角色不断互换左子树、根节点、右子树分别处理的是不同的问题规模。第四个难点是数据范围。n稍微大一点2^n - 1这个数字就会超过int范围处理不好就是溢出。把这些点都解决掉代码虽然只有几十行但思维量不小。这就是题目难度“中”的由来。1.3 东华OJ的输入输出特性刷东华OJ基础题库有一个很实际的感受很多题都支持多组输入而且不会在题目里额外强调。128这道题我见过的主流写法是输入两个整数n和m表示n个盘子询问第m步操作直到EOF结束。如果你只写一次cin n m即使算法全对OJ也只会给你WA因为后续数据根本没有读进去。输出格式也值得提前确认。常见的输出有“第m步把x号盘从from移到to”也有“move disk x from from to to”之类的英文格式。建议交题前仔细核对样例输出的空格、冒号、换行。我在OJ上因为输出多了一个空格被罚过太多次现在养成了先复制样例输出到本地对比的习惯。2. 递归的执行轨迹步数究竟在哪一层产生2.1 递归函数的三段式结构要正确定位第m步首先得知道每一步是在递归的哪个位置产生的。标准汉诺塔递归函数可以写成这样void hanoi(int n, char from, char tmp, char to) { if (n 1) { // 移动1号盘这一步算一次移动 cout from - to endl; return; } // 第一段把上面n-1个盘子从from借助to移到tmp hanoi(n - 1, from, to, tmp); // 第二段把第n个最大盘子从from移到to cout from - to endl; // 第三段把tmp上的n-1个盘子从tmp借助from移到to hanoi(n - 1, tmp, from, to); }这个函数的结构可以拆成三个动作先递归处理前n-1个盘子的移动再移动当前最大盘最后再递归处理另外n-1个盘子的移动。注意三段式里的第一段和第三段本身会继续产生大量移动它们不是“一步”而是“一组步”。步数的计数器应该加在每次真正发生移动的位置也就是cout那一行前后。如果你把计数器加在函数入口那每进入一层递归都会多计一次结果完全错乱。2.2 用n3手动推一遍完整轨迹纸上推演n3的所有移动能把递归结构看得非常清楚。三根柱子分别叫A、B、C三个盘子编号1、2、3最终要把它们从A移到C。从hanoi(3, A, B, C)开始进入第一段执行hanoi(2, A, C, B)这个子问题要把2个盘子从A借助C移到B。进入它的第一段执行hanoi(1, A, B, C)第1步1号盘 A-C。移动第2个盘子第2步2号盘 A-B。进入它的第三段执行hanoi(1, C, A, B)第3步1号盘 C-B。回到最外层移动第3个盘子第4步3号盘 A-C。进入最外层第三段执行hanoi(2, B, A, C)这个子问题要把2个盘子从B借助A移到C。进入它的第一段执行hanoi(1, B, C, A)第5步1号盘 B-A。移动第2个盘子第6步2号盘 B-C。进入它的第三段执行hanoi(1, A, B, C)第7步1号盘 A-C。整个过程用表格记下来规律很直观步数移动的盘子移动方向11号盘A - C22号盘A - B31号盘C - B43号盘A - C51号盘B - A62号盘B - C71号盘A - C注意第4步也就是总步数正中间的那一步移动的是最大盘3号这一步是整个递归最外层的“根动作”。第4步之前的所有步骤都在为这一步做铺垫第4步之后的所有步骤都在做善后。而这种“中轴对称”的结构正好是后面剪枝优化的数学基础。2.3 全局计数器与“递归不会自动停止”的麻烦找到第m步之后你面临的下一个问题是递归还在继续跑。比如n3m2当递归打印完第2步后后面还有5步要执行。如果你不做任何处理程序会继续往下递归直到所有步数跑完。最简单的解决方案是用一个全局计数器cnt每次移动时递增当cnt m时记录结果然后给整个递归设置一个“停止开关”。这个开关可以是一个bool found变量。在递归入口处先判断if (found) return;这样一旦找到目标后续所有递归调用都会快速返回不会继续生成任何多余的移动。这个方案直观、容易理解适合作为第一版AC代码。但它有一个明显短板它仍然会把前m-1步全部模拟出来。如果m本身就很大比如n60m接近2^60全模拟依然会超时。所以我们需要后续的进阶方案。3. C实现正常思路下的全模拟加中途截停3.1 可直接提交的完整代码先给出一版最直接的C实现。这版代码的重点是全局计数器、递归入口的提前终止、以及基准条件的处理。#include iostream using namespace std; int cnt 0; int m; bool found false; void hanoi(int n, char from, char tmp, char to) { if (found) return; if (n 1) { cnt; if (cnt m) { cout 第 cnt 步把 n 号盘从 from 移到 to endl; found true; } return; } hanoi(n - 1, from, to, tmp); if (found) return; cnt; if (cnt m) { cout 第 cnt 步把 n 号盘从 from 移到 to endl; found true; return; } hanoi(n - 1, tmp, from, to); } int main() { int n; while (cin n m) { cnt 0; found false; hanoi(n, A, B, C); } return 0; }注意每次处理一组新输入前都要把cnt和found重置。不然上一组数据的状态会污染下一组这是多组输入最容易犯的错误。代码里我把输出写成了中文格式实际提交时需要按OJ题目要求调整。如果题目要求英文格式比如“move disk 1 from A to C”替换cout里的字符串即可。3.2 为什么计数要放在移动发生的位置有一个新手很容易踩的坑把cnt放在递归调用之前。比如写成这样void hanoi(int n, char from, char tmp, char to) { if (n 1) { cnt; ... } cnt; // 错误示范位置 hanoi(n - 1, from, to, tmp); ... }这么写的后果是每次进入递归函数时都会先多计一次步数被整体提前。更麻烦的是n 1的基准分支和普通分支都各自计数导致计数逻辑混乱。正确的做法是每一次“移动一个盘子”对应唯一一次计数。在代码里“移动”这个动作体现在两个位置一是n 1时的那次打印二是递归函数中间那条打印语句。计数器与打印语句绑定在一起而不是与函数调用绑定在一起这是这道题计数正确的前提。3.3 用全局标志提前终止的利与弊found标志位方案的好处是代码直观、不容易出错任何学过递归的人都能快速写出。坏处是它在找到答案后仍然依赖每层递归入口的return判断无法跳过“已经执行到一半的递归调用栈”中的剩余逻辑。但在实际OJ的数据范围内只要n不是特别大这个方案完全够用。如果n在20以内全模拟加中途截停的运行时间几乎可以忽略不计。真正需要担心的场景是n超过30这时候2^n - 1已经上亿即便中途截停跑到第m步之前的代价也可能非常可怕。因此你需要第5节的剪枝思维来兜底。4. 第一次交题最容易踩的四个坑4.1 盘子总数溢出int范围2^n - 1这个数字在n31时就已经超过int的最大值n63时超过unsigned long long的范围实际上2^63-1刚好等于long long的上限n64就会溢出。虽然这道题的m大概率不会给到那么极端但写代码时养成好习惯很重要。如果你需要判断m是否合法不要用pow(2, n)因为浮点数在n很大时会丢失精度。直接用移位运算long long total (1LL n) - 1;注意1LL是long long类型的1这样左移结果不会溢出int。如果n很大甚至要考虑用unsigned long long或做额外保护否则只能放弃判断合法性直接信任题目数据。4.2 递归参数传反导致的错位汉诺塔递归的参数轮换很容易写反。hanoi(n - 1, from, to, tmp)和hanoi(n - 1, tmp, from, to)这两行前者是把前n-1个盘子移到辅助柱后者是把前n-1个盘子从辅助柱移到目标柱。一旦把tmp和to的顺序搞混输出序列会整体错位而且很难靠肉眼排查出来。我的习惯是在函数定义里就把三个参数命名成from、tmp、to再加上注释。移动最大盘的那行永远是从from到to如果写成from到tmp那第一段递归和中间移动的目标就矛盾了整个问题根本不可能收敛。检查递归参数时可以拿n2的样例手推几行很快就能发现问题。4.3 多组输入没处理导致WA东华OJ的很多基础题都采用“多组输入直到EOF”的模式128题我印象里也一样。while (cin n m)是标准写法但有人会忘记每次循环重置全局状态。假设第一次查询后found变成了true第二组输入进来时递归入口直接if (found) return;结果什么都不输出白白WA一次。正确的做法是在每次循环体开头重置状态while (cin n m) { cnt 0; found false; hanoi(n, A, B, C); }4.4 输出格式和题目要求不一致OJ判题用的是逐字符比对多一个空格、少一个冒号、大小写不一致都会判WA。最稳妥的方法是把题目样例输出原样复制下来对比自己的输出逐字符检查。我遇到过一种情况题目要求输出“第m步”但我写成了“第m步:”差别就是全角冒号和半角冒号肉眼几乎看不出来OJ照样毫不留情地WA。这种错误特别浪费感情建议提交前先看讨论区有没有人提醒过输出格式的坑。5. 进阶优化利用“三段式结构”直接命中第m步5.1 汉诺塔的分段结构前段、中线、后段回到递归执行轨迹。对于hanoi(n, from, tmp, to)它处理的总步数是2^n - 1。这三个部分其实可以精确划分为左半段前2^(n-1) - 1步内容是“把n-1个盘子从from借助to移到tmp”。中间点第2^(n-1)步内容是“把第n个盘子从from移到to”。右半段后2^(n-1) - 1步内容是“把n-1个盘子从tmp借助from移到to”。这个分段是严格数学意义上的不是经验规律。因为递归定义本身就决定了这三个子问题的执行顺序和步数。基于这个结构我们可以直接判断第m步落在哪一段然后只进入对应的分支。这样每一层递归都能把问题规模缩小一半时间复杂度从O(2^n)降到了O(n)。5.2 剪枝递归实现下面是基于分段结构的递归代码。它本质上还是递归但不会执行任何多余的移动。#include iostream using namespace std; void hanoi(int n, char from, char tmp, char to, long long m) { long long half (1LL (n - 1)) - 1; if (m half) { // 第m步在左半段处理前n-1个盘子, 从from借助to移到tmp hanoi(n - 1, from, to, tmp, m); } else if (m half 1) { // 第m步正好是最大盘的移动 cout 第 m 步把 n 号盘从 from 移到 to endl; } else { // 第m步在右半段换算成右半段中的新步数 hanoi(n - 1, tmp, from, to, m - half - 1); } } int main() { int n; long long m; while (cin n m) { hanoi(n, A, B, C, m); } return 0; }注意当n1时half (1LL 0) - 1 0此时m只能是1直接命中m half 1分支输出1号盘的移动。所以这个函数不需要单独的if (n 1)基准条件逻辑照样正确。为什么右边递归里要把m减去half 1因为右半段是从总步数的第half 2步开始的而右半段内部的第一步对应递归子问题的第1步。我们要把全局步数映射到子问题的局部步数才能继续比较。这一步映射是剪枝递归的精髓也是面试时最能体现理解深度的地方。5.3 二进制视角最低位的1决定移动哪个盘子汉诺塔的第m步还有一个非常漂亮的数学规律第m步移动的盘子编号等于m的二进制表示中最低位1所在的位置加1。举例验证n3的7步步数mm的二进制最低位1的位置实际移动的盘子1001第0位1号盘2010第1位2号盘3011第0位1号盘4100第2位3号盘5101第0位1号盘6110第1位2号盘7111第0位1号盘这个规律和“最低位1的位置”完全吻合。代码上可以用__builtin_ctzll(m)GCC内置函数返回m的二进制末尾连续0的个数或者手写循环得到最低位1的位置。方向规律也成立最小盘1号的移动方向只取决于n的奇偶性盘子编号越大方向循环的周期越长。但完整的柱方向推导需要结合当前盘子的位置写起来比剪枝递归复杂不少所以在竞赛里我通常只用这个二进制规律做快速验证不用它作为主写法。5.4 三种写法的效率对比方法是否生成前m-1步时间复杂度代码复杂度适用场景全模拟 截停是O(2^n)低n小且只求一次剪枝递归否O(n)中n较大、m任意二进制定位否O(log n)较高面试展示、需要极快计算实际刷题时如果题目没有提示n特别大第一版全模拟代码通常已经可以AC。但剪枝递归的思维价值更高因为它让你真正理解“递归执行序列”是可以被分段定位的。这个思想可以用来解决很多衍生问题比如“输出某个递归过程从a步到b步之间的所有操作”这就是一道典型的进阶变体题。我在实际写题过程中会把剪枝递归作为主推方案因为它几乎不增加代码量却能从根上避免超时风险。你可以在本地用n30、m536870911这种接近中间值的数据测试全模拟和剪枝递归的运行时间差距会非常明显。这道题做完以后建议你再做一个小练习把剪枝递归改成“输出第m步前后的三步操作”。你会发现只需要修改命中条件的判断范围就能输出一个连续片段。这个变体练熟了汉诺塔相关的递归题基本就通透了。 汉诺塔第m步定位：从递归模拟到剪枝优化的C++实现
第一次在东华OJ上看到128这道题我心里想的是汉诺塔这不是递归入门题吗直接一个递归把所有移动打印出来不就完了。结果交上去不是超时就是WA翻车翻得明明白白。后来我才意识到这道题问的根本不是“怎么把汉诺塔移完”而是“整棵递归执行树的第m个动作到底是什么”。它考的是你能不能精确命中递归过程中的某一个瞬间而不是把整棵递归树从头到尾完整走一遍。这篇文章就围绕这个“命中瞬间”展开用C实现递归解法再把几种不同的优化思路一并讲透。1. 题目拆解当汉诺塔不再问“总共几步”而是问“第m步发生了什么”1.1 经典汉诺塔模型回顾汉诺塔问题的标准描述是三根柱子A、B、Cn个大小不同的圆盘初始全部套在A柱上按照从大到小、自下而上的顺序排列。目标是把所有盘子移动到C柱并且整个过程只能遵守两条规则一次只能移动一个盘子大盘任何时候都不能压在小盘上面。经典问题的答案是移动步数为2^n - 1当n3时一共7步n4时15步n10时1023步。很多入门教程都会给一个最简单的递归打印程序把每一步移动打印出来。但东华OJ这道题加了一个限制条件只输出第m步发生了什么。这个改动让题目从“枚举全过程”变成了“定位执行序列中的某一个原子操作”。这个区别很重要。如果题目让你把所有步骤都输出那么全模拟就是标准答案没有任何问题。可如果只问你第m步你再从头到尾生成一遍所有移动就多做了大量无用功。当n20时全模拟要输出超过100万步勉强还能跑n30时直接超过10亿步全模拟在OJ上基本就是超时警告。所以这道题的本质是要求你理解递归执行过程中“步数”这个维度的分布规律。1.2 为什么这道题被标记为“难度中”很多人看到“递归”两个字就觉得是送分题实际上这道题有四个隐藏难点。第一个难点是计数位置。每一步移动在递归代码里到底是在哪里发生的是进入递归函数的时候还是递归调用结束之后如果计数位置放错整个输出全部错位。第二个难点是提前终止。全模拟递归会把2^n - 1步全部跑完就算你在第m步输出了结果递归也不会自动停下来它还会继续执行子问题。第三个难点是递归参数轮换。汉诺塔递归的精髓在于柱子角色不断互换左子树、根节点、右子树分别处理的是不同的问题规模。第四个难点是数据范围。n稍微大一点2^n - 1这个数字就会超过int范围处理不好就是溢出。把这些点都解决掉代码虽然只有几十行但思维量不小。这就是题目难度“中”的由来。1.3 东华OJ的输入输出特性刷东华OJ基础题库有一个很实际的感受很多题都支持多组输入而且不会在题目里额外强调。128这道题我见过的主流写法是输入两个整数n和m表示n个盘子询问第m步操作直到EOF结束。如果你只写一次cin n m即使算法全对OJ也只会给你WA因为后续数据根本没有读进去。输出格式也值得提前确认。常见的输出有“第m步把x号盘从from移到to”也有“move disk x from from to to”之类的英文格式。建议交题前仔细核对样例输出的空格、冒号、换行。我在OJ上因为输出多了一个空格被罚过太多次现在养成了先复制样例输出到本地对比的习惯。2. 递归的执行轨迹步数究竟在哪一层产生2.1 递归函数的三段式结构要正确定位第m步首先得知道每一步是在递归的哪个位置产生的。标准汉诺塔递归函数可以写成这样void hanoi(int n, char from, char tmp, char to) { if (n 1) { // 移动1号盘这一步算一次移动 cout from - to endl; return; } // 第一段把上面n-1个盘子从from借助to移到tmp hanoi(n - 1, from, to, tmp); // 第二段把第n个最大盘子从from移到to cout from - to endl; // 第三段把tmp上的n-1个盘子从tmp借助from移到to hanoi(n - 1, tmp, from, to); }这个函数的结构可以拆成三个动作先递归处理前n-1个盘子的移动再移动当前最大盘最后再递归处理另外n-1个盘子的移动。注意三段式里的第一段和第三段本身会继续产生大量移动它们不是“一步”而是“一组步”。步数的计数器应该加在每次真正发生移动的位置也就是cout那一行前后。如果你把计数器加在函数入口那每进入一层递归都会多计一次结果完全错乱。2.2 用n3手动推一遍完整轨迹纸上推演n3的所有移动能把递归结构看得非常清楚。三根柱子分别叫A、B、C三个盘子编号1、2、3最终要把它们从A移到C。从hanoi(3, A, B, C)开始进入第一段执行hanoi(2, A, C, B)这个子问题要把2个盘子从A借助C移到B。进入它的第一段执行hanoi(1, A, B, C)第1步1号盘 A-C。移动第2个盘子第2步2号盘 A-B。进入它的第三段执行hanoi(1, C, A, B)第3步1号盘 C-B。回到最外层移动第3个盘子第4步3号盘 A-C。进入最外层第三段执行hanoi(2, B, A, C)这个子问题要把2个盘子从B借助A移到C。进入它的第一段执行hanoi(1, B, C, A)第5步1号盘 B-A。移动第2个盘子第6步2号盘 B-C。进入它的第三段执行hanoi(1, A, B, C)第7步1号盘 A-C。整个过程用表格记下来规律很直观步数移动的盘子移动方向11号盘A - C22号盘A - B31号盘C - B43号盘A - C51号盘B - A62号盘B - C71号盘A - C注意第4步也就是总步数正中间的那一步移动的是最大盘3号这一步是整个递归最外层的“根动作”。第4步之前的所有步骤都在为这一步做铺垫第4步之后的所有步骤都在做善后。而这种“中轴对称”的结构正好是后面剪枝优化的数学基础。2.3 全局计数器与“递归不会自动停止”的麻烦找到第m步之后你面临的下一个问题是递归还在继续跑。比如n3m2当递归打印完第2步后后面还有5步要执行。如果你不做任何处理程序会继续往下递归直到所有步数跑完。最简单的解决方案是用一个全局计数器cnt每次移动时递增当cnt m时记录结果然后给整个递归设置一个“停止开关”。这个开关可以是一个bool found变量。在递归入口处先判断if (found) return;这样一旦找到目标后续所有递归调用都会快速返回不会继续生成任何多余的移动。这个方案直观、容易理解适合作为第一版AC代码。但它有一个明显短板它仍然会把前m-1步全部模拟出来。如果m本身就很大比如n60m接近2^60全模拟依然会超时。所以我们需要后续的进阶方案。3. C实现正常思路下的全模拟加中途截停3.1 可直接提交的完整代码先给出一版最直接的C实现。这版代码的重点是全局计数器、递归入口的提前终止、以及基准条件的处理。#include iostream using namespace std; int cnt 0; int m; bool found false; void hanoi(int n, char from, char tmp, char to) { if (found) return; if (n 1) { cnt; if (cnt m) { cout 第 cnt 步把 n 号盘从 from 移到 to endl; found true; } return; } hanoi(n - 1, from, to, tmp); if (found) return; cnt; if (cnt m) { cout 第 cnt 步把 n 号盘从 from 移到 to endl; found true; return; } hanoi(n - 1, tmp, from, to); } int main() { int n; while (cin n m) { cnt 0; found false; hanoi(n, A, B, C); } return 0; }注意每次处理一组新输入前都要把cnt和found重置。不然上一组数据的状态会污染下一组这是多组输入最容易犯的错误。代码里我把输出写成了中文格式实际提交时需要按OJ题目要求调整。如果题目要求英文格式比如“move disk 1 from A to C”替换cout里的字符串即可。3.2 为什么计数要放在移动发生的位置有一个新手很容易踩的坑把cnt放在递归调用之前。比如写成这样void hanoi(int n, char from, char tmp, char to) { if (n 1) { cnt; ... } cnt; // 错误示范位置 hanoi(n - 1, from, to, tmp); ... }这么写的后果是每次进入递归函数时都会先多计一次步数被整体提前。更麻烦的是n 1的基准分支和普通分支都各自计数导致计数逻辑混乱。正确的做法是每一次“移动一个盘子”对应唯一一次计数。在代码里“移动”这个动作体现在两个位置一是n 1时的那次打印二是递归函数中间那条打印语句。计数器与打印语句绑定在一起而不是与函数调用绑定在一起这是这道题计数正确的前提。3.3 用全局标志提前终止的利与弊found标志位方案的好处是代码直观、不容易出错任何学过递归的人都能快速写出。坏处是它在找到答案后仍然依赖每层递归入口的return判断无法跳过“已经执行到一半的递归调用栈”中的剩余逻辑。但在实际OJ的数据范围内只要n不是特别大这个方案完全够用。如果n在20以内全模拟加中途截停的运行时间几乎可以忽略不计。真正需要担心的场景是n超过30这时候2^n - 1已经上亿即便中途截停跑到第m步之前的代价也可能非常可怕。因此你需要第5节的剪枝思维来兜底。4. 第一次交题最容易踩的四个坑4.1 盘子总数溢出int范围2^n - 1这个数字在n31时就已经超过int的最大值n63时超过unsigned long long的范围实际上2^63-1刚好等于long long的上限n64就会溢出。虽然这道题的m大概率不会给到那么极端但写代码时养成好习惯很重要。如果你需要判断m是否合法不要用pow(2, n)因为浮点数在n很大时会丢失精度。直接用移位运算long long total (1LL n) - 1;注意1LL是long long类型的1这样左移结果不会溢出int。如果n很大甚至要考虑用unsigned long long或做额外保护否则只能放弃判断合法性直接信任题目数据。4.2 递归参数传反导致的错位汉诺塔递归的参数轮换很容易写反。hanoi(n - 1, from, to, tmp)和hanoi(n - 1, tmp, from, to)这两行前者是把前n-1个盘子移到辅助柱后者是把前n-1个盘子从辅助柱移到目标柱。一旦把tmp和to的顺序搞混输出序列会整体错位而且很难靠肉眼排查出来。我的习惯是在函数定义里就把三个参数命名成from、tmp、to再加上注释。移动最大盘的那行永远是从from到to如果写成from到tmp那第一段递归和中间移动的目标就矛盾了整个问题根本不可能收敛。检查递归参数时可以拿n2的样例手推几行很快就能发现问题。4.3 多组输入没处理导致WA东华OJ的很多基础题都采用“多组输入直到EOF”的模式128题我印象里也一样。while (cin n m)是标准写法但有人会忘记每次循环重置全局状态。假设第一次查询后found变成了true第二组输入进来时递归入口直接if (found) return;结果什么都不输出白白WA一次。正确的做法是在每次循环体开头重置状态while (cin n m) { cnt 0; found false; hanoi(n, A, B, C); }4.4 输出格式和题目要求不一致OJ判题用的是逐字符比对多一个空格、少一个冒号、大小写不一致都会判WA。最稳妥的方法是把题目样例输出原样复制下来对比自己的输出逐字符检查。我遇到过一种情况题目要求输出“第m步”但我写成了“第m步:”差别就是全角冒号和半角冒号肉眼几乎看不出来OJ照样毫不留情地WA。这种错误特别浪费感情建议提交前先看讨论区有没有人提醒过输出格式的坑。5. 进阶优化利用“三段式结构”直接命中第m步5.1 汉诺塔的分段结构前段、中线、后段回到递归执行轨迹。对于hanoi(n, from, tmp, to)它处理的总步数是2^n - 1。这三个部分其实可以精确划分为左半段前2^(n-1) - 1步内容是“把n-1个盘子从from借助to移到tmp”。中间点第2^(n-1)步内容是“把第n个盘子从from移到to”。右半段后2^(n-1) - 1步内容是“把n-1个盘子从tmp借助from移到to”。这个分段是严格数学意义上的不是经验规律。因为递归定义本身就决定了这三个子问题的执行顺序和步数。基于这个结构我们可以直接判断第m步落在哪一段然后只进入对应的分支。这样每一层递归都能把问题规模缩小一半时间复杂度从O(2^n)降到了O(n)。5.2 剪枝递归实现下面是基于分段结构的递归代码。它本质上还是递归但不会执行任何多余的移动。#include iostream using namespace std; void hanoi(int n, char from, char tmp, char to, long long m) { long long half (1LL (n - 1)) - 1; if (m half) { // 第m步在左半段处理前n-1个盘子, 从from借助to移到tmp hanoi(n - 1, from, to, tmp, m); } else if (m half 1) { // 第m步正好是最大盘的移动 cout 第 m 步把 n 号盘从 from 移到 to endl; } else { // 第m步在右半段换算成右半段中的新步数 hanoi(n - 1, tmp, from, to, m - half - 1); } } int main() { int n; long long m; while (cin n m) { hanoi(n, A, B, C, m); } return 0; }注意当n1时half (1LL 0) - 1 0此时m只能是1直接命中m half 1分支输出1号盘的移动。所以这个函数不需要单独的if (n 1)基准条件逻辑照样正确。为什么右边递归里要把m减去half 1因为右半段是从总步数的第half 2步开始的而右半段内部的第一步对应递归子问题的第1步。我们要把全局步数映射到子问题的局部步数才能继续比较。这一步映射是剪枝递归的精髓也是面试时最能体现理解深度的地方。5.3 二进制视角最低位的1决定移动哪个盘子汉诺塔的第m步还有一个非常漂亮的数学规律第m步移动的盘子编号等于m的二进制表示中最低位1所在的位置加1。举例验证n3的7步步数mm的二进制最低位1的位置实际移动的盘子1001第0位1号盘2010第1位2号盘3011第0位1号盘4100第2位3号盘5101第0位1号盘6110第1位2号盘7111第0位1号盘这个规律和“最低位1的位置”完全吻合。代码上可以用__builtin_ctzll(m)GCC内置函数返回m的二进制末尾连续0的个数或者手写循环得到最低位1的位置。方向规律也成立最小盘1号的移动方向只取决于n的奇偶性盘子编号越大方向循环的周期越长。但完整的柱方向推导需要结合当前盘子的位置写起来比剪枝递归复杂不少所以在竞赛里我通常只用这个二进制规律做快速验证不用它作为主写法。5.4 三种写法的效率对比方法是否生成前m-1步时间复杂度代码复杂度适用场景全模拟 截停是O(2^n)低n小且只求一次剪枝递归否O(n)中n较大、m任意二进制定位否O(log n)较高面试展示、需要极快计算实际刷题时如果题目没有提示n特别大第一版全模拟代码通常已经可以AC。但剪枝递归的思维价值更高因为它让你真正理解“递归执行序列”是可以被分段定位的。这个思想可以用来解决很多衍生问题比如“输出某个递归过程从a步到b步之间的所有操作”这就是一道典型的进阶变体题。我在实际写题过程中会把剪枝递归作为主推方案因为它几乎不增加代码量却能从根上避免超时风险。你可以在本地用n30、m536870911这种接近中间值的数据测试全模拟和剪枝递归的运行时间差距会非常明显。这道题做完以后建议你再做一个小练习把剪枝递归改成“输出第m步前后的三步操作”。你会发现只需要修改命中条件的判断范围就能输出一个连续片段。这个变体练熟了汉诺塔相关的递归题基本就通透了。