汉诺塔问题

题目描述

相传在古代印度的 Bramah 庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把 64 个一个比一个小的金盘从一根柱子上移到另一根柱子上去。 移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。 有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只盘子的话，按照上述规则将64只盘子从一个柱子移至另一个柱子上，所需时间约为 5800 亿年。 假定这三根柱子的编号分别为 A、B、C，现在在柱子 A 上面放了 n 个盘子，正好是把这 n 个盘子从小到大的顺序放着， B 和 C 上先都是空着，现在要将这 n 个盘子按照上面的规则从 A 移动到 C，请输出具体移动的每个盘子的顺序。

输入格式

输入一个整数 n，1<=n

输出格式

输出每次移动的盘子的柱子的编号，例如从 A 柱上移动一个盘子到 C，请输出“ A-C ”，每次移动输出一行。

3

A-C
A-B
C-B
A-C
B-A
B-C
A-C

提示

（暂无提示）

来源

童程童美