1、实验题目：栈的应用实验内容：Hanoi 塔问题。 （要求 4 个盘子移动，输出中间结果）实验目的：（1）掌握栈的特点及其存储方法；（2）掌握栈的常见算法以及程序实现；（3）了解递归的工作过程。设计分析：Hanoi 塔问题要求实现将一定数目 n 的直径各不相同的盘子从 A 塔移动到 C 塔，盘子事先在 A 中已经按直径大小从小到大层叠好了，越往底层直径越大，规定每次只能移动一个盘子，且不能出现小盘子上面有大盘子的情况。可以用递归的方法实现。先考虑最简单的情况，假设 n=1，即只有一个盘子，此时便可直接将其从 A 移动到C； n=2 时，小盘在上，大盘再下，此时可以借用中间的 B 塔来运输，即先将
2、小盘从 A 移至B，再将大盘从 A 移至 C，最后将小盘从 B 移至 C，这样便不会出现小盘在下，大盘在上的情况；然而当 n 越来越大时，移动的次数就会越来越多，看起来好像很复杂，其实其中的基本思想很简单：若 A 塔上有 n 个盘子，要将其全部移至 C 塔中，由于最底层盘的直径最大，则就要将其上面的 n-1 个盘子移至中间的 B 塔，再将最底层的盘子移至 C 塔上，完成这个工作后，就会发现下一步就是将中间 B 塔上的 n-1 个盘子移至 C 塔上，这就和第一步的工作类似了，只不过盘子少了一个，且所处的塔也发生了变化，此时可将 A 塔作为传输中介，将 B 塔上面的 n-2 个盘子移至 A 塔，之
3、后再将第 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
4、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“, printf(“其移动过程为:n“);Hanoi(n, A, B, C);测试用例：图 3-1程序执行初始界面如图 3-1 所示，提示输入 A 塔上层叠的盘子总数 n 值。图 3-2当输入 1 时，即 A 塔上只有一个盘子，输出其移动过程为 AC，表示仅一步
5、就能完成，只需将 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 塔问题的探索与解决，我了解了递归算法的原理和功能，原本看起来很复杂的问题模型，用递归函数调用仅几个简单的程序语句就表达出来了，体现出递归算法的高效性，很多问题都可以用递归算法实现，简单的如求阶乘，通过调用自身程序代码实现递归。今后我会尝试着用递归算法解决更多的实际问题。
