【顺时针单向递归与双状态递推】GESP四级 / CSP-J 题解：luogu-B4579 [GESP202609 四级] 新汉诺塔

CCF GESP 2026年9月认证（第十五次认证）C++ 四级试题，洛谷 B4579。本题严格遵循 CCF GESP 官方大纲规范，重点考察顺时针单向递归与双状态递推。题目逻辑严密，模型典型，是深入理解与掌握信奥核心考点的经典范例。

B4579 [luogu-B4579 [GESP202609 四级] 新汉诺塔]

🔗 洛谷原题传送门：B4579

题目要求

题目描述

经典汉诺塔有 A、B、C 三根柱子，初始 A 上有从小到大排列的 $n$ 个圆盘，目标是移到 C。 小杨添加了新规则：每一次移动，圆盘只能顺时针移动，即只能从 $A \to B$、$B \to C$ 或 $C \to A$；其它移动是不允许的。 在新规则下，给定圆盘数量 $n$，求将 $n$ 个圆盘从 A 移动到 C 所需的最少移动步数。

输入格式

输入一个正整数 $n$，表示圆盘的数量。

输出格式

输出一个整数，表示最少移动步数。

输入输出样例

样例输入 #1

2

样例输出 #1

7

说明/提示

$n \le 20$。对于 $n=3$，输出为 21。

题目分析与解题思路

1. 双状态分治递推定义： 由于只能顺时针移动，移动 1 步与移动 2 步性质不同，需要引入互相依赖的双状态：
   • 设 $f(n)$ 为将 $n$ 个盘顺时针移动 1 根柱子（如 $A \to B$）的最少步数；
   • 设 $g(n)$ 为将 $n$ 个盘顺时针移动 2 根柱子（如 $A \to C$）的最少步数。
2. 初始状态（$n=1$）：
   • $1$ 个盘 $A \to B$：直接移 $1$ 步，故 $f(1) = 1$；
   • $1$ 个盘 $A \to C$：必须经 $A \to B \to C$，共 $2$ 步，故 $g(1) = 2$。
3. 状态转移关系：
   • 求 $f(n)$（$A \to B$）：
     1. 前 $n-1$ 个盘 $A \to C$（顺移 2 步）：$g(n-1)$ 步；
     2. 第 $n$ 个盘 $A \to B$（顺移 1 步）：$1$ 步；
     3. 前 $n-1$ 个盘 $C \to B$（顺移 2 步）：$g(n-1)$ 步。 即：$f(n) = 2g(n-1) + 1$。
   • 求 $g(n)$（$A \to C$）：
     1. 前 $n-1$ 个盘 $A \to C$（顺移 2 步）：$g(n-1)$ 步；
     2. 第 $n$ 个盘 $A \to B$（顺移 1 步）：$1$ 步；
     3. 前 $n-1$ 个盘 $C \to A$（顺移 1 步）：$f(n-1)$ 步；
     4. 第 $n$ 个盘 $B \to C$（顺移 1 步）：$1$ 步；
     5. 前 $n-1$ 个盘 $A \to C$（顺移 2 步）：$g(n-1)$ 步。 即：$g(n) = 2g(n-1) + f(n-1) + 2$。
4. 数据范围：$n \le 20$，$g(20)$ 结果在 long long 范围内，时间复杂度 $\mathcal{O}(n)$。

完整参考代码 (C++11)

/**
 * Problem: luogu-B4579
 * Standard: C++11 (CCF GESP 官方大纲规范)
 * Author: OneCoder
 */

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) {
        return 0;
    }

    // f[i]: 顺时针跨 1 根柱子（A->B）
    // g[i]: 顺时针跨 2 根柱子（A->C）
    vector<long long> f(n + 1, 0);
    vector<long long> g(n + 1, 0);

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

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

    cout << g[n] << "\n";

    return 0;
}

考点归纳与备考建议

1. 考纲匹配度：严格对标 CCF GESP 四级考纲重点，绝不超纲，注重基础算法与逻辑建模规范；
2. 规范防范：所有代码严格以 C++11 标准编译运行，针对整数溢出、边界判断、空状态均做了详尽严整的防御性处理。