第6章 递 归 6.1 递归的概念 6.2 递归算法的设计 6.3 递归过程和递归工作栈 6.4 递归算法的效率分析

Slides:



Advertisements
Similar presentations
因数与倍数 2 、 5 的倍数的特征
Advertisements

一、 一阶线性微分方程及其解法 二、 一阶线性微分方程的简单应用 三、 小结及作业 §6.2 一阶线性微分方程.
2.8 函数的微分 1 微分的定义 2 微分的几何意义 3 微分公式与微分运算法则 4 微分在近似计算中的应用.
2.6 隐函数微分法 第二章 第二章 二、高阶导数 一、隐式定义的函数 三、可微函数的有理幂. 一、隐函数的导数 若由方程 可确定 y 是 x 的函数, 由 表示的函数, 称为显函数. 例如, 可确定显函数 可确定 y 是 x 的函数, 但此隐函数不能显化. 函数为隐函数. 则称此 隐函数求导方法.
2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
2 、 5 的倍数特征 集合 2 的倍数(要求) 在百数表上依次将 2 的倍数找出 并用红色的彩笔涂上颜色。
阻塞操作. 在 linux 里,一个等待队列由一个 wait_queue_head_t 类型的结构来描述 等待队列的初始化: static wait_queue_head_t testqueue; init_waitqueue_head(&testqueue);
§3.4 空间直线的方程.
圆的一般方程 (x-a)2 +(y-b)2=r2 x2+y2+Dx+Ey+F=0 Ax2+Bxy+Cy2+Dx+Ey+ F=0.
一、二阶行列式的引入 用消元法解二元线性方程组. 一、二阶行列式的引入 用消元法解二元线性方程组.
《高等数学》(理学) 常数项级数的概念 袁安锋
常用逻辑用语复习课 李娟.
小学生游戏.
第四章 函数的积分学 第六节 微积分的基本公式 一、变上限定积分 二、微积分的基本公式.
第5章 定积分及其应用 基本要求 5.1 定积分的概念与性质 5.2 微积分基本公式 5.3 定积分的换元积分法与分部积分法
第三节 格林公式及其应用(2) 一、曲线积分与路径无关的定义 二、曲线积分与路径无关的条件 三、二元函数的全微分的求积 四、小结.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
Examples for transfer function
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
全国计算机等级考试 二级基础知识 第二章 程序设计基础.
在PHP和MYSQL中实现完美的中文显示
强连通分量 无向图 1、任意两顶点连通称该图为连通图 2、否则将其中的极大连通子图称为连通分量 A D C B E 有向图
走进编程 程序的顺序结构(二).
辅导课程六.
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
以ISI平台为例,为您演示一下如何在Endnote文献中查看该文献的References
What have we learned?.
本节内容 模拟线程切换 视频提供:昆山滴水信息技术有限公司 官网地址: 论坛地址: QQ交流 :
动态规划(Dynamic Programming)
用event class 从input的root文件中,由DmpDataBuffer::ReadObject读取数据的问题
第七章 操作符重载 胡昊 南京大学计算机系软件所.
宁波市高校慕课联盟课程 与 进行交互 Linux 系统管理.
第4章 非线性规划 4.5 约束最优化方法 2019/4/6 山东大学 软件学院.
第一章 函数与极限.
C++语言程序设计 C++语言程序设计 第七章 类与对象 第十一组 C++语言程序设计.
数列.
专题作业.
C语言程序设计 主讲教师:陆幼利.
EBNF与操作语义 请用扩展的 BNF 描述 javascript语言里语句的结构;并用操作语义的方法描述对应的语义规则
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
$9 泛型基础.
顺序表的删除.
概 率 统 计 主讲教师 叶宏 山东大学数学院.
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
11.1 递归的定义 11.2 常见递归问题 11.3 递归的实现 11.4 递归转化为非递归的一般过程 11.5 递归的时间和空间复杂度
离散数学─归纳与递归 南京大学计算机科学与技术系
6.1递归的概念 若一个算法直接的或间接的调用自己本身,则称这个算法是递归算法。 存在算法调用自己的情况: (1)问题的定义是递推的
姚金宇 MIT SCHEME 使用说明 姚金宇
1、递归的概念 2、递归函数的设计 3、递归过程与递归工作栈 4、例 5、递归过程的非递归化
第4章 Excel电子表格制作软件 4.4 函数(一).
iSIGHT 基本培训 使用 Excel的栅栏问题
用穷举法设计程序 南京师范大学 教育技术系 倪佳慧
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
3.16 枚举算法及其程序实现 ——数组的作用.
第4课时 绝对值.
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
学习任务三 偏导数 结合一元函数的导数学习二元函数的偏导数是非常有用的. 要求了解二元函数的偏导数的定义, 掌握二元函数偏导数的计算.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
本节内容 C语言的汇编表示 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
第二节 函数的极限 一、函数极限的定义 二、函数极限的性质 三、小结 思考题.
正弦、余弦函数的性质 华容一中 伍立华 2017年2月24日.
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
C++语言程序设计 C++语言程序设计 第九章 类的特殊成员 第十一组 C++语言程序设计.
插入排序的正确性证明 以及各种改进方法.
创建、启动和关闭Activity 本讲大纲: 1、创建Activity 2、配置Activity 3、启动和关闭Activity
使用Fragment 本讲大纲: 1、创建Fragment 2、在Activity中添加Fragment
§4.5 最大公因式的矩阵求法( Ⅱ ).
第二次课后作业答案 函数式编程和逻辑式编程
一元一次方程的解法(-).
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
Presentation transcript:

第6章 递 归 6.1 递归的概念 6.2 递归算法的设计 6.3 递归过程和递归工作栈 6.4 递归算法的效率分析 第6章 递 归 6.1 递归的概念 6.2 递归算法的设计 6.3 递归过程和递归工作栈 6.4 递归算法的效率分析 6.5 转化递归算法为非递归算法 6.6 回溯法

6.1 递归的概念 递归(Recurtion)是一种有效的算法设计方法。递归的数学定义是:若一个对象部分地包含他自身,或要用他自身给自己下定义,则称这个对象是递归的对象。递归算法的定义是:若一个算法直接地或间接地调用自己,则称这个算法是递归算法。简单地说,递归算法就是有自调用的算法。

递归分两种情况: 1.定义是递归的 许多对象的定义是递归的。例如,许多数学概念的定义就是递归的。阶乘函数的常见定义是: 当n=0时 (6―1) 当n>0时

显然,这是一个循环过程定义。一旦n给定,我们就可由这个循环过程定义得出n!。例如,n=4,则有4!=4×3×2×1。 观察上边的等式,有4!=4×3!。 因此我们有阶乘函数的另一种定义为: 当n=0时 (6―2) 当n>0时

这种定义方法用阶乘函数自己定义了阶乘函数(只是阶乘值更小一些),我们称(6―2)式的定义法是递归定义法。 另一个用递归方法定义的数学概念例子是斐波那契数列。斐波那契数列Fib(n)的递归定义是: 当n=0或n=1 (6―3) n>1

又例如我们在第4章讨论过的链表结点也是一种递归定义。我们去掉链表结点类的成员函数,把链表结点改写成只包含数据域data和指针域next的结构体,便可以更清楚地理解链表结点定义的递归性。链表结点的结构体定义如下: struct ListNode { Datatype data; ListNode*next; };

在上述链表结点结构体的定义中,结构体ListNode的定义中用到了它自身,即指针域next是一种指向自身类型的指针。 仔细分析可以发现链表的定义是递归的,第7章将要讨论的树和二叉树的定义也都是递归的。

2.问题的解法是递归的 有些问题的解法是递归的。一个典型的例子是折半查找算法。折半查找算法也称作二分查找算法。它要解决的问题是:在一个有序(不失一般性设为由小到大的正序)的线性表a中查找是否存在一个数据元素x。 C ++ 语言的折半查找算法如下: int BSearch(elemtypea[],elemtypex,intlow,inthigh) //在下界为low、上界为high的数组a中,折半查找数据元素x { int mid;

if(low>high)return-1;//查找失败出口 mid=(low+high)/2;//查 找区间折半 if(x==a[mid])returnmid;//查找成功出口  //若x<a[mid],在下界为low上界、为mid-1的数组a中,折半查找数据元素x if(x<a[mid]) return(BSearch(a,x,low,mid-1));

//若x>a[mid],在下界为mid+1、上界为high的数组a中,折半查找数据元素x Else return(BSearch(a,x,mid+1,hig h)); }

另一个典型的例子是汉诺塔问题的求解。汉诺塔问题是:设有3根标号为A,B,C的柱子,在A柱上放着n个盘子,每一个都比下面的略小一点,要求把A柱上的盘子全部移到C柱上。移动的规则是:(1)一次只能移动一个盘子;(2)移动过程中大盘子不能放在小盘子上面;(3)在移动过程中盘子可以放在A,B,C的任意一个柱子上。

这个问题用常规的非递归方法求解甚至不能首先确定问题的解是否存在,我们用递归方法分析考虑如下。设盘子的总数为n,我们给A柱上的盘子从上至下编号为1到n。当n=1时,问题可直接求解,即我们可直接把A柱上的盘子移到C柱上;当n>1时,移动由以下三步组成:   (1)用C柱做过渡把A柱上的n-1个盘子移到B柱上; (2)把A柱上的最后一个盘子移到C柱上; (3)用A柱做过渡把B柱上的n-1个盘子移到C柱上。

图6―1 n=4的汉诺塔问题移动过程

上述n个盘子的汉诺塔问题的递归求解思路是:把移动n个盘子的汉诺塔问题归结为移动n-1个盘子的汉诺塔问题,把移动n-1个盘子的汉诺塔问题归结为移动n-2个盘子的汉诺塔问题,……把移动2个盘子的汉诺塔问题归结为移动1个盘子的汉诺塔问题;对于1个盘子的汉诺塔问题如前所述可直接求解。在1个盘子的汉诺塔问题解决后,可以解决2个盘子的汉诺塔问题,……在n-1个盘子的汉诺塔问题解决后,可以解决n个盘子的汉诺塔问题,这样n个盘子的汉诺塔问题最终就得以解决。

6.2 递归算法的设计 递归算法就是算法中有直接或间接调用算法本身的算法。递归算法的设计方法和上述问题的递归解法的分析思路类同,是一种分而治之的算法设计方法。递归算法或者称为分而治之算法的思想是:对于一个较为复杂的问题,把原问题分解成几个相对简单且类同的子问题,这样原问题的解决就变成了对子问题的解决,而子问题的子子问题最终是可以直接求解的。

并不是每个问题都适宜于用递归算法求解。适宜于用递归算法求解的问题应具有如下三点基本要素: (1)问题具有某种可借用的类同自身的子问题描述的性质; (2)相对于原问题来说,子问题将更加简化; (3)某一有限步的子问题(也称作本原问题)有直接的解存在。

这三点基本要素是一个问题存在递归算法的充分必要条件。当一个问题存在这三点基本要素时,设计该问题的递归算法的方法是: (1)把对原问题的求解分解成对子问题的求解; (2)设计递归出口,即求解本原问题。  下面两个例子具体示范了问题的递归算法设计方法。

例6―1 根据阶乘的递归定义设计求n的阶乘的递归算法。n的阶乘的递归定义为: 阶乘递归函数设计如下: #include<stdlib.h> #include<iostream.h> long Fact (intn) {

intx; longinty;  if(n<0) { cout<<"参数n错"<<endl; exit(1); }  if(n==0)return1; //递归出口  x=n-1; y=Fact(x);//求解子问题

returnn*y; //对原问题的求解是在对子问题求解的基础上实现的 } 为使初学者能透彻理解递归算法,我们给出一个以n=3调用阶乘递归函数的主函数如下,然后我们分析上述递归函数的执行过程。

main( ) { Long int fn;   fn=Fact(3); cout<<"fn ="<<fn<<endl; } 该程序对阶乘递归函数调用的执行过程如图6―2所 示。图中,带箭头的弧线旁的数值代表函数的返回值, 最终有fn=6。

图6―2 n=3的阶乘递归函数执行过程

每次进入下一次Fact( )函数调用前,由于当前的操作尚未执行完,因此需要保存当前工作的参数,然后才能进入下一次Fact( )函数调用。此时除函数名Fact、参数n需保存外,局部变量x和y也需保存。支持递归函数设计的C++语言(以及其他一些高级语言)是用一个堆栈来实现各次递归调用前的参数保存的。当Fact()函数要进行下一次递归调用时,

系统首先把前述的4个参数通过进栈操作保存到堆栈中;当Fact( )函数调用遇到递归出口语句(即当n=0)时,递归调用结束;在每次返回上一次递归函数调用前,系统首先通过退栈操作把保存在堆栈中的参数恢复出来。n=3的阶乘递归函数调用的系统堆栈区的动态变化过程如图6―3所示,图中符号*表示值尚未知,堆栈采用第3章讨论的顺序堆栈。

图6―3 n=3的阶乘递归函数调用系统堆栈变化过程

例6―2设计汉诺塔问题的递归算法。汉诺塔问题重述如下:设有3根标号为A,B,C的柱子,在A柱上放着n个盘子,每一个都比下面的略小一点,要求把A柱上的盘子全部移到C柱上。移动的规则是:(1)一次只能移动一个盘子;(2)移动过程中大盘子不能放在小盘子上面;(3)在移动过程中盘子可以放在A,B,C的任意一个柱子上。首先,分析汉诺塔问题可知,盘子的个数n是必须的一个输入参数,对n个盘子,可从上至下依次编号为1,2,…,n;其次,输入参数还需有3个柱子的代号,我们令3个柱子的参数名分别为fromPeg,auxPeg和toPeg;

最后,汉诺塔问题的求解是一个处理过程,因此算法的输出是n个盘子从柱子fromPeg借助柱子auxPeg移动到柱子toPeg的移动步骤。我们设计每一步的移动为如下形式: Move Disk I from Peg X to Peg Y 结合上一节我们讨论过的汉诺塔问题的递归求解思路,汉诺塔问题的递归算法可设计如下: #include<iostream.h> void Towers(int n,char fromPeg,charau xPeg,char to Peg)

//把n个盘子从fromPeg借助auxPeg移至toPeg { if(n==1) //递归出口 cout <<"MoveDisk1fromPeg"<<fromPeg <<"toPeg"<<toPeg<<endl; return; }   //把n-1个盘子从fromPeg借助toPeg移至auxPeg Towers(n-1,fromPeg,toPeg,auxPeg);

//把盘子n由fromPeg直接移至toPeg cout <<"Mov eDisk"<<n<<"fromPeg" <<fromPeg<<"toPeg"<<to Peg<<endl;   //把n-1个盘子再从auxPeg借助fromPeg移至toPeg Towers( n-1,auxPeg,fromPeg,toPeg);

我们设计如下的主程序: Void main ( void) { Int n;  cout<<"输入盘子个数:"; cin>>n;  Towers(n,′A′,′B′,′C′); }

程序的一次运行如下: 输入盘子个数:4 Move Disk 1 from Peg A to Peg B Move Disk 2 from Peg A to Peg C Move Disk 1 from Peg B to Peg C Move Disk 3 from Peg A to Peg B Move Disk 1 from Peg C to Peg A Move Disk 2 from Peg C to Peg B Move Disk 4 from Peg A to Peg C

Move Disk 2 from Peg B to Peg A Move Disk 1 from Peg C to Peg A Move Disk 3 from Peg B to Peg C Move Disk 1 from Peg A to Peg B Move Disk 2 from Peg A to Peg C Move Disk 1 from Peg B to Peg C

6.3 递归过程和递归工作栈 我们知道,对一个非递归函数的调用,在函数调用前要保存以下三方面的信息: (1)返回地址; 6.3 递归过程和递归工作栈 我们知道,对一个非递归函数的调用,在函数调用前要保存以下三方面的信息: (1)返回地址; (2)本函数调用时与形参结合的实参值,包括函数名和函数参数; (3)本函数的局部变量值。 当函数调用返回时,要首先释放当89初保存的实参值和局部变量值,然后按保存的返回地址返回。

对一个递归函数的调用,在函数调用前也要保存上述三方面的信息,但因为递归函数的自调用特性,上述保存信息的方法将由于函数不断地自调用,返回地址、实参值和局部变量值互相重叠,因此不能使用。递归函数保存上述三方面信息的方法是使用一个称作“运行时栈”的堆栈。每一层递归调用所需保存的信息构成一个工作记录,在每进入下一层递归调用时就建立一个新的工作记录,并把这个工作记录进栈到运行时栈,成为运行时栈的新栈顶;每退出一层递归调用,就从“运行时栈”退栈一个工作记录。因为栈顶的工作记录必定是当前正在运行层的工作记录,所以栈顶的工作记录又称为活动记录。

6.4 递归算法的效率分析 汉诺塔问题来源于印度的一个古老传说。汉诺塔问题的原始问题是:传说印度婆罗门庙里有一个塔台,台上有3根标号为A,B,C的用钻石做成的柱子,在A柱上放着64个金盘,每一个上面的全盘都比下面的略小一点。移动金盘的条件是:一次只能移动一个金盘,移动过程中大金盘不能放在小金盘上面。庙里的僧人一直移动不停。传说断言当把A柱上的金盘全部移到C柱上的那一天就是世界的末日。

我们再来讨论斐波那契数列的计算问题。斐波那契数列Fib(n)的递归定义是:

上述定义可直接转变为递归求值过程,递归的出口条件是Fib(0)=0,Fib(1)=1;当n>1时,递归调用公式为Fib(n)=Fib(n-2)+Fib(n-1),因此,求第n项斐波那契数列的递归函数如下: long Fib(int n) { if(n==0||n==1)return n; //递归出口 else return Fib(n-1)+Fib(n-2);//递归调用  }

上述递归函数求Fib(5)的递归计算过程如图6―4所示。由图可见,若要求Fib(5),要先求Fib(4)和Fib(3);而求Fib(4)时需先求Fib(3)和Fib(2);求Fib(3)时需先求Fib(2)和Fib(1);如此等等,总共需计算Fib(4)1次,计算Fib(3)2次,计算Fib(2)3次,计算Fib(1)5次,计算Fib(0)3次,累计递归调用的次数为15=24-1。

按归纳法可得出求斐波那契数列的递归函数Fib(n)的递归调用次数等于2n-1;若把图6―4左下角的两个子树Fib(1)和Fib(0)放到右下角的结点Fib(1)下,则图6―4是一棵完全二叉树,由完全二叉树的性质也可得出求斐波那契数列的递归函数Fib(n)的递归调用次数等于2n-1(关于完全二叉树和完全二叉树的性质将在下一章讨论)。因此,上述计算斐波那契数列的递归函数Fib(n)的时间复杂度为O(2n)。对于计算斐波那契数列Fib(n)问题,我们也可根据6―3式写出循环方式求解的函数如下:

图6―4 Fib(5)的递归调用树

longFib2(int n) { if(n==0||n==1)return n;  else long int oneBack=1,twoBack=0,curren t; for(inti=2;i<=n;i++) current=oneBack+twoBack;

twoBack=oneBack; oneBack=current; } return current; }

显然,上述循环方式的计算斐波那契数列的函数Fib2(n)的时间复杂度为O(n)。对比Fib2(n)和递归结构的Fib(n)可发现,循环方式的Fib2(n)算法在递推计算第n项的斐波那契数列时保存了当前已经计算得到的第n-1项和第n-2项的斐波那契数列,因此其时间复杂度为O(n);而递归方式的Fib(n)算法要计算第n项的斐波那契数列必须首先计算第n-1项和第n-2项的斐波那契数列,而某次递归计算得出的斐波那契数列,如Fib(3)无法保存,下一次要用到时还需要递归计算,因此其时间复杂度为O(2n)。

对于同一个问题,递归算法的时间复杂度是O(2n),而循环算法的时间复杂度是O(n),可见,求解斐波那契数列问题的循环算法效率要比递归算法效率高很多。一般情况下,若循环方式的算法和递归方式的算法均能求解该问题,通常循环方式算法的时间复杂度要比递归方式算法的时间复杂度低很多很多。

6.5 转化递归算法为非递归算法 总结我们本章至此讨论过的递归算法,可得出递归算法的两个特性: (1)递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题方法,对求解某些复杂问题,递归算法分析问题的方法是十分有效的。 (2)递归算法的时间效率通常非常差,其时间效率经常是实际应用中不可忍受的。

因此,第一,对求解某些问题时,我们希望用递归算法分析问题,用非递归算法具体求解问题;第二,有些计算机语言不支持递归功能,我们需要把递归算法转换为非递归算法;第三,递归算法是一次执行完的,这在处理有些问题(例如,7.5节将要讨论的二叉树分步遍历问题)时不合适。这样,也存在一个把递归算法转化为非递归算法的问题。

把递归算法转化为非递归算法有如下三种基本方法: (1)对于尾递归和单向递归的算法,可用循环结构的算法替代。 (2)自己用堆栈模拟系统的运行时栈,通过分析只保存必须保存的信息(因而可小幅度提高时间效率),从而用非递归算法替代递归算法。 (3)利用堆栈保存参数,由于堆栈的后进先出特性吻合递归算法的执行过程,因而可以用非递归算法替代递归算法。

6.5.1 尾递归和单向递归的消除 尾递归是递归调用语句只有一个,而且是处于算法的最后。我们以阶乘问题的递归算法Fact(n)为例讨论尾递归算法的运行过程。为讨论方便,我们再次列出阶乘问题的递归算法Fact(n),并简化掉参数n的出错检查语句,改写递归调用语句的位置在最后,算法如下: long Fact(intn) { if(n==0)return1; return n*Fact(n-1); }

分析上述算法可以发现,当递归调用返回时,返回到上一层递归调用的下一语句,而这个返回位置正好是算法的末尾。也就是说,以前每次递归调用时保存的返回地址、函数返回值和函数参数等实际上在这里根本就没有被使用。因此,对于尾递归形式的递归算法,不必利用系统的运行时栈保存各种信息。尾递归形式的算法实际上可变成循环结构的算法。循环结构的阶乘问题算法Fact2(n)如下:

longFact2(intn) { Int fac=1; for(inti=1;i<=n;i++) fac=fac*i; Return fac; }

尾递归是单向递归的特例。单向递归是指递归函数中虽然有一处以上的递归调用语句,但各次递归调用语句的参数只和主调用函数有关,相互之间参数无关,并且这些递归调用语句也和尾递归一样处于算法的最后。单向递归的一个典型例子是我们讨论过的计算斐波那契数列的递归算法Fib(n)。其中,递归调用语句Fib(n-1)和Fib(n-2)只和主调用函数Fib(n)有关,相互之间参数无关,并且这些递归调用语句也和尾递归一样处于算法的最后。

我们再次列出斐波那契数列的递归算法Fib(n)如下: long Fib(int n) { if(n==0||n==1)return n; //递归出口 else return Fib(n-1)+Fib(n-2); //递归调用 } 循环结构的斐波那契数列的算法Fib2(n)前面已经列出,此处不再列出。

6.5.2 模拟系统的运行时栈消除递归现以汉诺 塔问题的递归算法为例,讨论模拟系统的运行时栈把递归算法转换为非递归算法的问题。  例6―3 模拟系统的运行时栈把汉诺塔问题的递归算法转换为非递归算法。 我们再次列出汉诺塔问题的递归算法如下: #include<iostream.h> void Towers(int n,char fromPeg,char auxPeg,char toPeg)  { if(n==1)

{ cout <<"MoveDisk1fromPeg"<<fromPeg <<"toPeg"<<toPeg<<endl; return; } Towers(n-1,fromPeg,toPeg,auxPeg);cout <<"MoveDisk"<<n<<"fromPeg"<<fromPeg<<"toPeg"<<toPeg<<endl; Towers(n-1,auxPeg,fromPeg,toPeg);  }

由于汉诺塔问题的递归算法中有两处递归调用,再加上主调函数,所以非递归模拟算法中也应有三个模仿返回地址。三个返回地址分别为返回主调函数、返回第一次递归调用处和返回第二次递归调用处。在模拟算法中,这三个返回地址分别对应三个语句标号lable1、lable2和lable3,我们再用取值为1,2,3的一个变量模仿返回地址,因而在模拟递归算法中共有四个参数。(局部变量在整个递归调用中未发生变化,不用保存。)所以,非递归模拟算法中每次需保存算法的四个参数和一个模仿返回地址。

本应用例子从另一个角度也可看作是3. 3节学过的顺序堆栈类的应用。我们用3 本应用例子从另一个角度也可看作是3.3节学过的顺序堆栈类的应用。我们用3.3节的顺序堆栈类来模拟系统运行时栈,其数据元素类型Datatype定义如下: struct Datatype { short int retAddr; //模仿返回地址 int nParam; //参数n char fromParam; //参数fromPeg char auxParam; //参数auxPeg char to Param; //参数toPeg };

完整的汉诺塔问题用顺序堆栈类来模拟系统运行时栈的算法如下: struct Datatype { short int retAddr; int nParam;  char fromParam; char auxParam; char toParam; }; //定义顺序堆栈类的Datatype

#include"SeqStack.h“ //包括顺序堆栈类 Void SimTowers(int n,char fromPeg,char auxPeg,char toPeg) { Datatype currArea;//当前工作区 SeqStacks;//模拟系统运行时堆栈的堆栈 chartemp; shortinti;

//当前工作区初始化 currArea.retAddr =1; currArea.n Param=n; currArea.fromParam=fromPeg; currArea.a uxParam=auxPeg; currArea.toParam=toPeg; s.Push(currArea); //当前工作区入栈

//以下为模拟出口 start: if(currArea.nParam==1) { cout <<"MoveDisk1fromPeg"<<currArea.fromParam  <<"toPeg"<<currArea.toParam<<endl; i=cu rrArea.retAddr; currArea=s.Pop(); //出栈恢复当前工作区 switch(i)

{ case 1:gotolable1; case2:gotolable2; case3:gotolable3; }  //以下模拟递归自调用过程 s.Push(currArea); //当前工作区入栈 currArea.nParam --;

Temp =currAre a.auxParam; currArea.auxParam =currArea.toParam; currArea.toP Aram =temp; currArea.retAddr =2; Goto start;

//以下模拟返回第一次递归调用 lable2: cout <<"MoveDisk"<< currArea.nParam<<"fromPeg" <<currArea.fromParam<<"t oPeg" <<currArea.toParam<<endl; s.Push(currArea); //当前工作区入栈 currArea.nParam --; temp =currArea.fromParam;

currArea.fromParam =currArea.auxParam; currArea.auxParam =temp; currArea.retAddr =3;   gotostart;  //以下模拟返回第二次递归调用 lable3: i=currArea.retAddr; currArea=s.Pop(); //出栈恢复当前工作区

switch(i) { case1:gotolable1; case 2:gotolable2; case3:gotolable3; }  //以下模拟返回主调函数 lable1: return;

这个模拟汉诺塔问题的递归算法的系统运行时栈工作流程的算法虽然是非递归的,但却和原递归算法的系统内部执行流程类似。由于汉诺塔问题本身的算法复杂度就是O(2n),所以这个模拟算法的时间复杂度也是O(2n)。

6.6 回溯法 回溯法是求解复杂问题的又一种有效的方法。回溯法的思想是:对一个包括有很多结点,每个结点有若干个搜索分支的问题,设计算法为一个搜索过程,当搜索到某个结点,发现无法再继续搜索下去时,就让搜索过程回溯退到该结点的前一结点,继续搜索这个结点的其他尚未搜索过的分支;

如果发现这个结点也无法再继续搜索下去时,就让搜索过程回溯退到这个结点的前一结点继续这样的搜索过程;这样的搜索过程一直继续到搜索到问题的解, 或搜索完了全部可搜索分支没有解存在为止。

当问题有若干个解存在时,回溯法保证找到问题的一个解,但回溯法不能保证找到问题的最优解。 由于回溯法每前进一步在新的结点上进行的搜索过程和前一个结点的搜索过程类同,且使整个问题的搜索范围缩小一步,所以回溯法的算法本质上是一个递归算法。 下面我们以迷宫问题为例进一步讨论回溯法的思想和算法设计方法。

例6―4迷宫问题。一个迷宫是一些互相连通的交叉路口的集合,给定一个迷宫入口,一个迷宫出口,当从入口到出口存在通路时输出其中的一条通路,当从入口到出口不存在通路时输出无通路存在。对于像图6―5所示的迷宫,每个交叉路口除进来的路外有三个路口,分别是向左、向前和向右,我们假设迷宫中不存在环路。编制计算机模仿的迷宫问题算法并用图6―5验证。

要用计算机模仿迷宫问题,首先要把迷宫问题数值化。我们把每个路口定义成一个包括left、forward和right三个域的结构体。如果某个域的值为1表示该方向上有通路可继续走一步;如果某个域的值为0表示该方向上已无通路;全部这样的路口数值的集合就描述了一个具体的迷宫问题。此外,为算法设计方便,再在数值集合的前边加上路口的个数,在数值集合的后边加上迷宫的出口编号。这样,图6―5的数值化模拟文件"Maze1.dat"如下:

图6-5 迷宫问题的一个例子

6 0 2 0 3 5 6 0 0 4 0 0 0 0 0 0 7 0 0 文件的第一行是迷宫的路口个数,这里路口共有6个。 第二到第七行是编号1到编号6的6个路口的状态。例如, 第2行的020表示编号1的路口的状态是向左不通,向前通 到2号路口,向右不通。

图6―6 用回溯法解图6―5迷宫问题的搜索过程

用回溯法解图6―5所示的迷宫问题的搜索过程如图6―6所示。 按照面向对象程序设计的思想,我们把迷宫问题设计成一个类。其数据成员有路口个数mazeSize、出口Exit和路口集合*intSec;其构造函数读入如前所示的数据文件构造描述一个具体问题的迷宫类的对象;其搜索函数TravMaze(intSecValue)的输入参数intSecValue为当前所处的路口,搜索函数用回溯法搜索迷宫的所有分支,搜索函数是一个递归函数。迷宫类设计如下:

#include<stdlib.h> #include<fstream.h> structInterSection //路口的结构体定义  {  intleft; //向左 intfo rward; //向前 intright; //向右 };

classMaze //迷宫类定义 { private: int mazeSize; //路口个数 intExit;//出口 Int erSection*intSec; //路口集合 public: Maze(char*filename); //构造函数 int TravMaze(intintSecValue); //搜索函数 };

Maze::Maze(char*filename) { ifstreamfin; fin.open(filename,ios::in||ios::nocreate); //打开文件 if(!fin) cerr<<"数据文件无法打开!"; exit(1); }

fin>>mazeSize;//读入路口个数  intSec=newInterSection[mazeSize+1]; //建立mazeSize+1个元素的数组  for(inti=1;i<=mazeSize;i++)//读入全部路口的结构体数值 fin>>intSec[i].left>>intSec[i].forward>>intSec[i].right; fin>>Exit;//读入出口  fin.close();//关闭文件 }

//用回溯法搜索迷宫的所有分支,输入参数intSecValue为当前所处的路口 intMaze::TravMaze(intintSecValue) { //intSecValue>0为有路径存在,可以继续探索发现一条路径 if(intSecValue>0) if(intSecValue==Exit)//到达出口 cout<<intSecValue<<"<=="

;//输出路口号 return1;//返回1 } Else if(TravMaze(intSec[intSecValue].left))//向左探索 { //只有探索成功,即返回值为1,才执行以下语句 cout<<intSecV alue<<"<=="; //输出路口号 return1; //返回1

} elseif(TravMaze(intSec[intSecValue].forward)) //向前探索 { cout<<intS ecValue<<"<=="; return1; } Else if(TravMaze(intSec[intSecValue].right))//向右探索 cout<<intSecValue<<"<==";

return1; } } //intSecValue =0为无路径存在,返回0 return0; 上述成员函数TravMaze(intSecValue)只有在探索到某个路口满足该路口编号等于出口编号,表明已探索到一条路径时,才从出口编号开始回退显示探索到的一条从入口到达出口的路径上的所有路口编号,所以显示的路径序列应该是从出口到入口。

求解图6―5的迷宫问题的主函数如下: Void main(void) { char file Name[20]={"Maze1.dat"}; Maze m(fileName); int start=1;   if(m.TravMaze(start)) cout<<endl<<"此迷宫的一条通路如上所示"<<endl; else cout<<"此迷宫无通路!"<<endl; }

程序的运行结果如下: 7<==6<==2<==1<== 此迷宫的一条通路如上所示 从上述求解图6―5的迷宫问题程序的运行结果,读者可通过实例再次分析迷宫类搜索成员函数的执行过程。我们的问题是:运行结果为什么首先显示出口“7<==”?搜索成员函数Trav Maze( )的执行过程是怎样的?

上述迷宫类中的搜索成员函数Trav Maze(intSec Value)算法假设了迷宫中的路径不构成环路。对于一个如图6―7所示的带环路的迷宫,Trav Maze(intSec Value)算法将由于重复不断的进栈操作而出错。有兴趣的读者可以重新编写一个不重复走已走过的路径的搜索算法。

图6―7 带环路的迷宫