GESP 题解库 / 4 级题解 / [GESP202609 四级] 新汉诺塔 · 第 24 / 25 题
GESP202609 四级 · B4579 · 中等

新汉诺塔

只允许 A→B、B→C、C→A 三种移动,求把 n 个圆盘从 A 移到 C 的最少步数。

📊
n ≤ 20
圆盘数量
🔢
long long
数值类型
⚡
O(n)
时间复杂度
🎯
双向递推
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

经典汉诺塔中,n 个圆盘从小到大叠在 A 柱上,目标是把它们移到 C 柱且保持顺序,规则是每次只能移动一个圆盘、大盘不能压在小盘上。

新规则:圆盘只能从 A 移到 B、从 B 移到 C、或从 C 移到 A,其他方向的移动都不允许(即只能"顺时针"移动)。

给定 n,求最少移动步数。

样例:n = 2 → 7;n = 3 → 21。

💡
人话翻译:加了"只能顺时针移动"这个限制后,移动变得更麻烦——因为想从 A 直接到 C 是不允许的,必须绕道 A→B→C。所以我们需要同时维护两种成本:"移动 1 格"(如 A→B)和"移动 2 格"(如 A→C)。

🔍 关键词提取

递推状态定义循环移动限制long long

已知条件

项目说明
输入一个正整数 n
输出最少移动步数
数据范围n ≤ 20
允许的移动仅 A→B、B→C、C→A(顺时针)
样例n = 2 → 7;n = 3 → 21

需要解决的问题

02
思维导图
整理解题思路的全貌
🔁 同时维护"移1格"和"移2格"
🧠 状态定义
A→B→C 是顺时针环
F(n):移 2 格(如 A→C)
G(n):移 1 格(如 A→B)
两者互相依赖
📐 递推式
F(n) = 2F(n−1) + G(n−1) + 2
G(n) = 2F(n−1) + 1
初值 F(0) = G(0) = 0
一路推到 F(n)
🎯 关键步骤
最大盘必须 A→B 再 B→C
移动前要把上面 n−1 个盘挪开
挪开后还要挪回来
共两个 F 和 一个 G
⚠️ 易错点
只用一个状态(漏掉 G)
用 int 溢出
初值搞错
以为答案还是 2ⁿ − 1
03
样例手算推导
从 n = 1 递推到 n = 3

🧮 递推过程:从 0 推到 3

先明确:F(n) 表示把 n 个盘顺时针移 1 格(如 A→B)的步数,G(n) 表示顺时针移 2 格(如 A→C)的步数。

nG(n):移 1 格F(n):移 2 格计算依据
000没有盘子,不用移动
112G(1) = A→B 一步;F(1) = A→B→C 两步
257G(2) = 2F(1)+1 = 5;F(2) = 2F(1)+G(1)+2 = 7
31521G(3) = 2F(2)+1 = 15;F(3) = 2F(2)+G(2)+2 = 21
1
F(n) 递推式怎么来的?

要把 n 个盘从 A 移到 C(顺时针 2 格)

① 先把上面 n−1 个盘从 A 移到 C(占位),需 F(n−1) 步

② 最大盘从 A 移到 B,1 步

③ 把 n−1 个盘从 C 移到 A(顺时针 1 格),需 G(n−1) 步

④ 最大盘从 B 移到 C,1 步

⑤ 再把 n−1 个盘从 A 移到 C,需 F(n−1) 步

合计 2F(n−1) + G(n−1) + 2

F(n) = 2F(n−1) + G(n−1) + 2

2
G(n) 递推式怎么来的?

要把 n 个盘从 A 移到 B(顺时针 1 格)

① 把 n−1 个盘从 A 移到 C(让位),需 F(n−1) 步

② 最大盘从 A 移到 B,1 步

③ 把 n−1 个盘从 C 移到 B(顺时针 1 格),需 F(n−1) 步

合计 2F(n−1) + 1

G(n) = 2F(n−1) + 1

📊 逐项验证样例

nG(n)F(n)是否与样例一致
112n = 1 → 2(题面未给,但可推理)
257✅ 与样例 7 一致
31521✅ 与样例 21 一致
43159(继续递推)
563163
🔑
为什么不能只用"移 2 格"这一个状态?因为在递推过程中,"把 n−1 个盘从 C 移到 A"这一步是移 1 格(C→A),不是移 2 格。所以必须同时维护 F 和 G 两个状态——这是本题的核心难点,也是"递推题需要设计合适状态"的典型例子。
04
解法对比
双向递推 O(n) vs 记忆化搜索

⚔️ 解法对比

🟢 双向递推(推荐) 推荐

从 n = 0 递推到 n,同时维护 F、G

  • 时间 O(n)
  • 代码 10 行
  • n = 20 时几乎瞬间
  • 状态定义清晰
💡
实现结构:for (k = 1; k <= n; k++) { long long nf = 2*f + g + 2, ng = 2*f + 1; f = nf; g = ng; }——注意要先算出新值再赋值,否则会互相污染。

🟠 记忆化搜索

写递归函数,用数组记录已算过的 F(k)、G(k)

  • 时间 O(n)
  • 代码稍长(要写两个函数)
  • 需要考虑递归深度
  • 本质相同
⚠️
两种都可以:递推更简洁,记忆化搜索的推导过程更贴近思维。对本题这种线性递推,递推写法既短又不会爆栈。

📈 性能对比

方案代码量适用性
双向递推约 10 行线性递推的最优写法
记忆化搜索约 25 行状态依赖复杂时更方便
05
算法流程图
从 n = 0 递推到 n
开始读入 n;f = 0(移 2 格),g = 0(移 1 格)k 从 1 到 nnewF = 2 × f + g + 2;newG = 2 × f + 1f = newF;g = newGk 还没到 n 吗?输出 f(n 个盘移 2 格的步数)结束k 加 1 继续递推
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔁 新汉诺塔步数计算器

输入圆盘数 n(1 ~ 20),程序会展示递推过程中每一步的 F、G 值。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    // f = 顺时针移 2 格(如 A → C)的步数
    // g = 顺时针移 1 格(如 A → B)的步数
    long long f = 0, g = 0;      // n = 0 时都不需要移动

    for (int k = 1; k <= n; k++) {
        long long nf = 2 * f + g + 2;   // 先算新值
        long long ng = 2 * f + 1;
        f = nf;                          // 再一起赋值,避免互相污染
        g = ng;
    }

    printf("%lld\n", f);
    return 0;
}
🔑
为什么要"先算新值再赋值"?因为 nf 和 ng 都用到了同一轮的 f、g。如果先写 f = nf; 再算 ng = 2 * f + 1;,f 已经被更新成新值了,ng 就会算错。递推中"同时更新多个状态"时务必小心这个陷阱。

📖 关键几行怎么看

代码作用为什么这样写
long long f = 0, g = 0初值0 个盘不需要移动
nf = 2 * f + g + 2F 递推两次 F(n−1) + 一次 G(n−1) + 两次单步
ng = 2 * f + 1G 递推两次 F(n−1) + 一次单步
f = nf; g = ng;同时更新必须先算出两个新值再赋值
⚠️
三个坑:① 只用 F 一个状态(漏掉 G,无法处理"移 1 格"那一步);② 用 int 存(n = 20 时答案约 5.8 × 10⁸,虽然勉强在 int 内,但中间量 2*f 可能溢出,用 long long 更安全);③ 先更新 f 再算 ng,导致数值错误。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
121 个盘:A→B→C,共 2 步
27题面样例 1
321题面样例 2
459继续递推 F(4) = 2×21+15+2 = 59
5163F(5) = 2×59+31+2 = 163
20运行验证最大值,考察 long long
✅
自查清单:① 两个状态都维护了吗?② 先算新值再赋值吗?③ 用 long long 了吗?

🚨 易错点清单

⚠️
只用一个状态:必须同时维护 F(移 2 格)和 G(移 1 格),因为递推过程中需要用 G。
⚠️
先更新 f 再算 ng:会用到被覆盖的值,结果错误。
⚠️
以为答案仍是 2ⁿ − 1:新规则下步数远大于经典汉诺塔。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(1)
n 最大
20
运算量
20 次

时间怎么算的?

空间都用在哪?

只需要 f、g 两个变量(连数组都不需要)。

✅ 20 次循环,瞬间完成。这题的难点在于"设计正确的递推状态",而不是效率。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 经典汉诺塔:H(n) = 2H(n-1) + 1 = 2^n - 1
long long hanoi(int n) { return (1LL << n) - 1; }

// 本题(顺时针限制):需要两个状态
// F(n) = 2F(n-1) + G(n-1) + 2     移 2 格
// G(n) = 2F(n-1) + 1              移 1 格

// 也可以合并成一个二阶递推
// 由 G(n) = 2F(n-1) + 1 得 G(n-1) = 2F(n-2) + 1
// 代入 F(n) = 2F(n-1) + 2F(n-2) + 3
// 验证:F(3) = 2×7 + 2×2 + 3 = 21 ✓

// 递推题的一般方法
// 1) 定义清楚状态(本题:移 k 格需要多少步)
// 2) 找出"最大元素"的处理方式
// 3) 写出状态之间的转移式
// 4) 确定初值,从初值递推到目标

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
状态设计移 1 格 / 移 2 格分别定义所有"操作受限"的递推题
同时更新多状态先算新值再统一赋值所有多变量递推
结构对比受限版 vs 经典版理解"限制条件如何改变复杂度"
🌟
思考题:本题的 F(n) 增长约为 2.73ⁿ,而经典汉诺塔是 2ⁿ。为什么加了限制会变慢这么多?(提示:因为"移 2 格"需要借用"移 1 格"的操作,形成一个更复杂的依赖网络,相当于每一步都要多绕路。可以把这个结果和 (1+√3)ⁿ 对照——从递推式的特征方程 r² = 2r + 2 解出来正是 1 + √3 ≈ 2.732。)