汉诺塔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塔问题得以解决。源程序代码：#includevoid Move(char A, char B)printf(%c-%cn, A, B);void Hanoi(int n, char A, char B, char C)if (n = 1)Move(A, C);elseHanoi(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塔上只有一个盘子，输出其移动过程为AC，表示仅一步就能完成，只需将A塔上的盘子移至C上。这是最简单的情形，也是作为解决hanoi塔问题递归算法的出口，当n值大于1时，由递归算法层层推进，最终确定到这一个盘子的移动过程。图3-3当n=2时输出移动过程如图3-3所示，第一步AB表示将A最上面的盘子（直径小的）移至B，AC则表示将A最上面的盘子（直径大的）移至C，最后在将B最上面的盘子移至C即可。图3-4当n=3时输出移动过程如图3-4所示，此时需要7步完成整个过程，随着n值的增大，移动的步数也随之增多，总结可得移动步数S与n的关系为S=2n-1。实验总结：通过此次对Hanoi塔问题的探索与解决，我了解了递归算法的原理和功能，原本看起来很复杂的问题模型，用递归函数调用仅几个简单的程序语句就表达出