Tower of Hanoi

题目描述

河内塔游戏由三根柱子（左、中、右）和 n 个不同大小的圆盘组成。初始时，左柱按从上到下盘子大小递增的顺序放置着所有盘子。 目标是使用中柱把所有盘子移到右柱。每次移动可以把某根柱子的最上面的盘子移动到另一根柱子上。另外，不允许把较大的盘子放在较小的盘子上。 你的任务是找到一个使移动次数最少的解。

输入格式

唯一的输入行包含一个整数 n：盘子的数量。

输出格式

首先输出一个整数 k：最少的移动次数。 接着输出 k 行描述这些移动。每行有两个整数 a 和 b：表示将一个盘子从柱子 a 移到柱子 b。

2

3
1 2
1 3
2 3

提示

$1 \le n \le 16$

标签: CSES2165|入门题

来源

CSES2165|入门题