1096_HanoiTower问题（递归函数）

Hanoi Tower问题，中文叫汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。

传说故事是这样的：大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

下面是3层汉诺塔的搬动过程示意图。

如果考虑一下把64片黄金圆盘，由一根柱子移到另一根柱子上，并且始终保持上小下大的顺序。这需要多少次移动呢？

这里需要递归的方法。假设有n片，移动次数是f(n)。显然

f(1)=1

f(2)=3

f(3)=7，且 f(k+1)=2*f(k)+1

此后不难证明  f(n)=2ⁿ-1

n=64时，f(64) = 2⁶⁴-1=18446744073709551615

有多个测试用例，每个测试用例占一行，是一个正整数n，表示有n个盘子。

对每个测试用例，输出搬动盘子的次序。

三根柱子的编号为 "a"，"b" 和 "c"，一开始所有盘子在a柱，最终目标是c柱子。

每次搬动的输出格式为     "源柱子-->目标柱子"，

如    a-->b  表示把a柱子最上面的盘子搬到b柱子的最上面。

每个测试用例之间输出一个空行。

3
2
4
1

a-->c
a-->b
c-->b
a-->c
b-->a
b-->c
a-->c

a-->b
a-->c
b-->c

a-->b
a-->c
b-->c
a-->b
c-->a
c-->b
a-->b
a-->c
b-->c
b-->a
c-->a
b-->c
a-->b
a-->c
b-->c

a-->c

本题主要训练递归函数的写法。

当然，一般的递归函数都是可以改写为非递归形式的。有兴趣的同学可以研究以下非递归实现的汉诺塔解法。