#8833. [NOIP2007 普及组] Hanoi 双塔问题

[NOIP2007 普及组] Hanoi 双塔问题

版权信息​: NOIP 2007 普及组

任务总览

任务名称 时间限制 内存限制 分数
Hanoi 双塔问题 1 sec 125 MB 暂无

题目描述

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

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

image

  • 每次只能移动一个圆盘;
  • 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),只需要常数空间来保存中间结果。

结论

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