信息奥赛题解｜汉诺塔III

---

🚀 题目浏览

【题目描述】

约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。

现在我们改变游戏的玩法，不允许直接从最左（右）边移到最右（左）边（每次移动一定是移到中间杆或从中间移出），也不允许大盘放到小盘的上面。

Daisy 已经做过原来的汉诺塔问题和汉诺塔II，但碰到这个问题时，她想了很久都不能解决，现在请你帮助她。现在有 $N$ 个圆盘，她至少多少次移动才能把这些圆盘从最左边移到最右边？

【输入】

多组数据，请处理到文件结束。

每组数据包含一个正整数 $N\ (1\le N\le 35)$.

【输出】

对于每组数据，在一行内输出移动最小的次数。

【输入样例】

1
3
12

【输出样例】

2
26
531440

【原题链接】

https://vjudge.net/problem/HDU-2064

---

☘️ 题解分析

汉诺塔问题升级版，但是递归/递推的本质没有发生变化。

🧑🏻‍💻 C++ 代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 40;
LL f[N], n;

int main() {
    // 递推，预处理出所有答案
    f[1] = 2;
    for (int i = 2; i <= 35; i++) {
        f[i] = f[i - 1] * 3 + 2;
    }

    // 输出答案
    while (cin >> n) cout << f[n] << endl;

    return 0;
}