汉诺塔步数

题目描述

相传在古代印度的 Bramah 庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。

有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只盘子的话，按照上述规则将64只盘子从一个柱子移至另一个柱子上，所需时间约为5800亿年。

假定这三根柱子的编号分别为A、B、C，现在在柱子A上面放了 $n$ 个盘子，正好是把这 $n$ 个盘子从小到大的顺序放着，B和C上先都是空着，现在要将这 $n$ 个盘子按照上面的规则从A移动到C，请输出最少移动步数和每次移动的过程。

输入格式

输入一个整数 $n$，$1 \le n \le 8$。

输出格式

输出每步的具体移动过程。

样例输入 #1

3

样例输出 #1

1:A-C
2:A-B
3:C-B
4:A-C
5:B-A
6:B-C
7:A-C

数据范围

$1 \le n \le 8$

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐。

测试点分布