递归程序结构研究

递归程序结构研究 MicrocomputerApplicationsVo1.16,No9,2000研究与 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 嵌型电脑应用2000年第 16卷第9期 点上还有更复杂的结构.它们统称为递归树,下面透一讨论. 1.具有简单链表结构的递归问嚣 这种递归的特点是相邻三项之间明显存在某种递归关 系,这方面的函数如阶乘,F/bonaec/数列ckerman函数等. 这类问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 结构如图2所示,和链表的结构有点类似层的处 理要借助n—l层(有时包括更深层次),上层的解决依赖于下 每一层的处理都非常简单.根据问题的同要求. 层的解嵌. 结点可单独求值,也可把所有结点练台起来求整个问题的 值.求Fibona~ci的第11-项与前n项和就分别对应这两方面的 l叫越.适屉深入 l层I1--l屉2层l层 叵叵口圈= 例1求2阶Ftbonaeci数列的第11-项. r00 F()篇1,一l LFib(一1)+Fib(n一2).n>】 语句(3),(6),(7)分别位于不同的条件分支中. 2具有树状结构的递归问题 有些问题本身具有树状形式的数据结构,例如二叉树, 广义表.八皇后问题,ol背包问题,迷宫寻径问题韶立方体 是,在每一层上具有多条进^深层递归操作的语,H有多 ? 22? 结点的分叉数相同. 第n一1层 圈3二又树状结构递归程序的执行过程 倒2二叉树遍历 (1)subporder(bt) (2)ifbt<>NILthen (3)oper(bt.data) (4)Porder(bt.1e) (5)Porder(bt.rc) (6)end[f (7)endsub 二叉树相当于每十结点具有两条进入深层递归操作F(n 一 1)的同题. 实际上链表相当于一叉树,八皇后相当于固定探度为8 的满八叉树,而广义表则相当于特殊的只对叶子操作的二叉 树,0l背包同题相当于满二叉树,迷宫寻径问题相当于西叉 树,超立方体寻径同题相当于满n叉树,超立方体的总结点数 S与I1-的关系为:s一2. 这类数据结构一般均可归结为多指针域的多叉树状结 构,如果把指针域设成数组,则可写成循环形式,如二叉树 的左右指针设为ch(O),ch(1).那么可以把porder(bt.1c), porder(btre)改写为 roy;=0tot Porder(bt.ch(i)) next 这样改写的好处是,对于八皇后问题中的八叉树.我们只 需要设置一个循环,而不需要连写八条进入深层递归的语 句.这样也易于理解.也达到了这类问题的归一化. 3复杂链表结构的递归问嚣 逐层津凡 第n届第n一1层第2层第1层 囤4复杂链结构递归程序的执行过程 这类问题的总体框架结掏也是链表,但是在对于每个结 MicrocomputerApplications"4o1.16,No.9,2000研究与设计截型电脑启甩2000年第 16掌第9期 点的处理上则非常复杂.这类问题的复杂性体现在准备性操 作P(丑)和恢复性操作H(n)上. l节和2节所讨论的两类递归同题都有相对固定的规 律,容易写出违归程序.有些问题,容易看出其上的递归性质 (如hanoi塔问题],九连环问题等),但是对于其上的操作按 照递归性质进行划分并不容易,因此编写程序很简单.这 类问题虽然在总体框架上是链表结构,由于每个结点址理上 的复杂性,用处理简单链表 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 来处理此类同题就显得无能 为力.但这类递归也不是通过增加进入探屡递归操作F(n 1)就可以完成,因此2节的方法也不适用. 这类问题还有一个共同的特点.为完成第ii层的全部操 作,需先操作阻碍完成第n层操作的其他层.为实现第n层 的具体操作G(n)作准备待G(n)完成后,逊要进行恍复性操 作H(n),之后才是进A探层递归操作(倒3的语句(7).例4 的语句(12),(27)).当然在作准备性操作P(J)过程中,可能 要用到递归语句(倒3的语句(5),倒4的晤句(9)(24) (25),但这些语句均不是指进入深层递归,只是准备性操作P (n)中包吉的语甸,因为当前层第n屡的具体操作G(n)还投 有完成,谈何进入深层递归.理解这类问题一定要把P(n),G (n),H(n),F(n—1)的作用区别开来.准确使用他们对理解问 题和编程将变得更加容易.下面通过倒子进一步兑】 倒3hanoi问题 问题描述如图5所示,把x轴上的三只直径不等的盘子 全部移到z轴上,每次髂动一只且移动过程巾大直径圆盘不 可放在小直径圈盘之上 囤53层hanoi塔 (1)Subhaitoi(n,x,Y.z) (2)ifn=ltheit (3)oper(I.fromxtoz) (4)else (5)hanoi(n—l,x,z,y) {准备性操作语句P(it)) (6)oper(ntfromxtoz) (7)hanoi(n一【.Y,x.z) {这条语句才是进^探层的递归操作.需要说叫的是虽 然是进入探层递归操作,但它除了表示层数的参数变化 外,其中x和Y的参数位置也交换了.逍说|月P(n)和G(n) 操作对进入探层递归造成了影响.但不是直接的.因为X轴与 Y轴的作用是等价的,把x与Y参数换位f7j犊完全l料台进入 深层递归的条件.这里如果我f『j改动问题?求,增加一条 规则,即最终完成的每层操作必须是从x轴移动到z轴.但 过墟操作没有这种限制.增加了这条规则后,问题就变得稍 微复杂了.导致了x轴与Y轴不等价,但是把递归问题结构 体现得更清楚了.有了这条规则后,显然这条语句不可作为进 入深层递归的语句,要把这条语甸改为 hano(n—1.x,y,z) 这才是避A寐层递归的操作.因为前面的P(丑)和G(丑) 操作对进^深层递归造成了影响,困此必须为进入深层递归 作恢复性操作,需在这条语句之前增加语句 hanoi(n--],Y,z,x) 这条语甸表示把所有n一1层从Y轴移至x轴) (8)eitd[f (9)endsub 有了上这样的分析基础,对于倒5的九连环问题就容 易用递归程序编写了,它的过程中就包含着进入探层递归前 的恢复性准备工作. 倒4九连环问题 问题描述见图6,7. 98765432l ? 23? 囤6九连环全国 图7A,B为1只环的装环过程,C, D,E为2只环的蓑环过程 九连环的操作包古有两个过程:装环过程和卸环过程.分 析如下: 卸环过程: (1)subdnring(n) (2)n一1then (3)oper(uitlock1) (4)else (5)fn一2then (6)oper(unlock2) (7)0口er(uitLock1) (8)else (9)dnring(n--2) {不是进入深层递归操作.只是为卸下第n层环的具体操 作做准备性操作P(n)) (1O)oper(unlockIt) (卸下第n只环,具体性操作G(n)) (11)ut)ring(n一2) MicrocomputerApplicationsVo1.16,No9,2000研究与设计t型电齄应用2000年第l6 卷第9期 {要把所有剩下的n一2其环装上后,才可以满足进入深 层的递归操作.这条语句就是进入探层递归的慨复性操作H (n)} (12)dnring(n--1) {进入深层递归操作} (13)endif (14)endif (15)end5ub 装环过程: (16)subupring(n) (17)ifn—lthen (18)oper(1ock1) (19)else (20)ifn一2then (21)oper(1ock2) (22)oper(1ock1) (23)else (24)upring(n—1) {不是进入深层递归操作,其是为装上第n只环作准备性 操作P(n)) (25)dnring(n--2) {这条语句仍旧是为装上第n只环作准备性操作P(n) (26)oper(1ockn) {装上第n只环J (27)upring(n--2) {进入睬层递归操作) (28)endif (29)endif (3O)endsub 总上所述,较为复杂的递归问题的程序一般结构: (1)subl-e~ursJon(n) (2)if满足出口条件then (3)出口操作; (4)else (5)第n层的准备性操作P(n); (6)第n层具体性操作G(n); (7)进入深层递归前的恢复性操作H(n); (8)进入深层递归recu~sion(n一1);(可能包含多条递归 语句) (9)endtf (10)endsub 四,结束语 上面讨论的三种结构之间并非相互独立,而是相互联系, 简单链表结构是树状结构的特殊情况.相当于每个结点都为 简单的一叉树问题,而对于复杂链表结构则相当于每个结点 都比较复杂的一叉树问题.通过对递归问题的进行由简单到 复杂的讨论得出丁递归程序的一般结构与设计递归程序的 一 般方法.从而使复杂递归程序的设计变得较为窖易. 参考文献 [1]严蔚敏等着,《数据结构》清华大学出柱社,1995年 [2]蔡经球.《一类递归算法的多种计算 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 机器比较》,《小型 擞型计算机未统}2000年3月第2l卷第3期 [3]蔡蛀球,《关干递归变换之"函数嵌入法的若干研宽》,{计 算机 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 与设计}1995年3月第l6卷第3期 [4]蔡蛀球,<递归程序变换在特殊函数公式推导中的应用》, 《小型微型计算机亲统》l993年5月第l4卷第5期 [5]梁晋清等,《程序设计》上海交通大学出版社,1994年 [6]Andrew.S.Tanenbaum,~[D/stributingOperationSystem) 清华大学出版社1999年 (收稿日期2000年6月8日) (上接第2O贾) 号的信号为微机ISA总线的信号.带撇号的为接至实验母板 ISA总线插槽的信号,EN'为连动开关的一路信号. 三,新实验台的附加效果 新设计的实验台可用来进行原有的所有实验由于是在 高档机上使用,所以可充分利用机器的软件资源,如操作系 统,各种高级语言等.用DOS上的TurboC,Windows匕的 VB,VC等编写实验程序已成为可能.因此可大大提高编程效 率及效果,如做A/D实验时,可动态显示模拟世的趋势另 外也可加入一些原来因编程量太大而:殴不J的实验,如双 机间的协议通信等. ? 24? 新实验台的另一附加效果是一机多用.一台微机既可傲 微机系统设计实验和接口实验,又可用于其他软件开发.这样 可提高实验室的利用率. 参考文献 [1]束传乃主蝙《386/486微型计算机系统原理与堆谬)人民 邮电出版社,1995 [2]量渭清,王换招《高档擞机接口裢术及应用》西安交通大学 出版杜.1995 (收稿日期:2000年5月15日)