GESP 2026年9月 · 四级赛后解析

新汉诺塔递推公式怎么推？

从1、2、3个盘子手动模拟一步一步推广到n

2026年9月GESP四级第一道编程题是《新汉诺塔》。

这道题的关键，是结合经典 Hanoi 的思路来分析 New Hanoi。

经典 Hanoi 告诉我们：分析圆盘移动时，要盯住最大的盘子，先想清楚“怎样为最大盘腾位置、最大盘怎样到达目标、上面的小盘怎样放回去”。New Hanoi 改变了移动方向，原来的答案不能直接套用，但这种拆解问题的方法仍然有效。

因此，拿到题目后先不要写程序。我们从1个盘子开始，反复手动模拟2个、3个盘子的完整移动过程，在每一轮模拟中观察最大盘和上方小塔的位置变化，再从重复出现的过程里找出规律。最后，才把规律抽象成状态和递推关系。

整道题的思考过程可以归纳为四步：

1. 仔细理解题意，联想经典 Hanoi 的经验2. 用1个、2个盘子动手试一试3. 用3个、4个盘子继续模拟，寻找重复规律4. 写出递推方程，并设计数组逐项计算

经典 Hanoi 的目标，是把整座圆盘塔从起点柱搬到目标柱。无论有多少个盘子，分析时都围绕最下面的最大盘展开：

先把最大盘上面的n-1个盘子移开→ 移动最大盘→ 再把n-1个盘子放回最大盘上面

于是，n个盘子的问题会转化为规模更小的n-1个盘子问题。这就是经典 Hanoi 的核心：不是观察答案数字，而是观察移动过程怎样重复。

New Hanoi 仍然具有“大盘被小盘压住”这一结构，因此我们继续沿用这种思考方式。不同之处在于，圆盘的移动方向受到限制，所以需要通过多轮手动模拟重新寻找重复过程。

再读懂 New Hanoi 的新规则

题目仍然有A、B、C三根柱子，并遵守汉诺塔的基本规则：每次只能移动一个盘子；只能移动柱子最上面的盘子；小盘必须始终放在大盘上面。

新增加的限制是，圆盘只能按照下面的方向移动：

A → B → C → A

A到B可以直接移动；A到C不能直接移动，必须先经过B；反方向移动也不允许。

这个方向限制，让“把整座塔搬到相邻柱”和“把整座塔搬到目标柱”变成了两种不同的任务。

先看1个盘子

题目要求把整座塔从A柱搬到C柱。我们先用 `newHanoi[n]` 表示：把n个盘子从A柱全部搬到C柱的最少步数。

当只有1个盘子时，它不能从A直接跨到C，只能：

A → B → C

所以：

newHanoi[1] = 2

这时只需要记录一种结果。接下来继续手动模拟2个盘子，看看过程会发生什么变化。

再完整模拟2个盘子

现在有两个盘子：1号是小盘，2号是大盘。开始时，它们都在A柱上；目标是把两个盘子全部搬到C柱，并保持小盘在大盘上面。

初始状态：

A柱：2号盘、1号盘B柱：空C柱：空

由于2号大盘被1号小盘压在下面，第一步不能直接移动大盘。我们必须先把小盘移开。

第1步：小盘从A移动到B

A柱：2号盘B柱：1号盘C柱：空

第2步：小盘从B移动到C

小盘不能从B返回A，只能继续沿规定方向移动到C。

A柱：2号盘B柱：空C柱：1号盘

现在大盘上方已经没有其他盘子，可以移动大盘。

第3步：大盘从A移动到B

A柱：空B柱：2号盘C柱：1号盘

接下来要让大盘从B移动到C，但C柱上还有小盘。必须先把小盘移走。

第4步：小盘从C移动到A

A柱：1号盘B柱：2号盘C柱：空

C柱已经腾空，大盘可以继续移动。

第5步：大盘从B移动到C

A柱：1号盘B柱：空C柱：2号盘

现在大盘已经到达目标C柱，最后只需把小盘放到大盘上面。

第6步：小盘从A移动到B

A柱：空B柱：1号盘C柱：2号盘

第7步：小盘从B移动到C

A柱：空B柱：空C柱：2号盘、1号盘

两个盘子全部到达C柱，共移动7步：

小盘A→B→ 小盘B→C→ 大盘A→B→ 小盘C→A→ 大盘B→C→ 小盘A→B→ 小盘B→C

所以，2个盘子从A搬到C的最少移动次数是：

newHanoi[2] = 7

这一遍手动模拟先解决“怎样搬得成”。接下来分析3个盘子时，再把刚才的7步看成一个完整模块，观察同样的过程如何重复出现。

分析3个盘子：新的问题出现了

现在有大、中、小三个盘子，都在A柱，目标仍然是把它们全部搬到C柱。

先不要急着列出21次具体移动。先盯住最大的盘子，因为只有把大盘搬到C柱，整个任务才可能完成。

大盘到达C柱之前，必须先在B柱

根据移动方向：

A → B → C → A

大盘不能从A直接移动到C。它到达C之前，一定要先处在B柱。

而大盘要从B移动到C时，中盘和小盘不能压在它上面，也不能占着C柱。此时必须形成下面的状态：

A柱：中盘、小盘B柱：大盘C柱：空

所以，分析3个盘子的关键，就变成了：怎样先得到“大盘在B，中盘和小盘在A”的状态？

大盘从A移动到B之前，中盘和小盘必须在C

开始时三个盘子都在A。要让大盘从A移动到B，必须先把压在它上面的中盘和小盘全部移开。

B柱是大盘马上要去的位置，不能被中、小盘占据，因此中盘和小盘必须先整体搬到C柱：

A柱：大盘B柱：空C柱：中盘、小盘

“把两个盘子从A搬到C”正是刚刚手动完成的2个盘子问题，所以需要：

newHanoi[2] = 7步

然后大盘从A移动到B，需要1步：

A柱：空B柱：大盘C柱：中盘、小盘

接下来必须把中盘和小盘从C搬回A

为了让大盘继续从B移动到C，C柱必须腾空。因此，要把中盘和小盘从C整体搬到A。

这里出现了一个新的过程：

把一座塔从C搬到A

它与 `newHanoi[2]` 表示的“A搬到C”不是同一个方向，步数也不同。我们暂时把这个过程记为：

nearHanoi[2]

手动移动两个盘子，可以写出下面的完整合法过程：

小盘：C → A小盘：A → B大盘：C → A小盘：B → C小盘：C → A

共5步，因此：

nearHanoi[2] = 5

完成后得到我们需要的中间状态：

A柱：中盘、小盘B柱：大盘C柱：空

大盘进入C后，还要再次完成两个盘子的问题

现在大盘可以从B移动到C，需要1步。

此时：

A柱：中盘、小盘B柱：空C柱：大盘

最后，还要把中盘和小盘从A搬到C，放到大盘上面。这又是一次完整的2个盘子问题：

newHanoi[2] = 7步

因此，3个盘子的完整结构是：

中、小盘从A搬到C：newHanoi[2]→ 大盘从A到B：1步→ 中、小盘从C搬回A：nearHanoi[2]→ 大盘从B到C：1步→ 中、小盘再次从A搬到C：newHanoi[2]

所以：

newHanoi[3]= newHanoi[2] + 1 + nearHanoi[2] + 1 + newHanoi[2]= 7 + 1 + 5 + 1 + 7= 21

现在就能看出，分析3个盘子时，仅有 `newHanoi` 还不够，因为中间必须解决“把一座塔从C搬到A”的问题。第二个状态不是预先规定的，而是在手动推演中自然出现的。

到这里，可以总结出两种目标动作

经过多轮手动模拟，我们发现，题目中需要反复解决两种整塔移动：

第一种：把n个盘子整体搬到顺向相隔一柱的目标柱第二种：把n个盘子整体搬到顺向相邻柱

例如从A柱出发：

A → C：需要经过B，属于第一种A → B：顺着箭头直接到达，属于第二种

从C柱出发时同样如此：

C → B：需要经过A，属于第一种C → A：顺着箭头直接到达，属于第二种

因此，用两个名字保存这两类动作：

newHanoi[n]：把n个盘子整体搬到顺向相隔一柱的目标柱nearHanoi[n]：把n个盘子整体搬到顺向相邻柱

这里的 `near` 就是“相邻”的意思。这样命名后，每次看到 `nearHanoi`，就知道它表示整座塔沿允许方向搬到下一根柱子。

再用4个盘子检查这个结构

4个盘子不需要真的逐步写出几十次移动。可以把上面的3个盘子看成一座已经会搬的“小塔”，继续围绕最大的4号盘分组。

要把4个盘子从A搬到C：

① 上面的3个盘子从A搬到C：newHanoi[3] = 21② 4号盘从A移动到B：1步③ 上面的3个盘子从C搬到A：nearHanoi[3] = 15④ 4号盘从B移动到C：1步⑤ 上面的3个盘子再次从A搬到C：newHanoi[3] = 21

因此：

newHanoi[4]= 21 + 1 + 15 + 1 + 21= 59

其中，`nearHanoi[3]` 也沿用同一个结构：先把上面的2个盘子搬走，移动最大盘，再把2个盘子放回，因此：

nearHanoi[3]= newHanoi[2] + 1 + newHanoi[2]= 7 + 1 + 7= 15

从3个盘子到4个盘子，五个阶段完全没有改变，变化的只是“小塔”从2个盘子增加为3个盘子。这说明我们找到的是可以推广到任意n的重复结构。

先写nearHanoi的递推关系

`nearHanoi[n]` 表示把n个盘子组成的整座塔从C搬到A。C→A正好是允许直接移动的方向。

要把最下面的大盘从C移动到A，先要把上面的n-1个盘子从C搬到B，为大盘腾出空间。

从C到B不能直接移动，必须经过A。这个过程与“从A搬到C”只是柱子名称轮换了一次，移动结构完全相同，因此需要：

newHanoi[n-1]

接着：

大盘从C移动到A：1步

最后，要把n-1个盘子从B搬到A，仍然需要经过C，结构又与 `newHanoi[n-1]` 相同。

因此：

nearHanoi[n]= newHanoi[n-1] + 1 + newHanoi[n-1]= 2 × newHanoi[n-1] + 1

代入n=2检查：

nearHanoi[2]= 2 × newHanoi[1] + 1= 2 × 2 + 1= 5

与刚才的手动过程一致。

再写newHanoi的递推关系

从3个盘子的过程可以看到，要把n个盘子从A搬到C，始终需要五个阶段：

① 上面的n-1个盘子从A搬到C：newHanoi[n-1]② 最大盘从A移动到B：1步③ n-1个盘子从C搬回A：nearHanoi[n-1]④ 最大盘从B移动到C：1步⑤ n-1个盘子再次从A搬到C：newHanoi[n-1]

所以：

newHanoi[n]= newHanoi[n-1] + 1 + nearHanoi[n-1] + 1 + newHanoi[n-1]= 2 × newHanoi[n-1] + nearHanoi[n-1] + 2

再结合辅助公式：

nearHanoi[n] = 2 × newHanoi[n-1] + 1

两组数据就可以从小到大依次推导。

这里的公式不是看着2、7、21这几个答案猜出来的。真正的推导顺序是：

手动完成2个盘子→ 分析3个盘子的大盘怎样到达C→ 发现中间必须把小塔从C搬回A→ 新增nearHanoi状态→ 分别推导两个过程的递推关系

设计数组保存计算结果

规律确定后，再考虑程序如何存储。需要两个数组：

newHanoi[i]：i个盘子从A搬到C的最少步数nearHanoi[i]：i个盘子从C搬到A的最少步数

初始值都是0。然后从1到n依次计算：

nearHanoi[i] = 2 × newHanoi[i-1] + 1newHanoi[i] = 2 × newHanoi[i-1] + nearHanoi[i-1] + 2

第i项只依赖第i-1项，因此从前往后推导即可。题目最终输出 `newHanoi[n]`。

用小数据验证方程

根据递推式计算：

n=1：nearHanoi[1]=1，newHanoi[1]=2n=2：nearHanoi[2]=5，newHanoi[2]=7n=3：nearHanoi[3]=15，newHanoi[3]=21n=4：nearHanoi[4]=43，newHanoi[4]=59

这些结果与手动模拟以及题目样例一致。

验证小数据可以检查两个状态有没有定义反、有没有漏掉最大盘的移动、初始值是否正确，以及最后应该输出哪个数组。

《新汉诺塔》不是让孩子背下两条公式。它真正训练的是：借用经典 Hanoi 的分析框架，对新规则进行多轮手动模拟，再从模拟过程里找出可以重复的结构。

完整的解题路径是：

读懂新增规则→ 从1个盘子开始模拟→ 完整拆解2个盘子→ 用3个盘子确认结构会重复→ 在3个盘子的过程中发现辅助状态→ 用4个盘子确认结构会重复→ 写出两个递推方程并推广到n个盘子→ 设计数组保存结果→ 用小数据验证

经典 Hanoi 提供思考方法，手动模拟帮助我们看见新规则下的变化，递推关系则是对重复过程的最后概括。

从具体操作中找到重复结构，再把结构写成递推关系，这才是四级阶段最重要的算法思维。

很多孩子看到汉诺塔，会立刻想到经典公式 `2^n-1`。但题目一旦改变移动规则，原公式就不能直接套用。

真正可靠的方法，是回到问题本身：先画方向、再动手模拟、记录小规模答案、观察最大盘如何移动，然后设计能够完整描述问题的状态。

下一篇，我们再用同样的方法分析第二道编程题《有序网格》。

——魔都信奥直通车

本文依据CCF GESP官网公布的2026年9月C++四级试题整理，题目与数据范围以官方试卷为准。

读懂规则 · 拆解过程 · 写对程序

魔都信奥直通车 · 陪孩子稳步成长