|
#2
卧龙孔明2007-11-15 19:49
|
Description
Hanoi塔问题是每个新一代的的计算机科学家必须掌握的最著名的经典问题之一。传说在遥远的东方有一座庙，僧侣们尝试把一叠金盘从一根木桩上，从下到上尺寸逐步缩小。僧侣们尝试着按照一次只能移动一个金盘并且大的金盘永远不能放在小的金盘上面的规定，将这叠金盘移动到另外一个木桩上。总共有三个木桩，一个用于暂放金盘。按照推测，僧侣们完成他们的工作之时，正是地球毁灭之日。若真是这样，我们可不愿意助他们一臂之力了。
让我们假设僧侣们想把盘子从桩1移到桩3.我们希望开发一个算法，显示僧侣从木桩到木桩移动盘子的序列。
如果使用传统的方法来处理这个问题，会很快发现我们陷入到这堆盘子的管理之中而无法自拔。这个问题很棘手，似乎没有什么希望解决。然而，用递归的方法来处理这个问题，解决思路就很简单。移动n个盘子可以看成移动n-1的盘子（因此是递归问题），如下所示：
a）把n-1个盘子从桩1移到桩2，把桩3作为临时存放点。
b）把最后一个盘子（最大的）从桩1移到桩3。
c）把n-1个盘子从桩2移到桩子3，把桩1作为临时存放点。
当最后一次任务只有n=1个盘子要移动时（即基本情况），整个过程就结束了。这使值需要轻松地把盘子移过去就可以了，不再需要临时存放点。编写一个程序解决Hanoi塔问题。递归函数使用四个参数：
a）准备移动的盘子数
b）最初放置这些盘子的木桩
c）最后放置这些盘子的木桩
d）作为临时存放点的桩
程序应该打印出将这些盘子从起始桩和移动到目的桩所采取的准确步骤。例如，把三个盘子从桩1移动到桩3，程序应该打印出如下的移动序列：
1 -> 3 (表示把一个盘子从桩1移到桩3)
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3
Input
第一行1个整数t，表示有t组数据。以下t行，每行1个整数n，表示最初桩1有n个盘子。
Output
对于每组输入数据，打印一系列移动序列，每行打印一次移动操作，最后一行打印移动的次数。
Sample Input
2
2
3
Sample Output
1 -> 2
1 -> 3
2 -> 3
Total Steps: 3
1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3
Total Steps: 7
Hint
输出中冒号后有一空格
大家谁帮个忙啊..