​版权信息​： NOIP 2007 普及组

任务总览

题目描述

给定 A、B、C 三根足够长的细柱，在 A 柱上放有 2n 个中间有孔的圆盘，共有 n 个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的。

现要将这些圆盘移到 C 柱上，在移动过程中可放在 B 柱上暂存。要求：

• 每次只能移动一个圆盘；
• A、B、C 三根细柱上的圆盘都要保持上小下大的顺序。

任务：设 Aₙ 为 2n 个圆盘完成上述任务所需的最少移动次数，对于输入的 n，输出 Aₙ。

输入格式

一个正整数 n，表示在 A 柱上放有 2n 个圆盘。

输出格式

一个正整数，表示完成上述任务所需的最少移动次数 Aₙ。

样例输入和输出

输入示例 1：

1

输出示例 1：

2

输入示例 2：

2

输出示例 2：

6

提示

• 对于 50% 的数据，1 ≤ n ≤ 25；
• 对于 100% 的数据，1 ≤ n ≤ 200。

题目分析

这是经典的汉诺塔问题，然而在本题中，每个尺寸的圆盘有两个相同的，因此我们需要进行一定的调整。通过递推关系可以推导出最小的移动次数。

设 Aₙ 为将 2n 个圆盘从 A 柱移动到 C 柱的最少移动次数。根据递推关系：

• Aₙ = 2 * Aₙ₋₁ + 2， 其中 Aₙ₋₁ 表示 2(n-1) 个圆盘从 A 移到 C 所需的最少移动次数。

时间复杂度分析

• 时间复杂度：O(n)，由于递推关系式可以通过简单的循环计算，时间复杂度是线性的。
• 空间复杂度：O(1)，只需要常数空间来保存中间结果。

结论

本题的关键是通过递推关系来快速计算出所需的最小移动次数。