#G1192. [GESP202609 四级] 新汉诺塔
[GESP202609 四级] 新汉诺塔
[GESP202609 四级] 新汉诺塔
时间限制:1.0 s 内存限制:512.0 MB
题目描述
汉诺塔问题是最经典的递推问题之一:
有三个可以放圆盘柱子,编号为 A、B 和 C。
开始时柱子 A 上套着 n 个圆盘,它们从上到下按照从小到大的顺序排列。
我们的任务是要把这 n 个圆盘移到柱子 C 上,并保持它们的原有顺序不变。
在移动圆盘的过程中,需要遵守以下规则:
- 圆盘只能从一根柱子顶部拿出,从另一根柱子顶部放入。
- 每次只能移动一个圆盘。
- 小圆盘必须时刻位于大圆盘之上。
小杨在学习了汉诺塔问题后,决定添加一个新规则:
- 每一次移动,圆盘只能从 A 移动到 B,从 B 移动到 C,或者从 C 移动到 A;其它移动是不允许的。
在新规则下,给定圆盘数量 n,试问最少移动步数是多少?
输入格式
输入一个正整数 n,表示圆盘的数量。
输出格式
输出一个整数,表示在新规则下将 n 个圆盘从 A 移动到 C 所需的最少移动步数。
样例 #1
样例输入 #1
2
样例输出 #1
7
样例解释
以下步骤是最佳的(编号为 1 的是小盘,为 2 的是大盘):
- 将 1 从 A 移动到 B;
- 将 1 从 B 移动到 C;
- 将 2 从 A 移动到 B;
- 将 1 从 C 移动到 A;
- 将 2 从 B 移动到 C;
- 将 1 从 A 移动到 B;
- 将 1 从 B 移动到 C。
可以证明没有更少步骤可以完成这个任务。
样例 #2
样例输入 #2
3
样例输出 #2
21
数据范围
- 对于所有数据,。