GESP2026年9月认证C++四级( 第三部分编程题（1、新汉诺塔））精讲

这道题显然是超出大部分考四级同学的实际能力！

题目是在经典汉诺塔上增加了一个新规则：圆盘只能按照 A → B、B → C、C → A 的方向移动，其他方向都不允许。

一、先给同学们讲一个故事：三座魔法塔

很久很久以前，有一个叫小杨的魔法师。

他来到了一座神秘的城堡，城堡里有三根魔法柱：

A B C
│ │ │
│ │ │
●│ │ │
●●│ │ │
●●●│ │ │

A、B、C 三根柱子上放着大小不同的圆盘。

规则和经典汉诺塔一样：

规则1：一次只能移动一个圆盘

不能：

一下搬两个

只能：

搬一个

规则2：只能拿最上面的圆盘

下面压着一个圆盘，就不能直接拿出来。

规则3：大圆盘不能压在小圆盘上

例如：

●
●●

可以。

但是：

●●
●

不可以。

二、但是今天有一个超级麻烦的新规定！

小杨突然发现城堡门口贴着一张告示：

🚨 魔法圆盘只能顺时针走！

也就是说：

A → B
B → C
C → A

只有这三个方向可以走。

而：

A → C ❌
B → A ❌
C → B ❌

全部禁止！

题目就是：

现在有 n 个圆盘，全部放在 A 柱，要把它们按照原来的顺序全部搬到 C 柱，最少需要多少步？

题目的样例是：

输入：
2

输出：
7

也就是说：

两个圆盘，竟然需要整整7步！

三、先不要写代码，我们先手工玩一次！

这是整道题最重要的地方。

假设只有两个圆盘：

A B C

小1
大2

目标：

A B C

小1
大2

第1步：小圆盘 A → B

A B C

大2 小1

第2步：小圆盘 B → C

A B C

大2 小1

第3步：大圆盘 A → B

A B C

大2 小1

现在麻烦来了！

大圆盘已经在 B。

按照规则，大圆盘下一步必须：

B → C

但是 C 上有小圆盘。

所以必须先把 C 上的小圆盘搬走。

第4步：小圆盘 C → A

因为：

C → A

允许。

第5步：大圆盘 B → C

A B C

小1 大2

但是目标是：

小1
大2

小圆盘现在还在 A。

所以：

第6步：小圆盘 A → B

A B C

小1 大2

第7步：小圆盘 B → C

A B C

小1
大2

成功！

所以：

2个圆盘 → 7步

这正是题目的样例：

2
7

以及题目给出的7步移动过程。

四、同学们都很苦恼：为什么不能直接 A → C？

因为新规则规定了：

A → B
B → C
C → A

只能沿着这个方向走。

可以把三根柱子想象成一个魔法传送环：

A
↙ ↖
/ \\
C ←────── B

更准确地画成：

A
↓
B
↓
C
↓
A

所以：

A → B ✅
B → C ✅
C → A ✅

A → C ❌
C → B ❌
B → A ❌

五、真正的难题来了：如果有 n 个圆盘怎么办？

如果：

n = 2

我们还能手工玩。

如果：

n = 10

呢？

如果：

n = 20

呢？

难道我们真的一颗一颗圆盘去模拟？

那就太累了。

聪明的小杨想：

“我能不能把 n 个圆盘的问题，变成 n-1 个圆盘的问题？”

这就是今天最重要的思想。

六、我们先给问题起两个名字

这里是整道题最关键的一步。

我们定义两个“魔法任务”。

任务 F：从 A 搬到 B

我们定义：

F[n] = n 个圆盘从 A 搬到 B 的最少步数。

例如：

F[1]

一个圆盘：

A → B

只需要：

1步

所以：

F[1] = 1

任务 G：从 A 搬到 C

我们定义：

G[n] = n 个圆盘从 A 搬到 C 的最少步数。

我们真正要求的就是：

G[n]

因为题目要求：

A → C

七、先解决 F[n]

假设现在有 n 个圆盘：

1号：最小
2号
3号
…
n号：最大

我们想：

A → B

最大圆盘 n 最终必须从：

A → B

但是最大圆盘上面压着：

1 ~ n-1

所以必须先把上面的 n-1 个圆盘搬走。

搬到哪里？

不能搬到 B。

因为我们最后要让：

n号大圆盘 A → B

所以 B 必须空出来。

于是：

n-1个圆盘
A → C

这个问题是什么？

正好就是我们定义的：

G[n-1]

然后最大圆盘移动

n号圆盘：
A → B

只需要：

1步

但是还没结束！

现在：

n号大圆盘在 B
n-1个小圆盘在 C

我们最终希望全部到 B。

可是小圆盘现在在 C。

而规则规定：

C → A
A → B

所以要把 n-1 个圆盘从 C 搬到 B。

这和：

A → C

本质上是一样的，只是把三根柱子的名字整体转了一圈。

所以还需要：

G[n-1]

因此：

F[n] = G[n-1] + 1 + G[n-1]

也就是：

⭐ F[n] = 2 × G[n-1] + 1

这就是参考程序中的：

f[i] = 2 * g[i – 1] + 1;

八、再解决 G[n]

这才是真正的目标。

我们想把：

n个圆盘
A → C

怎么办？

最大的圆盘 n 最终必须到 C。

但是注意：

A → C

是不允许的！

所以最大圆盘必须：

A → B → C

也就是：

A → B
B → C

需要两步。

九、第一阶段：先搬走上面的 n-1 个小圆盘

最大圆盘在 A。

我们要让它：

A → B

所以 A 上面的 n-1 个圆盘必须先离开。

它们需要：

A → C

因此需要：

G[n-1]

步。

十、第二阶段：最大圆盘 A → B

n号圆盘：
A → B

需要：

1步

十一、第三阶段：把 n-1 个圆盘从 C 搬到 A

现在：

A：空了
B：最大圆盘
C：n-1个小圆盘

为了让最大圆盘继续：

B → C

C 必须空出来。

所以：

n-1个圆盘：
C → A

注意：

C → A

正好是允许的！

这个任务和：

A → B

是同一种情况。

所以需要：

F[n-1]

步。

十二、第四阶段：最大圆盘 B → C

现在 C 已经空出来了。

所以：

n号圆盘：

B → C

又需要：

1步

十三、第五阶段：最后的小圆盘 A → C

现在：

A：n-1个小圆盘
B：空
C：最大圆盘

最后只需要：

n-1个圆盘
A → C

这又是：

G[n-1]

步。

十四、终于得到核心公式！

把这5部分加起来：

第一部分：G[n-1]
第二部分：1
第三部分：F[n-1]
第四部分：1
第五部分：G[n-1]

所以：

⭐ G[n] = 2 × G[n-1] + F[n-1] + 2

这正是题目参考程序中的：

g[i] = 2 * g[i – 1] + f[i – 1] + 2;

十五、现在孩子应该明白：为什么要有 F 和 G 两个数组了

可以把它想象成两个任务机器人：

🤖 F机器人：

负责：
n个圆盘 A → B

🤖 G机器人：

负责：
n个圆盘 A → C

然后：

F[n]
↓
需要两个 G[n-1]

G[n]
↓
需要两个 G[n-1]
+ 一个 F[n-1]

所以：

F[n] = 2G[n-1] + 1

G[n] = 2G[n-1] + F[n-1] + 2

十六、从最小的1个圆盘开始算

我们约定：

F[0] = 0
G[0] = 0

为什么？

因为：

0个圆盘根本不用搬。

所以：

F[0] = 0
G[0] = 0

n = 1

计算：

F[1]
= 2 × G[0] + 1
= 2 × 0 + 1
= 1

所以：

F[1] = 1

再算：

G[1]
= 2 × G[0] + F[0] + 2
= 0 + 0 + 2
= 2

确实：

A → B
B → C

两步。

十七、n = 2

现在：

F[1] = 1
G[1] = 2

所以：

F[2]
= 2 × G[1] + 1
= 2 × 2 + 1
= 5

再算：

G[2]
= 2 × G[1] + F[1] + 2
= 2 × 2 + 1 + 2
= 7

所以：

G[2] = 7

这和题目样例完全一致：

输入：2
输出：7

十八、继续算 n = 3

F[2] = 5
G[2] = 7

于是：

F[3]
= 2 × G[2] + 1
= 2 × 7 + 1
= 15

再：

G[3]
= 2 × G[2] + F[2] + 2
= 2 × 7 + 5 + 2
= 21

所以：

3个圆盘 A → C
最少需要21步

十九、做一张表，一下就明白了

同学们可以观察：

G[1] = 2
G[2] = 7
G[3] = 21
G[4] = 64

数字越来越大。

这就是为什么：

不能真的一层一层模拟移动过程，而应该直接计算答案。

二十、这道题其实就是“动态规划”

虽然题目用到的是递推，但不掌握动态规划的方法，已经很难做这道题，所以本题是严重的超纲。

因为：

G[4]

需要：

G[3]
F[3]

而：

G[3]

又需要：

G[2]
F[2]

……

所以我们从小到大：

0
↓
1
↓
2
↓
3
↓
4
↓
…
↓
n

一个一个计算。

这就是用到了：

小问题 → 大问题

二十一、代码十分简单，但是推论代码的过程非常不简单！

题目的参考程序是：

#include <iostream>
using namespace std;

int f[22], g[22];

int main() {
int n;
cin >> n;

for (int i = 1; i <= n; ++i) {
f[i] = 2 * g[i – 1] + 1;
g[i] = 2 * g[i – 1] + f[i – 1] + 2;
}

cout << g[n] << endl;

return 0;
}

这就是题目给出的参考程序。

二十二、逐行给大家解析下

第1行

#include <iostream>

告诉 C++：

我要使用输入输出功能。

第2行

using namespace std;

方便我们使用：

cin
cout

第4行

int f[22], g[22];

准备两个“记忆盒子”。

f[0] f[1] f[2] f[3] …

g[0] g[1] g[2] g[3] …

其中：

f[i] = i个圆盘 A → B 的最少步数

g[i] = i个圆盘 A → C 的最少步数

二十三、输入 n

int n;
cin >> n;

例如：

2

那么：

n = 2

二十四、从1开始一个一个算

for (int i = 1; i <= n; ++i)

如果：

n = 5

那么：

i = 1
i = 2
i = 3
i = 4
i = 5

像爬楼梯一样：

第1层
↓
第2层
↓
第3层
↓
第4层
↓
第5层

二十五、第一条公式

f[i] = 2 * g[i – 1] + 1;

解释一下：

要完成 i 个圆盘 A→B，先做两次 i-1 个圆盘 A→C，再移动一次最大的圆盘。

所以：

F[i]
=
G[i-1]
+
1
+
G[i-1]

也就是：

2 × G[i-1] + 1

二十六、第二条公式

g[i] = 2 * g[i – 1] + f[i – 1] + 2;

解释一下：

要完成 i 个圆盘 A→C，需要：

① n-1 个圆盘 A→C
② 最大圆盘 A→B
③ n-1 个圆盘 C→A
④ 最大圆盘 B→C
⑤ n-1 个圆盘 A→C

所以：

G[i]
=
G[i-1]
+ 1
+ F[i-1]
+ 1
+ G[i-1]

整理：

G[i]
=
2G[i-1]
+
F[i-1]
+
2

二十七、最后为什么输出 g[n]？

cout << g[n] << endl;

因为题目最终要求：

n个圆盘
A → C

而我们早就规定：

g[n]

就是：

n个圆盘从 A 搬到 C 的最少步数。

所以直接：

cout << g[n];

就结束了。

二十八、把 n=2 在代码里跑一遍

输入：

2

开始：

f[0] = 0
g[0] = 0

i = 1

f[1] = 2 × g[0] + 1
= 1

g[1] = 2 × g[0] + f[0] + 2
= 2

现在：

f[1] = 1
g[1] = 2

i = 2

f[2] = 2 × g[1] + 1
= 2 × 2 + 1
= 5

然后：

g[2] = 2 × g[1] + f[1] + 2
= 2 × 2 + 1 + 2
= 7

最后：

cout << g[2];

输出：

7

二十九、这道题其实考的不是汉诺塔

这道题表面上考：

汉诺塔。

实际上考的是：

“拆问题”的能力。

我们看到：

20个圆盘

有可能第一反应：

老师，这怎么搬得完？

但算法高手会说：

我不需要真的搬20个。

我只需要知道：

20个问题
↓
19个问题
↓
18个问题
↓
…
↓
1个问题

然后从最小的问题开始，把答案一层一层推回来。

三十、新汉诺塔三步法

第一步：给任务起名字

F[n]：A → B
G[n]：A → C

第二步：找到最大圆盘

最大圆盘不能直接：

A → C

所以必须：

A → B → C

第三步：把大问题拆成小问题

F[n] = 2G[n-1] + 1

G[n] = 2G[n-1] + F[n-1] + 2

最后：

答案 = G[n]

三十一、最容易犯的4个错误

❌ 错误1：认为 A 可以直接到 C

题目新规则：

A → B
B → C
C → A

所以：

A → C ❌

❌ 错误2：只定义一个数组

有人可能想：

int dp[100];

但不行。

因为我们发现：

G[n]

计算的时候不仅需要：

G[n-1]

还需要：

F[n-1]

所以必须记录两种状态：

f[]
g[]

❌ 错误3：忘记两个“大圆盘移动”

计算：

G[n]

最大圆盘要：

A → B
B → C

所以一定有：

+2

不是 +1。

❌ 错误4：从 n 往0算

例如：

for (int i = n; i >= 1; i–)

会很麻烦，因为：

G[n]
需要 G[n-1]

G[n-1]
需要 G[n-2]

所以最舒服的方法是：

从小到大
0 → 1 → 2 → … → n

三十二、最后把整道题压缩成一张图

新汉诺塔
│
三根魔法柱 A B C
│
只能按照 A→B→C→A 移动
│
↓
定义两个状态
┌──────┴──────┐
↓ ↓
F[n] G[n]
A → B A → C
│ │
↓ ↓
F[n]=2G[n-1]+1
G[n]
↓
2G[n-1]+F[n-1]+2
│
↓
G[n]
│
↓
答案

🌟 给考生的最后一句话

这道题考察我们的，其实不是：

“汉诺塔怎么搬？”

而是：

“遇到一个看起来巨大、复杂、根本做不完的问题，不要害怕。先找到一个小问题，再想办法让大问题依赖小问题。”

这就是算法学习中非常重要的一次进阶：

暴力模拟
↓
发现规律
↓
定义状态
↓
拆成小问题
↓
递推公式
↓
从小到大计算
↓
得到答案

如果这类考题将来成为四级考试的常态，对于我们信奥教师，要从本次考试中吸取教训，递推的课程设置，要与线性DP相结合，在四级阶段，就要给学生提前讲解了。