详细解释版本

---

题目解析：新汉诺塔问题

这是一道经典汉诺塔问题的变种。在原规则基础上，限制了圆盘只能按 (A -> B -> C -> A) 的单向循环移动。这就要求我们在移动时，不能像原来那样一步到位，而是要通过中转来完成。

为了清晰表述，我们先定义两个状态数组：

• (f[i])：表示将 (i) 个圆盘移动一根柱子（例如 (A ->B)）所需的最少步数。
• (g[i])：表示将 (i) 个圆盘移动两根柱子（例如 (A ->C)）所需的最少步数。

---

1. 状态转移方程推导

情况一：移动两根柱子（求 (g[i])）

我们要让 (n) 个圆盘从 (A ->C)（跨越两根柱子），因为最大的圆盘不能直接一步到位，必须分两步走：

1. 首先，我们需要让上面的 (n-1) 个圆盘从 (A ->C)，也就是让 (n-1) 个圆盘全部移动两根柱子（这样最下面那个最大的才能从 (A) 移动，不然动不了）。步数：(g[i-1])
2. 然后，让最大的圆盘从 (A ->B) 走一步。步数：(+1)
3. 接着，让 (n-1) 个圆盘从 (C ->A)。由于规则是单向循环的，从 (C) 绕回 (A) 相当于走一根柱子（这样最大的圆盘才能从 (B -> C)）。步数：(f[i-1])
4. 接着，让最大的圆盘从 (B ->C) 走一步。步数：(+1)
5. 最后，让 (n-1) 个圆盘从 (A -> C)，也就是让 (n-1) 个圆盘全部移动两根柱子。步数：(g[i-1])

我们列出式子并整理：
g[i] = g[i-1] + 1 + f[i-1] + 1 + g[i-1]
整理可得：
g[i] = 2 *g[i-1] + f[i-1] + 2

情况二：移动一根柱子（求 (f[i])）

我们要让 (n) 个圆盘从 (A -> B)（跨越一根柱子），步骤如下：

1. 首先，我们需要先让 (n-1) 个圆盘从 (A -> C)，也就是让 (n-2) 个圆盘全部移动两根柱子腾出位置。这里采用拆分为 (n-2) 的思维推导：先把 (n-2) 个盘子从 (A) 移动两根柱子（(g[i-2])），再把第 (n-1) 个盘子走一根柱子（(+1)），最后把 (n-2) 个盘子移动两根柱子（(g[i-2])）。
2. 然后，底下的那个最大的圆盘直接从 (A ->B) 移动一步。
3. 最后，把刚才移走的 (n-1) 个圆盘从 (C -> B) 移回来。

列出式子：
f[i] = g[i-2] + 1 + g[i-2]
整理可得：
f[i] = 2 \times g[i-2] + 1

---

3. 代码 (C++)

#include<bits/stdc++.h>
using namespace std;
long long f[1000], g[1000];
// f数组：n个圆盘走一根柱子需要几步
// g数组：n个圆盘走两根柱子需要几步
int main(){
    int n;
    cin >> n;    
    // 初始化边界条件
    g[1] = 2;
    g[2] = 7;
    // 递推求解
    for(int i = 3; i <= n; i++){
        // 推导 f[i]：先移走 n-2 个(两步)，移动第 n-1 个(一步)，再移回 n-2 个(两步)
        f[i] = 2 * g[i-2] + 1;
        // 推导 g[i]：n-1个走两步 + 最大盘走一步 + n-1个走一步 + 最大盘走一步
        g[i] = 2 * g[i-1] + 2 + f[i];
    }
    // 题目要求把 n 个圆盘从 A 移动到 C（走两根柱子）
    cout << g[n];
    return 0;
}