7-8 Hanoi塔问题
分数 20
作者 黄龙军
单位 绍兴文理学院
Hanoi(汉诺)塔问题是一个经典的递归问题。
设有A、B、C三个塔座;开始时,在塔座A上有若干个圆盘,这些圆盘自下而上,由大到小地叠在一起。要求将塔座A上的圆盘移到塔座C上,并仍按同样顺序叠放。在移动过程中要求遵守如下规则:
每次只能移动一个圆盘;
任何时刻都不允许将较大的圆盘压在较小的圆盘之上;
在满足前两条规则的前提下,可将圆盘移至A、B、C中任何一塔座上。
例如,3个圆盘的初始状态如下:
n=3 时,移动过程如输出样例所示,其中,每行中的整数表示该次移动的圆盘编号,用A->C表示将圆盘从塔座A移到塔座C,其他类似。
输入格式:
测试数据有多组,处理到文件尾。对于每组测试,输入一个整数n(1<=n<=8)。
输出格式:
对于每组测试,在输出将n个圆盘从塔座A移动到塔座C的移动过程,每行是一个形如:i a->b 的输出,表示将编号为i的圆盘从塔座a移到塔座b。圆盘编号为1 n(最小的编号为1,次小的编号为2,……,最大的编号为n)。每两组测试数据之间留一个空行。
输入样例:
3
输出样例:
1 A->C
2 A->B
1 C->B
3 A->C
1 B->A
2 B->C
1 A->C