汉诺塔Hanoi问题.doc

实验题目：
栈的应用

实验内容：
Hanoi塔问题。（要求4个盘子移动，输出中间结果）

实验目的：
（1）掌握栈的特点及其存储方法；
（2）掌握栈的常见算法以及程序实现；
（3）了解递归的工作过程。

设计分析：
Hanoi塔问题要求实现将一定数目n的直径各不相同的盘子从A塔移动到C塔，盘子事先在A中已经按直径大小从小到大层叠好了，越往底层直径越大，规定每次只能移动一个盘子，且不能出现小盘子上面有大盘子的情况。可以用递归的方法实现。
先考虑最简单的情况，假设n=1，即只有一个盘子，此时便可直接将其从A移动到C；n=2时，小盘在上，大盘再下，此时可以借用中间的B塔来运输，即先将小盘从A移至B，再将大盘从A移至C，最后将小盘从B移至C，这样便不会出现小盘在下，大盘在上的情况；然而当n越来越大时，移动的次数就会越来越多，看起来好像很复杂，其实其中的基本思想很简单：若A塔上有n个盘子，要将其全部移至C塔中，由于最底层盘的直径最大，则就要将其上面的n-1个盘子移至中间的B塔，再将最底层的盘子移至C塔上，完成这个工作后，就会发现下一步就是将中间B塔上的n-1个盘子移至C塔上，这就和第一步的工作类似了，只不过盘子少了一个，且所处的塔也发生了变化，此时可将A塔作为传输中介，将B塔上面的n-2个盘子移至A塔，之后再将第n-1个盘子移至C中，这样重复进行下去就可以将它们全部运输过去。而对于第一步工作中将上面n-1个盘子移至B，则又需要将其上n-2个盘子移至此时视为传输中介的C，完成这一步又要将其上的n-3个盘子移至B，像这样层层递归进去，最终就会知道第一个盘子及最上面直径最小的盘子先移到何处，这即为递归出口，而后的盘子移动方案也都确定了，最终就可将所有的盘子按规则移至C塔，至此，Hanoi塔问题得以解决。

源程序代码：
#include<stdio.h>

void Move(char A, char B)
{
printf("%c-->%c\n", A, B);
}
void Hanoi(int n, char A, char B, char C)
{
if (n == 1)
Move(A, C);
else
{
Hanoi(n-1, A, C, B);
Move(A, C);
Hanoi(n-1, B, A, C);
}
}
void main()
{
int n;
char A = 'A', B = 'B', C = 'C';
printf("请输入盘子总数n值:");
scanf("%d", &n);
printf("其移动过程为:\n");
Hanoi(n, A, B, C);
}

测试用例：

图3-1
程序执行初始界面如图3-1所示，提示输入A塔上层叠的盘子总数n值。

图3-2
当输入1时，即A塔上只有一个盘子，输出其移动过程为AàC，表示仅一步就能完成，只需将A塔上的盘子移至C上。这是最简单的情形，也是作为解决hanoi塔问题递归算法的出口，当n值大于1时，由递归算法层层推进，最终确定到这一个盘子的移动过程。

图3-3
当n=2时输出移动过程如图3-3所示，第一步AàB表示将A最上面的盘子（直径小的）移至B，AàC则表示将A最上面的盘子（直径大的）移至C，最后在将B最上面的盘子移至C即可。

图3-4
当n=3时输出移动过程如图3-4所示，此时需要7步完成整个过程，随着n值的增大，移动的步数也随之增多，总结可得移动步数S与n的关系为S=2n-1。

实验总结：
通过此次对Hanoi塔问题的探索与解决，我了解了递归算法的原理和功能，原本看起来很复杂的问题模型，用递归函数调用仅几个简单的程序语句就表达出来了，体现出递归算法的高效性，很多问题都可以用递归算法实现，简单的如求阶乘，通过调用自身程序代码实现递归。今后我会尝试着用递归算法解决更多的实际问题。