只允许 A→B、B→C、C→A 三种移动,求把 n 个圆盘从 A 移到 C 的最少步数。
经典汉诺塔中,n 个圆盘从小到大叠在 A 柱上,目标是把它们移到 C 柱且保持顺序,规则是每次只能移动一个圆盘、大盘不能压在小盘上。
新规则:圆盘只能从 A 移到 B、从 B 移到 C、或从 C 移到 A,其他方向的移动都不允许(即只能"顺时针"移动)。
给定 n,求最少移动步数。
样例:n = 2 → 7;n = 3 → 21。
递推状态定义循环移动限制long long
| 项目 | 说明 |
|---|---|
| 输入 | 一个正整数 n |
| 输出 | 最少移动步数 |
| 数据范围 | n ≤ 20 |
| 允许的移动 | 仅 A→B、B→C、C→A(顺时针) |
| 样例 | n = 2 → 7;n = 3 → 21 |
F(n) = 2F(n−1) + G(n−1) + 2G(n) = 2F(n−1) + 1F(0) = 0、G(0) = 0;由此 F(1) = 2、G(1) = 1先明确:F(n) 表示把 n 个盘顺时针移 1 格(如 A→B)的步数,G(n) 表示顺时针移 2 格(如 A→C)的步数。
| n | G(n):移 1 格 | F(n):移 2 格 | 计算依据 |
|---|---|---|---|
| 0 | 0 | 0 | 没有盘子,不用移动 |
| 1 | 1 | 2 | G(1) = A→B 一步;F(1) = A→B→C 两步 |
| 2 | 5 | 7 | G(2) = 2F(1)+1 = 5;F(2) = 2F(1)+G(1)+2 = 7 |
| 3 | 15 | 21 | G(3) = 2F(2)+1 = 15;F(3) = 2F(2)+G(2)+2 = 21 |
要把 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
要把 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
| n | G(n) | F(n) | 是否与样例一致 |
|---|---|---|---|
| 1 | 1 | 2 | n = 1 → 2(题面未给,但可推理) |
| 2 | 5 | 7 | ✅ 与样例 7 一致 |
| 3 | 15 | 21 | ✅ 与样例 21 一致 |
| 4 | 31 | 59 | (继续递推) |
| 5 | 63 | 163 |
从 n = 0 递推到 n,同时维护 F、G
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)
| 方案 | 代码量 | 适用性 |
|---|---|---|
| 双向递推 | 约 10 行 | 线性递推的最优写法 |
| 记忆化搜索 | 约 25 行 | 状态依赖复杂时更方便 |
输入圆盘数 n(1 ~ 20),程序会展示递推过程中每一步的 F、G 值。
点按钮开始 →
#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 + 2 | F 递推 | 两次 F(n−1) + 一次 G(n−1) + 两次单步 |
ng = 2 * f + 1 | G 递推 | 两次 F(n−1) + 一次单步 |
f = nf; g = ng; | 同时更新 | 必须先算出两个新值再赋值 |
int 存(n = 20 时答案约 5.8 × 10⁸,虽然勉强在 int 内,但中间量 2*f 可能溢出,用 long long 更安全);③ 先更新 f 再算 ng,导致数值错误。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
1 | 2 | 1 个盘:A→B→C,共 2 步 |
2 | 7 | 题面样例 1 |
3 | 21 | 题面样例 2 |
4 | 59 | 继续递推 F(4) = 2×21+15+2 = 59 |
5 | 163 | F(5) = 2×59+31+2 = 163 |
20 | 运行验证 | 最大值,考察 long long |
只需要 f、g 两个变量(连数组都不需要)。
✅ 20 次循环,瞬间完成。这题的难点在于"设计正确的递推状态",而不是效率。
// 经典汉诺塔: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 经典版 | 理解"限制条件如何改变复杂度" |
2.73ⁿ,而经典汉诺塔是 2ⁿ。为什么加了限制会变慢这么多?(提示:因为"移 2 格"需要借用"移 1 格"的操作,形成一个更复杂的依赖网络,相当于每一步都要多绕路。可以把这个结果和 (1+√3)ⁿ 对照——从递推式的特征方程 r² = 2r + 2 解出来正是 1 + √3 ≈ 2.732。)