




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第一章 数学预备知识 第二章 导引与基本数据结构第三章 递归算法武汉科技大学理学院信息与计算科学系杨 波cookie_2008年9月2008-09-01版权所有:杨波,武汉科技大学理学院 递归递归是一种强有力的设计方法递归的效率问题递归的实现机制执行调用时将返回地址进栈为递归子程序准备数据:实参形参值将指令流转入新一级子程序入口处2008-09-01版权所有:杨波,武汉科技大学理学院 执行返回时保存中间计算结果数据从栈顶取出返回地址值按返回地址返回若有变参或函数,进行参数或函数回传递归的满足要求问题P的描述涉及到规模规模发生变化时,问题的性质不发生变化问题的解决有出口,即递归有结束的条件200
2、8-09-01版权所有:杨波,武汉科技大学理学院 递归的表现int P(参数表) if (递归出口) 简单操作 else 简单操作; P; 简单操作; 初始情况递归部分2008-09-01版权所有:杨波,武汉科技大学理学院 阶乘函数阶乘函数定义为:public int Factorial(int n) if(n=0) return 1; return n*Factorial(n-1); 2008-09-01版权所有:杨波,武汉科技大学理学院 斐波那契(Fibonacci)数列 无穷数列1,1,2,3,5,8,13,称为Fibonacci数列,递归定义为: public int F(int n)
3、 if(n=1) return 1; return F(n-1)+F(n-2);时间复杂度:指数阶F(5)= F(4) + F(3) = (F(3) + F(2) + (F(2) + F(1) = (F(2) + F(1) + (F(1) + F(0) + (F(1) + F(0) +1) = (F(1) + F(0) + 1) + (1 +1) +(1 + 1) +1) 2008-09-01版权所有:杨波,武汉科技大学理学院 欧几里德算法求最大公因子算法定义为: public static int GCD(int a,int b) if(b=0) /递归结束条件 return a; retu
4、rn GCD(b,a%b); /递归执行部分GCD(22,8)=GCD(8,22%8)=GCD(8,6)=GCD(6,8%6)=GCD(6,2)=GCD(2,6%2)=GCD(2,0)=22008-09-01版权所有:杨波,武汉科技大学理学院 已知元素x,判断x是否在a1:n中 public static void main(String argv) int x; int a; a=new int5; for(int i=1;in) return 0; else if(aj=x) return j; else return Search(j+1,x,a); 2008-09-01版权所有:杨波,
5、武汉科技大学理学院 整数划分问题将正整数n表示成一系列正整数之和,n=n1+n2+nk,其中n1n2nk1,k1。正整数n的这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分数,记作p(n)。 例如:正整数6有如下11中不同的划分,所以p(6)=11。6;5+1;4+2,4+1+1;3+3,3+2+1,3+1+1+1;2+2+2,2+2+1+1,2+1+1+1+1;1+1+1+1+1+1。 2008-09-01版权所有:杨波,武汉科技大学理学院 在正整数n的所有不同的划分中,将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。 q(n,1)=
6、1, n11q(n,m)=q(n,n), mn q(n,n)=1+q(n,n-1) q(n,m)=q(n,m-1)+q(n-m,m), nm1 当最大加数n1不大于1时,任何正整数n只有一种划分形式,即 1+1+1+1最大数n1实际上不能大于n。因此,q(1,m)=1正整数n的划分由n1=n的划分和n1n-1的划分组成 正整数n的最大加数n1不大于m的划分由n1=m的划分和n1m-1的划分组成 6;5+1;4+2,4+1+1;3+3,3+2+1,3+1+1+1;2+2+2,2+2+1+1,2+1+1+1+1;1+1+1+1+1+1。 2008-09-01版权所有:杨波,武汉科技大学理学院 pu
7、blic static int q(int n,int m) if(n1)|(m1) return 0; if(n=1)|(m=1) return 1; if(nm) return q(n,n); if(n=m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m); 2008-09-01版权所有:杨波,武汉科技大学理学院 消去递归直接递归消去规则(包括两方面)将递归过程中出现递归的地方,用等价的非递归代码来代替(后面将给出的规则1-7)对return语句做适当处理(后面将给出的规则8-13)2008-09-01版权所有:杨波,武汉科技大学理学院 消去规则消去
8、递归调用过程的开始部分,插入说明为栈的代码并将其初始化为空。(在一般情况下,栈用来存放参数、局部变量、函数的值,和每次递归调用的返回地址。) 将标号Li附于第一条可执行语句。然后,对于每一处递归调用都用一组执行下列规则的指令来代替。 将所有参数和局部变量的值存入栈。栈顶指针可作为一个全局变量来看待。 建立第i个新标号Li,并将i存入栈。这个标号的i值将用来计算返回地址。此标号放在规则7所描述的程序段中。 计算本次调用的各实在参数(可能是表达式)的值,并将这些值赋给相应的形式参数。 插入一条无条件转向语句转向过程的开始部分。 如果这过程是函数,则对递归过程中含有此次函数调用的那条语句作如下处理:
9、将该语句的此次函数调用部分用从栈顶取回该函数值的代码来代替,其余部分的代码按原描述方法照抄,并将4中建立的标号附于这条语句上。如果此过程不是函数,则将4建立的标号附于6所产生的转移语句后面的那条语句。 2008-09-01版权所有:杨波,武汉科技大学理学院 对return语句的处理如果栈为空,则执行正常返回。 否则,将所有输出参数的当前值赋给栈顶上的那些对应的变量。 栈中有返回地址标号的下标,就插入一条此下标从栈中退出的代码,并把这个下标赋给一个未使用的变量。 从栈中退出所有局部变量和参数的值并把它们赋给对应的变量。 如果这个过程是函数,则插入以下指令,这些指令用来计算紧接在return后面的
10、表达式并将结果值存入栈顶。 用返回地址标号的下标实现对该标号的转向。2008-09-01版权所有:杨波,武汉科技大学理学院 求数组中的最大元素A1:n2008-09-01版权所有:杨波,武汉科技大学理学院 int Max1(int i) int j,k; if(iaj) k=i; else k=j; else k=a.length-1; return k;public int Max2(int i) /java伪代码 int stack; int j,k,addr,n,top; n=a.length()-1; /数组a中存放了待查询的元素 stack=new int2*n+1; /规则1 to
11、p=0; /规则1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /规则8 else /规则9 addr=stacktop;top=top-1; /规则10 i=stacktop;top=top-1; /规则11 top=top+1;stacktop=k; /规则12 if(addr=2) go to L2 /规则13 规则1:过程的开始部分,插入说明为栈的代码并将其初始化为空。(在一般情况下,栈用来存放参数、局部变量、函数的值,和每次递归调用的返回地址。)规则2:将标号Li附于第一条可执行语句。然后,对于每一处递归调用都用一组
12、执行下列规则的指令来代替。规则3:将所有参数和局部变量的值存入栈。栈顶指针可作为一个全局变量来看待。 规则4:建立第i个新标号Li,并将i存入栈。这个标号的i值将用来计算返回地址。此标号放在规则7所描述的程序段中。 规则5:计算本次调用的各实在参数(可能是表达式)的值,并将这些值赋给相应的形式参数。 规则6:插入一条无条件转向语句转向过程的开始部分。 规则7:如果这过程是函数,则对递归过程中含有此次函数调用的那条语句作如下处理:将该语句的此次函数调用部分用从栈顶取回该函数值的代码来代替,其余部分的代码按原描述方法照抄,并将4中建立的标号附于这条语句上。如果此过程不是函数,则将4建立的标号附于6
13、所产生的转移语句后面的那条语句。 规则8:如果栈为空,则执行正常返回。 规则10:栈中有返回地址标号的下标,就插入一条此下标从栈中退出的代码,并把这个下标赋给一个未使用的变量。 规则11:从栈中退出所有局部变量和参数的值并把它们赋给对应的变量。 规则12:如果这个过程是函数,则插入以下指令,这些指令用来计算紧接在return后面的表达式并将结果值存入栈顶。 规则13:用返回地址标号的下标实现对该标号的转向。 规则9:否则,将所有输出参数的当前值赋给栈顶上对应的那些变量2008-09-01版权所有:杨波,武汉科技大学理学院 012345678910public int Max2(int i) /
14、java伪代码 int stack; int j,k,addr,n,top; n=a.length()-1; /数组a中存放了待查询的元素 stack=new int2*n+1; /规则1 top=0; /规则1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /规则8 else addr=stacktop;top=top-1; /规则10 i=stacktop;top=top-1; /规则11 top=top+1;stacktop=k; /规则12 if(addr=2) go to L2 /规则13 例:求数组a1:5中最大元素
15、的算法,a1=3,a2=10,a3=8,a4=9,a5=412223224k=5addr=2i=45j=5k=4i=34j=4i=24k=2i=12j=22008-09-01版权所有:杨波,武汉科技大学理学院 改进1上述算法只是为了说明一般方法。 对于栈的处理实际上可以采用结构体或类的方式实现,上述stack中分别存放了参数值或者函数返回值和每次函数调用的返回地址(实际为标号的下标,在此均为2)。可以使用二维数组来实现堆栈。 2008-09-01版权所有:杨波,武汉科技大学理学院 public int Max2(int i) /java伪代码 int stack; int j,k,addr,n
16、,top; n=a.length()-1; /数组a中存放了待查询的元素 stack=new intn+12; /规则1 top=0; /规则1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /规则8 else addr=stacktop1; /规则10 i=stacktop0; /规则11 stacktop0=k; /规则12 if(addr=2) go to L2 /规则13 public int Max2(int i) /java伪代码 int stack; int j,k,addr,n,top; n=a.length()
17、-1; /数组a中存放了待查询的元素 stack=new int2*n+1; /规则1 top=0; /规则1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /规则8 else addr=stacktop;top=top-1; /规则10 i=stacktop;top=top-1; /规则11 top=top+1;stacktop=k; /规则12 if(addr=2) go to L2 /规则13 2008-09-01版权所有:杨波,武汉科技大学理学院 改进2由于过程只返回一个地方,所以不必重复存放返回地址。也不需要转向语句。
18、 2008-09-01版权所有:杨波,武汉科技大学理学院 public int Max2(int i) /java伪代码 int stack; int j,k,addr,n,top; n=a.length()-1; /数组a中存放了待查询的元素 stack=new intn+1; top=0; while(iaj) k=i; else k=j; return k; public int Max2(int i) /java伪代码 int stack; int j,k,addr,n,top; n=a.length()-1; /数组a中存放了待查询的元素 stack=new int2*n+1; /规则1 top=0; /规则1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /规则8 else addr=stacktop;top=top-1; /规则10 i=stacktop;to
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年制造业供应链JIT模式与物流协同物流供应链管理考核试卷
- 个人信用信息安全使用承诺函4篇
- 2025年智能网联汽车电池热管理系统考核试卷
- 2025年互联网行业元宇宙营销水平考试-虚拟商场中的品牌店铺设计与用户流量引导考核试卷
- 2025年制造业高端装备研发能力考核试卷-医疗装备智能维护
- 难点解析人教版八年级物理上册第6章质量与密度-密度综合训练试卷(含答案解析)
- 重难点解析人教版八年级物理上册第4章光现象-光的色散专题测试试题(含答案及解析)
- 难点解析-人教版八年级物理上册第6章质量与密度-密度专题攻克练习题(含答案详解)
- 重难点解析人教版八年级物理上册第5章透镜及其应用-5.5显微镜和望远镜达标测试试题(含解析)
- 2025年建筑工地智能监控系统合同协议
- 2025年下半年四川广元青川县招聘事业单位工作人员18人重点基础提升(共500题)附带答案详解
- 2025江西吉安市国资委出资监管企业外部董事人选招录6人备考考试题库附答案解析
- 人教版五年级数学上学期第三单元 小数除法综合提优卷(A)(含答案)
- 大庆市2025黑龙江大庆市机关事务服务中心所属事业单位选调工作人员10人笔试历年参考题库附带答案详解
- 电动机的PLC控制编程实例说课稿-2025-2026学年中职专业课-电器及PLC控制技术-智能设备运行与维护-装备制造大类
- 国企改革培训课件
- 2025年中国移动室分设计优化工程师招聘面试题库及答案
- 2025-2026学年粤教花城版(2024)小学音乐一年级上册教学计划及进度表
- 医院装修工程危险源辨识与安全措施
- 河南省委党校在职研究生入学考试真题及答案
- 服装搭配手册指南
评论
0/150
提交评论