实验6+汉诺塔游戏的迭代实现

1、软件综合项目开发训练实验6 迭代汉诺塔游戏李伟键李伟键第2页/共15页递归递归：函数f()直接调用自己，或通过另一函数g()间接调用自己。f()|f()g() | f();| g(); f(); | |使用递归函数的两个条件一个大的问题可以逐步转化为一个或多个小的类似问题，直到简化为一个简单问题；递归有明确的终止条件。第3页/共15页递归的使用求解n的阶乘n！n! = n(n-1)(n-2).21 = n(n-1)!int factorial ( int num )if ( num =1; i-)sum = i * sum;printf(n!等于%d, sum);第6页/共15页递归vs迭代递

2、归程序更直接，更好理解，编程更简单；递归程序的实现比迭代程序的实现需耗费更多的时间和空间。因此，在具体实现的实现，尽可能把递归程序转化为迭代程序。 并非所有的递归程序都有对应的迭代程序；- 尾递归：递归作为最后一条语句，并且仅此一个递归调用。可以直接转化为迭代（如求n！的递归）；- 非尾递归，无法直接转化，需要通过使用堆栈，来实现递归。第7页/共15页递归转化为迭代把递归算法转化为非递归算法有如下三种基本方法： (1)通过分析，跳过分解过程，直接用循环结构的算法实现求值过程； (2)递归为尾递归，直接转化为迭代算法； (3)自己用栈模拟系统的运行时栈,通过分析只保存必须保存的信息,从而用非递归

3、算法替代递归算法。第8页/共15页汉诺塔问题有三根杆子（命名为A、B和C）。A杆上N（N1）个穿孔的圆盘，盘的尺寸由下到上依次变小。要求按照如下规则将A杆上的所有圆盘移至C杆上：每次只能移动一个圆盘；1. 大盘不能叠在小盘下面。第9页/共15页汉诺塔游戏第10页/共15页基本思路移动n个圆盘的基本思路将n-1个盘子从A杆移动B杆，在此过程中可使用C杆作为临时存放区；将最后一个盘子（最大）从A杆移动C杆；将n-1个盘子从B杆移动C杆，在此过程中可使用A杆作为临时存放区。移动n-1个圆盘的思路同移动n个圆盘。当n=1时，过程结束。第11页/共15页迭代思路(1/2)1.recursion_hano

4、(n-1,A,C,B); / 将 上 n-1 个圆盘移动到 B上2.moveAC(n, A,C); /将最大的圆盘移动到 C上 3.recursion_hano(n-1,B,A,C); /将B上的圆盘移动到C上先把1移完，再移2，最后再移3。移1时，又是：先把1移完，再移2，最后再移3。可以看出，如上符合一个堆栈的特点：后入先出。入栈顺序：3，2，1。接着出栈，1。处理1：入栈3，2，1第12页/共15页迭代思路(2/2)使用一个堆栈来存放函数参数，对这些函数参数，依次调用函数recursion_hano或者moveAC来处理： 如果是recursion_hano函数，依次把3.recursi

5、on_hano(n-1,B,A,C) 、2.moveAC(n, A,C)和1.recursion_hano(n-1,A,C,B)入堆栈 如果是moveAC函数，直接移动，也就是屏幕打印出移动某圆盘，从x柱到y柱。函数参数要存放入堆栈，需要为ElemType声明一个结构体，结构体内放入所需的各种参数(n,num, A,B,C)： n:要移动的盘子最大编号 num:移动盘子个数- 如果num为1，则为moveAC- 如果num=n，则为recursion_hano A，B，C:移动的柱子编号 AC，B为中转第13页/共15页编码思路初始化堆栈S依次把(n-1, n-1,B,A,C) 、 (n, 1,A,B,C) 、(n-1,n-1,A,C,B)入栈 /注意入栈顺序是反过来的bool b = pop(S, p); / 一次出栈，存入pwhile(堆栈非空) if(p.num =1 ) moveAC; else / p.n = p.num 继续压栈； b = pop(S,