6003 - 汉诺塔
时间限制 : 1 秒
内存限制 : 128 MB
相传在古代印度的 Bramah 庙中,有位僧人整天把三根柱子上的金盘倒来倒去,原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。
移动过程中需要遵守规则:每次只允许移动一只盘,且在任何时刻大盘不得落在小盘上面。
有人会觉得这很简单,真的动手移盘就会发现,如以每秒移动一只盘子的话,按照上述规则将64只盘子从一个柱子移至另一个柱子上,所需时间约为5800亿年。
假定这三根柱子的编号分别为A、B、C,现在在柱子A上面放了n个盘子,正好是把这n个盘子从小到大的顺序放着,B和C上先都是空着,现在要将这n个盘子按照上面的规则从A移动到C,请输出具体移动的每个盘子的顺序。
输入
一个整数n,1<=n<=15。
输出
输出每次移动的盘子的柱子的编号,每次移动输出一行。
例如,从A柱上移动一个盘子到C,请输出“A-C”。
样例
输入
3
输出
A-C A-B C-B A-C B-A B-C A-C