Hanoi(汉诺塔)问题

Hanoi(汉诺塔)问题

测试数据来自 Wujiang01/1088

据古印度神话,在贝勒斯的圣庙里安放着一块铜板,板上插有3根一尺长的宝石针。梵天在创造世界的时候,在其中的一根针上摆了由小到大共64片中间有孔的金片。如下图所示,为4片金片的情况。无论白天和黑夜,都有一位僧人负责移动这些金片,规则是一次只能将一片金片移一另一根针上,并且在任何时间以及任一根针上,小片永远在大片的上面。当64片金片都由最初的那根针上移到另一根针上时,这世界就将在一声霹雳中消失。
说明
编写程序,输入金片的数量,输出金片移动的过程。
输出说明:一行为一次的移动过程,每行的数据包含3个:第几片金片、从哪根针上移走、移到哪根针上,数据之间用空格分割。

测试案例1:
输入:

3

输出:

1 A C
2 A B
1 C B
3 A C
1 B A
2 B C
1 A C

测试案例2:
输入:

4

输出:

1 A B
2 A C
1 B C
3 A B
1 C A
2 C B
1 A B
4 A C
1 B C
2 B A
1 C A
3 B C
1 A B
2 A C
1 B C