7249. 汉诺塔 (Tower of Hanoi)
时间限制：1000 MS 内存限制：256 MB
题目描述
**时间限制**：1.00 s **空间限制**：512 MB ## 题目描述 汉诺塔游戏包含三个柱子（左、中、右）以及 $n$ 个大小各不相同的圆盘。初始时，所有圆盘都套在左侧的柱子上，且自顶向下按尺寸从小到大的顺序排列。 目标是将所有圆盘都移动到右侧的柱子上，移动中可以借助中间的柱子。每次移动时，你只能将某一个柱子最上方的圆盘移动到另一个柱子上。此外，不允许将大盘子放在小盘子上面。 你的任务是找出一个移动次数最少的解决方案。 ## 输入格式 唯一的一行包含一个整数 $n$，表示圆盘的个数。 ## 输出格式 第一行输出一个整数 $k$，表示最少的移动步数。 接下来 $k$ 行描述每一次移动，每行包含两个整数 $a$ 和 $b$，表示你将当前盘子从柱子 $a$ 移到柱子 $b$（其中 $1$ 表示左柱，$2$ 表示中柱，$3$ 表示右柱）。 ## 输入输出样例 ### 输入 #1 ``` 2 ``` ### 输出 #1 ``` 3 1 2 1 3 2 3 ``` ## 说明/提示 ### 数据规模与约定 * $1 \le n \le 16$