GESP单向汉诺塔|为什么要记录两个递推状态
圆盘只能沿 A → B → C → A 移动。把一摞盘从 A 搬到 B,需要顺着走一根柱。从 A 搬到 C,则要顺着走两根柱。这两种任务的最少步数不同,所以分别记录:
- f[n] 表示 n 个盘顺着走一根柱的最少步数。
- g[n] 表示 n 个盘顺着走两根柱的最少步数。
空塔不用搬,f[0] 和 g[0] 都是 0。观察最大盘怎么走,就能写出递推式:
f[n] = 2 × g[n−1] + 1
g[n] = 2 × g[n−1] + f[n−1] + 2
样例有两个盘,算出 g[2] = 7。写代码时,先用上一轮的 f、g 算出两个新值,再一起更新。题目要求从 A 搬到 C,最后输出 g。
四张配图依次是题目与样例、递推解析与 7 步演示、Python 代码、C++ 代码。
题目出自 GESP 2026 年 9 月 C++ 四级 · 编程题 1。
GESP四级 汉诺塔 递推算法 C加加学习



