递归问题（精选7篇）
递归问题 篇1
[教学内容分析]
本课选自普通高中课程标准实验教科书《算法与程序设计》第三章第五节《用递归法解决问题》,内容包括自定义函数及调用、递归算法思想和程序实现。因为自定义函数往往是递归算法不可缺少的部分,因此教科书在讨论了什么是递归法之后,还介绍了什么是自定义函数,以及在VB中如何定义、调用自定义函数,这两者是本节的重点内容。递归算法比较抽象,学生理解起来有一定难度,是本节的难点。“汉诺塔”问题是一个经典的递归问题,本节通过“汉诺塔”游戏引入递归算法的思想,在对它作数学分析之后,用了两种方法——递归法和解析法来解决,通过这两种方法的比较,让学生体会递归法的特点。递归程序比较简单,学生可以在教师的指导下直接编写。学生对递归程序的理解有一定困难,可采用图解法帮助学生理解。
[教学目标]
知识与技能——理解什么是递归法,学会用递归法的思想分析问题;理解什么是自定义函数,掌握自定义函数的定义方法;学会用递归法编写程序解决问题。
过程与方法——归纳递归法解决实际问题的基本思想和基本步骤,指导学生完成具体任务;应用程序设计学习、验证递归法解决实际问题。
情感态度与价值观——引导学生针对趣味性问题和实际生活中遇到的问题进行思考、讨论,探索解决问题的方法和步骤;激发学生学习程序设计的兴趣,树立用程序设计解决实际问题的信心。
[教学重难点]
重点:什么是递归算法,VB中自定义函数的定义及使用。
难点:理解递归法的程序实现过程。
[教学策略]
本节课具有理论性和实践性都较强的特点,因此,在教学过程中,既要重视理论的教学,也要重视学生的实践,将枯燥的内容和生动有趣的任务结合起来,开展多种形式的教学活动,如:演示、实践、讨论、评价、小组协作、竞争等,让学生参与到教学活动中来,避免教师“一言堂”,这样才能有效地激发学生的学习兴趣。
本节课采用任务驱动教学法,整个教学过程由多个内容相关、难度递增的任务组成,教师通过对这几个任务的精心设计,引导学生逐步深入,最终完成教学目标。整个教学过程以学生自主探究为主,教师起辅导、帮助、引领的作用。一开始的任务难度较低,可以让学生独立完成,随着任务难度的逐渐增加,采用小组协作的方式。这样既照顾了学生的能力差异,也锻炼了协作能力,保证了学生共同进步。
[教学过程]
环节一:创设情境,提出问题
师:同学们,你们玩过汉诺塔游戏吗?
生1:玩过。
生2:听过,没玩过。
生3:什么是汉诺塔游戏啊?
…………
师:没关系,今天的课会让每一位同学都融入到这个游戏中。(屏幕显示)这是印度的一个古老的传说。传说中开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒,第一根上面套着64个金环,最大的一个在底下,其余的一个比一个小,依次叠上去。庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上,规定可利用中间的一根棒作为帮助,但每次只能搬一个,而且大的不能放在小的上面。相传神同时发了咒语,当所有的金环全部移完时,就是世界末日到来的时候。同学们,在这个故事中神的咒语果真能实现吗?这节课我们就来探讨一下这个问题。
[设计意图]虽然汉诺塔问题已流传很久,很多人都听说过,但毕竟有一部分人对它不熟悉,教师利用这个古老的神话,通过合理的设问引发学生对问题的思考,使学生自然而然地进入到学习的情境中来。
环节二:组织活动,自主探究
教师事先将准备好的汉诺塔游戏上传到校园网上供学生使用时下载。
师:网上根据这个故事开发的游戏很多,同学们现在使用的只是其中的一个。这是一个过关游戏,第一关是两个金环,而后依次类推,金环越来越多,步骤越来越多,难度越来越大,要求借助Second柱将First柱上的金环按照规则移到Third柱上,移动规则是:
(1)每次只能移一个金环。
(2)只能在三个柱子上存放。
(3)任何时候大金环不能放在小金环上面。
教师提示学生看大屏幕,开始游戏。
师:怎样用最少的步骤完成第一关呢?
第一关:2个金环。选学生上台演示移动过程。
当First杆上只有两个金环时,我们需要先将上面的小盘放在Second杆上,再将下面的大盘放在Third杆上,最后再把Second杆上的小盘移到Third杆上,这样第一关就通过了,如图1所示。由此可见通过第一关最少需要移动3步。
师:好!第一关我们已经顺利通过了,下面同学们两两结对去通过第二关。比一比,看谁移动的次数最少?
让学生两两结对,通过游戏自主探究3个金环时的最少移动次数。
这一环节用时不宜过多,10分钟左右即可。
在实践中不同的学生移动的次数可能不同,让他们记录下最少的移动次数是多少。
[设计意图]玩游戏是大多数学生感兴趣的事情,为此,因势利导把游戏作为切入点,借助“汉诺塔”游戏活跃课堂气氛,一方面是引起学生学习的热情,另一方面也是让学生更直观地领会编程设计方法:递归法。为下面的教学作好铺垫。
环节三:启发思考,分析问题
师:同学们基本上都通过了第二关,下面我请几位同学说一说他们通过第二关用了多少步,得了多少分。
教师请几组学生回答他们各自通过第二关所用的步数及得分。
师:同学们,你们发现了没有,同样是过了关,为什么有的同学得的分多,有的同学得的分少呢?
生:过关的步数不同则得分不同,过关步骤越多,得分越低,反之越高,二者成反比。
师:下面我们就来进一步探讨怎样用最少的步数通过第二关?
教师提示学生看大屏幕,师生共同分析。
师:3个金环时(如图2),我们可以将这个任务分解为以下三个步骤,即:
步骤一:将First上的2个金环借助于Third移到Second上。
步骤二:将First上剩下的最后一个金环移到Third上。
步骤三:将Second上的2个金环借助于First移动到Third上。
其中我们发现步骤一实际上就是第一关的重现,所不同的只是金环所在的原始柱与将来移至的目标柱不相同而已,所以完成步骤一最少须移动3次。同理,完成步骤三最少也须移动3次,由此我们可以推算出通过第二关的最少步数为:3+1+3=7。
师:这7步具体是怎样的呢?
学生两两结对,探讨通过第二关的具体移动步骤。
师:第二关我们也通过了,后面的第三关、第四关……怎么办呢?
师生共同过关,第三关、第四关……共同总结汉诺塔游戏的移动规律如下:
(1)简化问题:设金环只有一个,则问题可简化为First→Third。
(2)对于大于一个金环的情况,逻辑上可分为两部分:第n个金环和除n以外的n-1个金环。如果将除n以外的n-1个金环看成一个整体,则:
a.将First杆上n-1个金环借助于Third杆先移到Second杆。
b.将First杆上第n个金环从First移到Third杆。
c.将Second杆上n-1个金环借助First移到Third杆。
假设我们用T (n)表示n个金环从First柱移到Third柱所需的最少移动次数。
根据以上移动规律,可以得出:
师:从公式①中我们可以发现一个特点,计算T (n)的值是通过多次调用自身函数实现的,这种自己调用自己的现象我们称之为递归。其实在现实生活中,也不乏这种现象,同学们,你们想一想现实生活中有哪些现象属于递归现象呢?
学生讨论,列举现实生活中的递归现象。例如:如果将两面镜子相对放在一起,你会发现:A镜子里有B镜子的映像,B镜子里面又有A镜子的映像,这样层层重叠,无究无尽。
学生讨论时,教师应提醒学生注意现实生活中的递归与程序设计中的递归算法的不同处:现实生活中的递归是无究无尽的,而在程序设计中的递归必须在适当的时候结束这种调用。
[设计意图]:通过亲身实践,逐步引入算法思想,将抽象的算法用直观的形式表达出来,帮助学生理解递归算法的思想,并以此为基础引导学生推导出解决该问题的数学模型,从而培养和锻炼学生的逻辑思维和抽象思维能力,增强他们分析问题和解决问题的能力。
环节四:编程尝试,解决问题
师:至此,我们已将计算T (n)的算法找到了,那么如何用程序来实现递归算法呢?
对学生分组,两人一组;讨论如何用程序实现递归算法。
教师补充自定义函数;并对学生编程进行指导。
学生完成并验证程序。
教师总结,图解递归过程。
学生再次体验递归过程。
师:程序写好了,那么我们运行程序,计算一下众僧们移动64个金环要移动多少次呢?解答结果是18446744073709551615次,看来,众僧们耗尽毕生精力也不可能完成金片的移动。我们也不必担心世界末日会到来了。
[设计意图]递归程序并不复杂,可以让学生体验递归程序的编程,教师结合示意图对递归程序的执行过程进行分析,使学生对递归算法有更进一步的理解。
环节五:变式练习,拓宽思路
师:以上我们用递归法解决了汉诺塔问题,同学们想一想除了用递归法以外,解决该问题还有其他的方法吗?
学生思考老师的问题。
生:我们已经抽取了数学模型,因此可用解析法。具体方法是,已知T (1)=1,根据公式①可以计算出T(2),有了T (2)可以再进一步计算出T (3)……直至推出T(64)。
学生浏览非递归算法,教师展示程序流程图。
[设计意图]:培养算法创新意识,鼓励学生积极地进行发散性思维和逆向思维,勇于探索,不断发现,学会用不同的方法来解决问题,培养学生解决问题的灵活性和多样性,让学生体会到解决问题的方法不是唯一的,其他方法也能解决问题。
环节六:比较讨论,归纳总结
师:这节课,我们用两种方法——递归法与解析法解决了同一问题,在此基础上,同学们将这两种方法比较一下,概括递归法的特点。
学生积极讨论,总结出:程序短、结构清晰、可读性强。
教师进行补充。
[设计意图]通过两种方法的比较,使学生自己能够客观分析递归法,了解其特点。这样既全面地掌握了知识,体验了过程,又发挥了学生的自主性,锻炼了评价算法的能力。
附录1:程序界面
附录2:程序代码
附录3:以n=4为例,则函数的递归调用关系如下图所示:
递归问题 篇2
在计算机科学中, 许多数据结构都通过递归方式加以定义的, 由于其本身固有的递归性质, 因而关于它们许多问题的算法均可以采用递归技术加以实现;另外, 还有一些问题虽然本身没有明显的递归特征, 但可以利用递归技术设计出简单高效的算法程序。这些可以利用递归技术加以解决的问题称为递归问题。递归算法结构清晰、可读性强且容易用数学归纳法证明算法的正确性。但递归算法的运行效率较低, 无论是耗费的计算时间还是占用的存储空间都比相应的非递归算法要多, 并且有些程序设计语言不支持递归实现机制, 因此把递归算法转化为非递归算法有着重要意义。目前将递归算法转化为非递归算法已有一些方法, 比如使用栈加以实现等。本文通过对非回溯递归问题[8]的研究, 将现有的一些把递归问题转化成递推的方法[6]作出进一步的细化, 给出了使用递推技术将递归问题的递归算法转换成非递归算法的具体方法。此方法比文献[7,8]中的方法更加直观易用。最后通过求数组的最大升序、数组划分[7]等问题加以了说明。
1 利用递推技术求解递归问题
使用递归机制实现问题的算法程序, 其前提是必须使用分划技术, 把需求的问题分划成若干和原问题结构相同、但规模较小的子问题, 使原问题的解建立在子问题解的基础上, 而子问题的求解只需通过递归调用加以实现即可。使用递推技术求解问题同样以分划技术为基础, 它也要求将需求解的问题分划成若干与原问题结构相同、但规模较小的子问题, 然而与递归方式不同的是, 递推方法是采用自底向上的方式产生计算序列, 其首先计算规模最小的子问题的解, 然后在此基础上依次计算规模较大的子问题的解, 直到最后产生原问题的解。由于求解过程中每一步新产生的结果总是直接以前面已有的计算结果为基础, 避免了许多重复的计算, 因此递推方法产生的算法具有更高的效率。
递归方法与递推方法共同采用的分划技术, 为使用递推技术解决递归问题奠定了基础。为了使用自底向上的递推方式来解决递归问题, 必须建立原问题与子问题的递推关系, 然后定义若干变量用于记录递推关系中每个子问题的解, 程序的执行过程便是不断修改这些变量的值, 使之成为更大子问题解的过程。当得到原问题解时, 递推过程便可以结束了。其具体步骤如下:
(1) 把求解的问题分划成若干和原问题结构相同、但规模较小的子问题。
(2) 建立原问题与子问题之间的递推关系。
(3) 定义若干变量, 用于记录递推关系中每个子问题的解。
(4) 确定算法求解的初始状态 (通常即为递归实现时的终止状态) 和递推的终止状态, 再根据递推关系, 不断修改这些变量的值, 直至到达终止状态为止。
2 实 例
2.1 使用递推的方式求第n项Fibona级数的值
已知Fibona级数多项式的定义如下:
由于Fibona级数的定义是递归的, 因而采用递归的方式十分方便, 现考虑如何使用递推方式求解。根据定义, 当n的值为1或2时, 可以直接输出多项式的值, 不必求解, 以下主要考虑n>2的情况。显然n>2时, 第n阶多项式的值是建立在第n-1和n-2阶多项式的基础上。
考虑一般情况, 当i>2时, 第i阶多项式的值是建立在第i-1阶和第i-2阶多项式值的基础上, 即将求第i阶多项式的值的问题分划成求第i-1和第i-2阶多项式的值两个子问题。如果采用F (i) 表示第i阶Fibona级数多项式的值, 则在i>2的情况下有如下递推关系成立:
F (i) =F (i-1) +F (i-2)
接下来只需定义两个变量f1和f2, 分别记录上述递推关系两个子问题的解, 即f1=F (i-1) , f2=F (i-2) , 且f1, f2的值随着i的值的改变而发生变化。问题求解的初始状态为:当i=3时, f1=1, f2=1。终止状态为i=n, 此时f (n) 即为所求问题的解。具体算法程序如下 (仅考虑n>2的情形) , 算法结束时, f的值即为问题的解。
2.2 最长升序问题
给定数组a[n] (n>0) , 求出其中连续不降序列的长度最大值。
记Maxlength (n) 表示长度为n的数组连续不降序列长度的最大值, Maxright (n) 表示以n为右端点的连续不降序列长度的最大值。根据以上定义写出此问题的递归表达式:
根据定义, 当n的值为1时, Maxlength (n) 的值为1, 可以直接输出其值, 不必求解。当n>1时, Maxlength (n) 的值是建立在Maxlength (n-1) 的值或者Maxright (n) 的基础上, 而Maxright (n) 的值建立在Maxright (n-1) 的基础上。这由具体条件决定。
考虑一般情况, 当i>1时, Maxlength (i) 的值是建立在Maxlength (i-1) 或者Maxright (i) 值的基础上, 而Maxright (i) 的值是建立在Maxright (i-1) 的基础上。由此可以得出递推公式:
对于Maxlength (i) 有:
当Maxlength (i-1) >Maxright (i) 时, 有Maxlength (i) =Maxlength (i-1) ;
当Maxlength (i-1) <=Maxright (i) 时, 有Maxlength (i) =Maxright (i) 。
对于Maxright (i) 有:
当a[i]>a[i-1]有Maxright (i) =Maxright (i-1) +1;
当a[i]<=a[i-1]有Maxright (i) =1。
该递推关系中有两个子问题:Maxlength (i-1) 和Maxright (i-1) , 于是定义两个变量, 使用Maxlength记录Maxlength (i-1) 的子问题的解, 定义变量Maxright记录Maxright (i-1) 子问题的解, 即Maxlength=Maxlength (i-1) , Maxright =Maxright (i-1) , 且Maxlength, Maxright的值随着i的值的改变而发生变化。问题求解的初始状态为:当i=2时Maxlength=1, Maxright=1, 终止状态为i=n, 此时Maxlenght即为所求问题的解。具体算法程序如下 (仅考虑n>1的情形) , 算法结束时, Maxlenght的值即为问题的解。
2.3 数组划分问题
给定长度为n组a[n] (n>0) , 其中只有1, 2, 3三种整数值, 且这三种整数值都有。要求对数组中的数据由小到大排序。
该问题的递归程序如下:
该问题的求解与前两例有所不同, 它的求解过程体现为一系列数组状态的变迁。
记Parray (s, t, r) 为求解过程中的某一状态, 在此状态下a[t]为待排序数组元素, 并且此时数组中a[1], a[2], …, a[s-1]存放1, a[t+1], a[t+2], …, a[r]存放2, a[r+1], a[r+2], …, a[n]存放3。
根据上述定义, 写出其递推表达式:
式 (1) 表示为当a[t]=2∧t>=s∧t<=r时数组可以由状态Parray (s, t, r) 变迁到状态Parray (s, t-1, r) 。
式 (2) 表示为当a[t]=3∧t>=s∧t<=r 时, 再经过数组元素a[t]与a[r]的交换, 数组可以由状态Parray (s, t, r) 变迁到状态Parray (s, t-1, r-1) 。
式 (3) 表示为当a[t]=3∧t>=s时, 再经过数组元素a[s]与a[t]的交换, 数组可以由状态由Parray (s, t, r) 变迁到状态Parray (s+1, t, r) 。
由式 (1) 至式 (3) 式可知, 递推关系中包含一个子问题Parray (s, t, r) 。因为Parray (s, t, r) 所描述的数组状态是由三个值刻画的, 于是定义三个变量s, t, r来记录数组的状态Parray (s, t, r) , 且数组状态随着变量s, t, r的改变而发生变化。问题求解的初始状态为:s=1, t=n, r=n, 终止状态为s>t, 此时数组即为所求。
具体递推算法程序如下:
3 结束语
本文介绍了利用递推技术解决递归问题的方法, 以上实例利用递推技术求解递归问题较好的克服了递归算法的缺点, 可以得到高效的算法程序, 有一定的实际意义。对实例2.1的求解方法推广, 可以解决如“最大积段”“最大和段”“最小和段”等问题由递归算法到递推算法的的转化, 实例2.3可以转化“荷兰国旗”、“积木游戏”等问题由递归算法到递推算法的的转化。另外, 对于前面的问题转换只给出了一个较为粗略的算法, 对于具体问题还可以进一步细化, 限于篇幅, 不再赘述。
摘要：使用递推技术实现递归问题的算法, 不仅可以节省存储空间, 而且可以极大地提高算法的执行效率。在对递归问题进行研究的基础上, 给出了使用递推技术将递归问题的递归算法转换成非递归算法的具体方法, 并通过具体实例加以了说明。
关键词：递推技术,递归问题,分划技术,递推关系
参考文献
[1]Moody T.Chu A fast recursive algorithm for constructing matrices withprescribed eigenvaluse and singular values[J].SIAM Jouranl on Nu-merical Analysis, 2000, 37 (3) :1004-1020.
[2]Jinyun Xue.A Unified Approach for Developing Efficient AlgorithmicPrograms[J].Journal of Computer Science and Technology, 1997, 12 (4) :103-118.
[3]李云清, 杨庆红, 揭安全.数据结构[M].北京:人民邮电出版社, 2004:103-119.
[4]王晓东.计算机算法设计与分析[M].2版.北京:电子工业出版社, 2005:7-39.
[5]朱洪, 陈增武, 等.算法设计和分析[M].上海:上海科学技术文献出版社, 1989:155-159.
[6]杨庆红, 罗坚.递归问题的非递归实现方法研究与应用[J].Com-puter Era, 2005 (8) :44-45.
[7]李云清.分划递推法及其应用[J].计算机工程与应用, 2001 (17) :77-79.
递归问题 篇3
加涅认为:“人类学习具有独特性和多样性”, 可分为言语信息、心智技能、动作技能、态度和认知策略五种类型, 并由九个时段构成, 分别是引起注意→告知学习目标→刺激回忆→呈现刺激材料→根据学习者特征提供学习指导→诱导反应→提供反馈→评定学生成绩→促进知识保持与迁移。加涅还认为“教学活动是一种旨在影响学习者内部心理过程的外部刺激”, 因此, 以上九个时段或事件为教师根据教学实际开展与学习者相吻合的教学活动提供了理论依据 , 基于以上九个事件的心理活动展开的教学法称为“加涅九段式学习法” (下文简称“九段式学习法”)
2 “用递归法解决问题”课程介绍
《算法与程序设计 (选修) 》教材中的程序实现部分, 是对前面学习内容在程序设计方法上的归纳梳理, 旨在提升学生用计算机程序解决问题的能力。在这本教材中详细介绍了解析、穷举、递归三种算法思想。在递归算法思想中, 教材编写是按照“方法介绍—问题呈现—分析问题—编程实现—实践探究”的模式, 可以看出采用的是“抛锚式”教学方法, 其中例举的问题都与现实生活联系紧密。在这个知识点中, 要求学生在理解并会应用递归法解决程序问题的同时, 要能够掌握递归法的思想和思维。
笔者在教学实践中发现, 通过教材原定的“抛锚式”的教学方法, 使学生的学习效果仅仅限定在了基本的教目标上, 并没有注重或深入到对学生算法思维的培养, 甚至在教材中贴近社会、贴近生活的教学实例也没有表现出预期的热情和兴趣。根据上述教学实践效果, 笔者进行了反思, 认为语言规则模块因其在课程体系中承上启下的重要作用在教材中占居了大量的篇幅, 该部分选取的问题就多数源于现实生活, 再在程序实现模块呈现此类问题, 很难再次引起学生的学习兴趣。因此, 笔者认为, 想要有效保持学生的学习热情, 需要对该模块的问题进行变换, 故笔者根据学生的学习心理应用加涅的九段式学习法, 并取得了一定的效果。
3 九段式学习法的具体应用
3.1 第一段:唤起注意——通过故事引出递归思想
唤起注意能在第一时间把学生
的思维带入课堂。在教学开始时, 笔者用多媒体播放“老和尚与小和尚”这个古老传说的音频:“从前有座山, 山上有座庙, 庙里有个老和尚, 老和尚在给小和尚讲故事, 讲的什么呢?从前有座山, 山上有座庙, 庙里有个老和尚, 老和尚在给小和尚讲故事……”这个故事简单, 学生都耳熟能详, 并且都对故事有自己的见解。这样先用故事吸引学生的注意力, 让学生从故事引起有意的注意, 教师趁机向学生讲述递归思想的概念, 使学生快速进入利于接受新事物的兴奋状态。
3.2 第二段:告知学习目标——提出概念、明确学习任务
结合上述故事, 让学生理解递归算法的概念“一般讲, 如果一个函数在定义时, 直接或间接地调用了自己, 这种算法在程序设计中统称为递归法。例如, 函数A自己调用了自己。另外, 如果函数A调用了函数B, 函数B反过来再调用函数A的算法, 也是递归算法。”待学生理解后, 抛出本节课学生的学习任务以及能够解决生活中的那类问题, 如镜子反射问题等, 让学生在明确学习任务的基础上, 懂得这堂课的实用性, 以便维持学生的学习兴趣。
3.3 第三段:刺激回忆——回忆已有的知识技能
笔者先借助课件向学生讲述这一故事材料:传说印度教的主神梵天创造世界时, 在印度北部佛教圣地贝拿勒斯圣庙里安放了一块黄铜板, 板上插着三根宝石针, 在第一根宝石针上自下而上地放着由大到小的64个金盘。这就是所谓的汉诺塔 (Hanoi) 。梵天要求僧侣们坚持按下面的规则把64个盘子移到第三根宝石针上:1一次只能移一个盘子;2盘子只许在三根针上存放;3永远不许大盘压小盘。梵天宣称, 当把他创造世界之时所安放的64个金盘全部从第一根针移到第三根针上时, 世界将在一声霹雳中毁灭。
笔者先让学生利用以前学习的知识, 开展思考, 寻找实现上述问题的方法和结果。
3.4 第四段:呈现刺激材料——通过内容展示新知识
笔者在这堂课中采用的是延续上面的教学材料, 通过计算机模拟汉诺塔问题开展小游戏。让学生通过游戏体验, 找寻问题的规律, 从而获得对知识的认知。
让学生思考并尝试如何按照要求完成主神梵天的任务。根据实验记录出以下规律:
(提示:函数s (n) 表示盘子数为n时, 所有盘子全部都移动到第三根宝石针上的最少移动次数。)
在这个游戏过程中寻找问题答案, 不仅能够让学生体会算法思想, 摆脱了数学方法的束缚, 还能使学生的学习兴趣始终维持在一个较高的水平, 传说与游戏的结合使难懂的递归思想在让学生感到新奇之余, 变得形象有趣, 教学难点也迎刃而解了, 使学生“在故事中认识递归, 在游戏中理解递归”。
3.5 第五段:提供学习指导——通过分析引领学生思维
剖析递归算法的实质是将规模大的、难解决的问题变成规模小的、易解决的同一问题, 规模较小的问题又变成规模更小的问题, 并且小到一定程度, 直到可以直接得出它的解, 从而得到原来大规模问题的解。引领学生知晓递归算法的思想核心在于“问题的规模”、“边界条件及边界值”、“解决问题的通式”。在这个过程中, 笔者通过要求学生将通过哪些步骤或等式实现这些问题, 将这些步骤或等式确定下来。
在这个过程中, 使学生能较快地建构递归算法的意义并形成一定的概念, 促进学生对于知识的保持。
3.6 第六段:诱导反应——通过回顾提取知识技能
在这个阶段, 教师要引导学生从前面的学习和思考中总结出应用的一些基本技能, 同时掌握学习的结果, 并加以应用。在这堂课中, 学生应该掌握的技能就是自定义函数的编写格式和自定义函数的调用格式。
其中:自定义函数的编写格式为:
[Public|Private] Function =< 函数名称 > ([< 参数列表 >]) [As < 类型 >]
< 局部常量、变量定义 >
< 语句组 >
[ 函数名 = 返回值 ]
End Function
自定义函数的调用格式为:
格式1:变量 = 函数名称 (参数)
格式2:Call函数名称 (参数)
格式3:函数名称 (参数)
然后诱导学生利用这些技能去解决新问题。
3.7 第七段:引出行为——首次作业, 证实预期目标
教师给学生布置首次作业, 以证实预期目标的达成情况。在本节课中要学生完成以下作业:通过自定义函数实现递归法算法, 写出其正确程序, 其一般格式为:
If边界条件成立Then
赋予边界值
Else
解决问题的通式
End If
3.8 第八段:提供反馈——及时反馈, 促进问题解决
在Visual Basic 6.0语言环境中验证程序, 根据反馈信息调整代码, 最终得到问题的正确答案, 完成用递归法解决问题的学习任务。分享学习成果, 通过组间交流的形式, 加深对递归算法思想的理解, 对学习内容进行整理归纳, 形成学习小结。
3.9 第九段:促进保持与迁移——变换情境, 强化学习结果
在这个阶段, 笔者提出了提供变化了的练习及复习, 在这个阶段的教学中, 笔者提出了三个材料以强化学生学习:1比萨斜塔上的小球:比萨斜塔位于意大利中部比萨古城的教堂广场上, 它是一座钟楼, 始建于公元1174年, 塔高54.4米, 8层圆柱形建筑, 全部用白色大理石砌成。现从塔顶向下抛一小球, 小球每次着地后反弹的高度是上次高度的四分之一, 那么, 小球静止前经过的垂直距离是多少?用递归法计算;2斐波那契的兔子繁殖:有人养了一对兔子, 这对兔子以后每月生一对兔子, 新生兔子从第三个月开始, 也是每月生一对兔子, 问12个月后这人有多少对新生兔子;3小猴子吃桃子:小猴子第一天摘了一堆桃子, 当即吃掉一半, 忍不住又多吃了一个。第二天早上它又将剩下的桃子吃了一半, 然后又多吃一个, 以后每天早上它都会将前一天剩下的桃子吃掉一半多一个。到第10天早上小猴子想再吃时发现, 就只剩下一个桃子可以吃了。问第一天小猴子共摘了多少个桃子?
4 九段式教学法与“抛锚式”的教学法结果对比
笔者在采用九段式教学法的同时, 对另一班级采用“抛锚式”教学, 并对教学结果进行了对比, 对比结果如下:
5 结语
递归问题 篇4
对于用顺序法表示的二叉树,各结点在数组中的编号很有规律,其周游较容易进行,但对于用链式存储结构表示的二叉树,进行周游就复杂一些,仅讨论二叉链表存储的二叉树的周游算法。首先讨论深度优先周游二叉树的递归算法,然后研究深度优先周游二叉树的非递归算法。
1 深度优先周游二叉树的递归算法
前序法(DLR)的递归定义是:若二叉树为空,则空操作;否则:访问根结点;前序周游左子树;前序周游右子树。
中序法(LDR)的递归定义是:若二叉树为空,则空操作;否则:中序周游左子树;访问根结点;中序周游右子树。
后序法(LRD)的递归定义是:若二叉树为空,则空操作;否则:后序周游左子树;后序周游右子树;访问根结点。
深度优先周游二叉树的次序是递归定义的,因此其递归算法是很容易实现的。若二叉树的二叉链表存储结构定义为:
则3种深度优先周游二叉树的递归算法分别为:
从上述深度优先周游二叉树的定义可知,3种周游算法的不同处仅在于访问根结点和周游左、右子树的先后关系。深度优先周游二叉树的递归算法的实现,在系统运行时是借助栈来完成的。以图1所示的二叉树为例,分析栈的变化过程。前序周游二叉树与中序周游二叉树时,栈的变化相同,而后序周游二叉树则稍微复杂一些。如表1、表2和表3所示。
2 二叉树的非递归周游算法
根据上述二叉树周游时的栈的变化情况,可以看出:二叉树的前序周游和中序周游时栈的变化情况完全相同,不同的是前序周游时,进栈时访问元素;而中序周游时,出栈时访问元素。由此设计二叉树的DLR和LDR的非递归周游算法如下:
使用栈进行前序周游时,遇到一个结点,就访问该结点,并把该结点推入栈中,然后下降去周游它的左子树。周游完它的左子树后,从栈顶托出这个结点,然后按照它的右孩子指针指示的地址再去周游该结点的右子树。
使用栈进行中序周游时,遇到一个结点,就把它推入栈中,并去周游它的左子树。周游完它的左子树后,从栈顶托出这个结点并访问之,然后按照它的右孩子指针指示的地址再去周游该结点的右子树。
使用栈进行后序周游二叉树时,遇到一个结点,把它推入栈中,去周游它的左子树。周游遍它的左子树后,还不能马上访问处于栈顶的结点,而是要再按照它的右孩子指针指示的地址去周游该结点的右子树。周游遍右子树后才能从栈顶托出该结点并访问之。为此,需要设一个标志,以标识右子树已被周游。算法中设置了一个指针标志pre,表示刚刚访问的结点。如果当前结点的右孩子为pre,就说明右子树已被访问,接下来是访问当前结点了。
3 深度优先周游二叉树的算法性能分析
上述深度优先周游二叉树的递归算法与非递归算法的时间复杂度均为O(n),空间复杂度在理想情况下为O(log 2n),如二叉树退化为单支树时,则空间复杂度为O(n)。
由于递归算法结构清晰,程序易读,而且它的正确性容易得到证明,因此,利用允许递归调用的语言进行程序设计时,给用户编制程序和调试程序带来很大的方便。因为对这样的一类递归问题编程时,不需要程序员而由系统来管理递归工作栈。而非递归算法更方便读者理解工作栈的变化情况,但需要程序员决定栈所占据的存储空间大小,为保证二叉树周游不至于因为栈溢出而进行不下去,就需要给栈分配足够的存储空间。
摘要：给出了深度优先周游二叉树的前序、中序、后序的3种递归算法,在分析了周游二叉树的递归算法中的工作栈的执行过程的基础上,设计了先序、中序、后序周游二叉树的非递归算法,对深度优先周游二叉树算法的性能进行了分析。
关键词：二叉树,周游,递归,非递归,栈
参考文献
[1]严蔚敏,吴伟民.数据结构(C语言版).清华大学出版社,2010.
汉诺塔非递归算法 篇5
关键词：汉诺塔,非递归算法,二叉树
1 引言
汉诺塔问题说的是，有三根柱子，不妨称为A、B、C三柱，A柱上有大小不同的n个盘子，最上面的盘子最小，最下面的盘子最大，不妨用1,2,3，……，n从上到下对n个盘子编号，每次从一个柱中移动一个盘到另一柱上，同时，做到大不压小，最后把n个盘移到C柱，要求写出移动过程。汉诺塔问题常用的解法是用递归算法，这是数据结构课中递归算法的经典例子。但不难发现，这种递归算法占用相当大栈空间，而且运行速度较慢，当盘数n较大时，常常会因栈溢出而无法运行。近几年，不少学者对汉诺塔问题的非递归算法作了大量的研究，有的利用两次移动n-1个盘的相似特点[1]，用递推的方法解决递归，但它仍需要大量的存储空间;有的非递归算法，存储空间虽然很小，但时间复杂度却增加了不少。有没有一种兼顾时间和空间的非递归算法呢?文中对此作了研究，并给出了一种算法。
2 汉诺塔递归算法
n个盘的汉诺塔问题可用如下递归方法实现。
当盘数为1时，将第n盘从A移到C即可。记作：nA-->C
当盘数不为1时，将n-1盘从A(利用C柱过渡)移到B，然后，将第n盘从A移动到C，最后，将n-1个盘从B(利用A柱过渡)移动到C。程序如下：
3 兼顾时间与空间的非递归算法
3.1 操作过程与二叉树的对应关系
从汉诺塔的递归算法中可知，当盘子的个数大于2时，汉诺塔的移动过程分为3步，第一步将n-1个盘从A移到B;第二步将第n盘从A移到C;第三步将n-1个盘从B移到C。如果把移动过程看作是二叉树的中序遍历[2]，则可用图1的二叉树与汉诺塔移动过程建立对应关系[3]。
按照同样的方法，处理图1中的左右子树，便得到图2形式的二叉树。
直到盘的个数为1时，不再有左右子树。
从建树的过程可知，同一层的结点，要么都没有子树(最后一层)，要么每个结点均有两个子树。因些，整个一棵树构成了n层的满二叉树。该树的中序遍历结果就是汉诺塔的移动过程的解。
为了更好地分析这个特殊的满二叉树，不妨对汉诺塔的操作进行编号，如表1。
如此，与汉诺塔相对应的二叉如图3。
这种二叉树，不妨称为汉诺塔二叉树，它的特点如下：
特点一：除最后一行结点没有孩子外，每个结点的左右孩子如图4所示。
对这个特点，用归纳法作出如下证明。
证明：(1)当盘数n等于1时，此时结点没有左右孩子。对应的二叉树只有一个结点，处于最后一行。因此，结论成立。
(2)当盘数n=2时，由于该二叉树是满二叉树，所以，由建树过程知，从A柱移到B柱，对应的二叉树只能是图a，从B柱移到C柱时，对应的二叉树为图b，同理，其它情况所对应的二叉树分别为：图c、图d、图e及图f。因此，当n=2时结点符合图4特点。
(3)设盘数n=k时，结点符合图4特点。
(4)当盘数n=k+1时，先考虑k+1个盘从A柱移到C时，根据建树的方法知，根结点编号3，其左子树为k个盘从A移到C，因此，左子树的根结点编号为0，同理，右子树的根结点编号为1，其汉诺塔二叉树如图5所示，根结点符合图4特点。
而图5中的左右子树是盘数为k的汉诺塔二叉树，由(3)的假设知，它们都符合图4特点。所以，图5所有结点符合图4特点。
类似地，k+1个盘从A移到B、从B到A、从B到C，从C到A，以及从C到B盘，同理可知结点符合图4特点。所以，盘数n=k+1时，结点符合图4特点。
由上可知，对任意个盘，除最后一行结点没有孩子外，每个结点的左右孩子如图4所示。
特点二：n个盘从A移到C的汉诺塔二叉树，从水平方向看，奇数层结点是3、4、5、3、4、5……循环;偶数层结点是0、1、2、0、1、2……循环。
证明：(1)根据特点一，如果上一层结点编号3、4、5、3，则下一层结点必然是0、1、2、0、1、2、0、1，所以，如果上一层结点编号3、4、5、3……循环，下一层必是0、1、2、0……循环。
(2)同理，如果上一层是0、1、2、0……循环，则下层是3、4、5、3……循环。
(3)n个盘从A移到C的汉诺塔二叉树，第一层结点编号为3，符合3、4、5、3……循环，所以由(1)知，第2层符合0、1、2、0……循环，再由(2)知，第3层符合3、4、5、3……循环，所以，对于有限盘数n，所有结点符合特点二。
3.2 非递归算法实现
因为汉诺塔树二叉树具有上述特点，所以，可以无须存储整个树而达到中序遍历的结果。下面给出它的中序遍历算法。将二叉树严格按照左子树在左，右子树在右画，中序遍历的结果应该是结点从左到右的一个排列。由于它是满二叉树，整个输出过程是，先输出最下层的一个结点，然后，输出上层中第一个左子树能包含该结点的结点，然后，再输出下层的下一个结点，再输出上层中第一个左子树能包含该结点的结点......如此，直到下层的结点全部输出完为止。
用一维数组level_position[]存储某一层已输出的结点序号。由于该二叉树是满二叉树，上层第i个结点的左孩子一定是下层的第2i-1个结点，右孩子一定是下层的第2i个结点。
这样，判断下层结点是否是上层结点的右孩子，只要判断上下层结点在其本层的编号是否构成2倍关系即可，整个算法程序实现如下：
4 结语
汉诺塔问题是经典的递归算法例子，语句虽少，但需要大量的栈空间，运行效率不高。文中介绍用非递归方法解决汉诺塔问题的算法，仅用少量的存储空间克服了递归算法的不足。兼顾了时间与空间的复杂度，提供了解决汉诺塔问题的新方法。
参考文献
[1]邱宁.汉诺塔问题的非递归算法分析[J].浙江树人大学学报,2005.
[2]王晓东.数据结构与算法[M].北京:高等教育出版社,2003.
状态积累递归软序列估计 篇6
1965年Ward等人提出序列估计机制的捕获算法后[1],这一类算法有了很大的发展。在文献[2]提出的捕获算法中,将序列提前积累多次后作为初始捕获状态,这样大幅降低了信道噪声的干扰,然后以此为基础再进行捕获。Salih等提出的算法在接收端利用PN序列的相关性构造了一种辅助序列[3],在得到辅助序列后,根据辅助序列不断判断当前捕获序列结果与正确序列的距离和迭代方向,最终实现正确捕获。这两种方法都需要超过一个周期的捕获时间。Chiu等改进了序列的积累方式[4],信息的积累效率提高,因此算法性能获得了提高。文献[5]通过重新设计收发端的序列给出了一种分布式接收机,并采用不断积累修正获得较好的算法性能。文献[6]对现有的同步捕获方法进行了总结,并支持估计机制的优势所在。Yang等提出的递归软序列估计(Recursive Soft Sequence Estimation,RSSE)是SE机制的典型代表[7]。
RSSE是目前针对低信噪比、长序列周期条件下伪随机捕获算法中比较有效的一种。但当SNR值下降时,对数似然比(LLR)值会受到噪声的影响,使得RSSE机制与原有的序列捕获机制的硬判决相比没有什么优势。尤其是对于长周期序列,或是序列的生成多项式中非零项较多时,算法的捕获性能急剧下降。
为了提高RSSE类的序列捕获算法在低信噪比下(尤其对于捕获长PN序列)的性能,文中提出一种基于状态积累递归软序列估计(SARSSE)的序列捕获算法。通过在RSSE前端加入状态积累移位寄存器的设计,可以提高算法捕获效率。对于多个PN周期而言,由于每个PN序列周期内伴随发送信号的噪声都是相互独立的。所以将每个PN序列发送的前n个接收比特叠加在一起可以改善初始状态的估计,从而改善文献[7]信道输出信噪比(SNR)和LLR的值,最终能够在低SNR下得到较好的PN序列捕获性能。改善了RSSE机制的捕获性能。
1 SARSSE捕获机制
如图1所示,SARSSE捕获机制包括5个功能块:SISO译码器、状态累积寄存器、软码片寄存器、PN序列生成器以及积分判决电路。SISO译码器在接收到与PN序列的给定码片相关联的软信道输出采样之后估计相应的LLR软输出。除了这个码片的内信息(即直接从信道接收到的信息)之外,还可以利用外信息,外信息是由软码片寄存器中的延迟单元(称为软码片延迟单元,SCDU)中 所存储的由以前接收到的码片值所计算得到的LLR值构成。因此若可用过去时刻的软信息对当前时刻的软信息加强,必须将SCDU构造成线性反馈移位寄存器(LFSR)的结构形式,该过程需利用序列生成多项式g(x),这样才能使得当前时刻软信息的计算可以利用过去时刻的软信息积累。SCDU的数目与PN序列生成器中的延迟单元的数目相同,将SISO译码器的软输出送到软码片寄存器的最左边的SCDU,并丢弃最右边的SCDU中的软LLR值。SCDU用来存储连续的码片瞬时LLR值,并且采用该LLR的计算连续的码片值。与此同时,与PN序列的给定码片相关联的软信道输出采样还将送入状态累积寄存器中。当接收信噪比较高时,SARSSE机制可以在一个周期之内捕获到PN码,那么状态累积寄存器将不起作用。但是当SNR低时,SARSSE机制无法在一个PN码周期之内完成捕获,此时将上一周期在状态累积寄存器中存储的码片值与当前输入的软信道输出采样值相加,然后再将相加的值送入SISO译码器进行处理。
图1中SISO译码器需要软信道输出信息以及SISO译码器以前估计的LLR值所提供的外信息来计算软输出,从而更新软码片寄存器中的值。在单用户情况下,标准的捕获模型是
Zk = αk(-1)ck+nk (1)
式中:Zk是捕获模块接收到的对应于ck的噪声抽样信号,并且αk是信道衰落幅度。nk是单边功率谱密度为N0的零均值加性高斯白噪声(AWGN)。用Ec代表发送的码片能量,且undefined代表每码片的SNR。
ck是扩频序列,并且假设ck是由一个r-级LFSR产生的,这个寄存器的生成多项式可以表示为
g(D)=1+Ds1+Ds2+…+Dsl+…+DsM=r (2)
式中,D代表单位延时算子。每个生成器系数g1, g2, …,gr(共r个系数)表示是否存在反馈连接线(1表示存在,0表示不存在),其中有M个系数{s1,s2,…,sM=r,1≤si≤r}为1,而其他的系数均为0。由于扩频通信系统通常用+1来表示0,并且利用码片值取为{+1,-1}的二进制扩频序列进行通信,所以PN序列生成器输出的是符号{+1,-1}。因此,现在用域{+1,-1}上定义的模2乘运算替换域{1,0}上的常规模2加运算,如图1中所示。并且,PN序列生成器的输出符号服从以下的递归公式
undefined
软信道输出信息是信道输出为Zk条件下的ck的LLR值,即
undefined, i=0,1,2,… (4)
式中,undefined代表信道的可靠值。在式(4)中,L(ci)是随机变量ci的LLR值,其计算式为
undefined
如果没有有关ci的先验信息,那么有L(ci)=0。
由图1中可知,在计算当前时刻软信息的时候利用了过去时刻的软信息积累。根据生成多项式(2)的递归关系以及图1中软码片寄存器中SCDU的反馈连接,用于增强ci的正确译码概率的外信息可以近似表示为
undefined·undefined·
undefined (6)
假设Le(c-∞)=…=Le(c-2)=Le(c-1)=0,其中L(yi-1),L(yi-2),…,L(yi-r)是SISO译码器以前的r个软输出。
最后,利用式(4)中的信道输出信息和式(6)中的外信息,可以得到与ci相关联的SISO译码器软输出为
undefined
undefined·
undefined (7)
利用式(7)可以估计出完整PN序列的前r个连续码片值。
可见,ci的软信息积累依赖于信道的可靠值,当SNR低时,软信息并不会随着递归深度的增加而增加。因此,SARSSE机制在SISO译码器之前增加了状态累积移位寄存器,状态累积移位寄存器的初始值为0。当没有在一个PN码周期之内捕获到PN序列时,状态累积移位寄存器中的值会与下一个PN码周期的信道输入值相加。由于两次PN码周期期间的噪声是相互独立的,所以有
undefined
显然,信道的可靠性增加了,也即改善了SISO译码器输入内信息的可靠性,从而改善了整个机制的捕获性能。
用仿真来验证提出的SARSSE捕获机制。仿真结果主要基于生成多项式为g(D)=1+D+D3+D4+D13和g(D)=1+D2+D5的PN序列。首先比较了与正确判决PN序列的某个指定码片值的极性相关的可靠性。横坐标是接收到的归一化码片数(l/r);纵坐标是判决可靠性,定义为SISO译码器输出(公式(7)的计算结果)的绝对值。图2显示了由生成多项式g(D)=1+D+D3+D4+D13产生的PN序列的捕获性能,用两种机制进行捕获(RSSE和SARSSE)。
2 SARSSE算法仿真
通过在AWGN(加性高斯白噪声)环境下的仿真,来验证上文提出的SARSSE捕获机制。仿真结果主要基于生成多项式为f(D)=1+D+D3+D4+D13的PN序列。首先比较了两种捕获机制在改进前后的可靠性,该可靠性是指正确判决PN序列的某个指定码片值,具体定义为SISO译码器的输出绝对值,判断可靠性是通过式(7)计算的。图2是信噪比为-2 dB时,在第二个周期其判断可靠性的积累情况。随着序列积累过程的进行,软信息不断地增加,从而两种算法的判断可靠性在理论上应该持续积累,但从仿真结果可以看出,信道环境的信噪比为-2 dB时,RSSE机制的判断可靠性已经不会像SARSSE机制那样随着接收序列数的增加而变大,因此SARSSE机制在低信噪比时可靠性优于RSSE序列捕获算法。
图3中通过计算利用不同的序列状态数对序列进行捕获后,对序列进行纠错的效果来考量算法的捕获能力,从而对比了两种算法(RSSE和SARSSE)的捕获性能。仿真序列的生成多项式为f(D)=1+D+D3+D4+D13。图中的结果再次验证了SARSSE捕获机制在低信噪比环境下的捕获可靠性能好于RSSE捕获算法。从图3中的曲线对比可以看出,当SNR较高时,使用相同的递归积累数(例如积累数L都为1 Sa或者10 Sa,1 Sa表示一个序列状态),SARSSE机制相对于RSSE机制的每码片的SNR增益大约为1 dB;并且当SNR继续降低时,增加递归积累数并不能再继续改善RSSE机制的系统性能,因此此时的SARSSE机制的SNR增益更加明显,L=40 Sa时的SNR增益达到了2 dB。
3 结束语
笔者提出了改善的RSSE捕获方法——SARSSE算法,并且研究了SARSSE机制对PN序列的捕获性能。仿真结果显示SARSSE捕获算法在低SNR环境下对PN序列的捕获可靠性好于RSSE算法,可以在硬件复杂度增加不大的情况下,在低SNR环境下进一步改善系统的捕获性能。
摘要：目前对于数字电视应用的长周期伪随机序列,捕获性能有限。提出状态积累递归软序列估计算法,在递归软信息积累过程前端建立状态积累移位寄存器,通过积累多个周期的信息来提供较为可靠的初始积累值,最终加速后续软信息积累,从而取得较好的捕获性能。
关键词：伪随机序列,捕获,状态积累,递归软序列估计
参考文献
[1]WARD R B.Acquisition of pseudonoise signals by sequential estimation[J].IEEE Trans.Communications,1965,13(4):475-483.
[2]JUNG C Y,YOON S.A novel DS/SS code acquision technique based onseed accumulation of sequence generator[C]//Proc.2001 IEEE MilitaryCommunications Conference.[S.l.]:IEEE Press,2001:1380-1383.
[3]SALIH M,TANTARATANA S.A closed-loop coherent acquisitionscheme for PN sequences using an auxiliary sequence[J].IEEE Journalon Selected Areas in Communications,1996,14(8):1653-1659.
[4]CHIU J,LEE L.An improved sequential estimation scheme for PN acqui-sition[J].IEEE Trans.Communications,1988,36(10):1182-1184.
[5]刘震昆,黄顺吉.低信噪比下超长PN码的快速捕获技术[J].信号处理,2006,22(3):299-302.
[6]康荣宗,汪涛,刘洛琨,等.超宽带通信系统的同步捕获算法研究[J].电视技术,2008,32(S1):78-81.
递归数据结构的数学定义 篇7
在许多数据结构教材中,对于一些简单的数据结构的逻辑表示,通常,除了采用自然语言的描述外,还可以给出确切的用数学语言描述的形式定义。
线性表结构是由一组性质相同的数据元素的集合D和D上二元关系的集合R所组成,其形式定义为:
其中
上述形式定义用数学语言很好地描述了线性表结构是由一组数据元素D组成,且元素之间的线性关系用R精确地描述了出来。任何一个具体的线性表都可以用上述数学语言加以描述,并且,采用数学语言描述,更为精确全面,不会产生二义性。
然而,一些递归的数据结构诸如树型结构、广义表结构等似乎很难给出一个完全用数学语言描述的定义来,大多采用的是文字描述的形式,或者部分采用数学语言,部分采用文字描述。下面从参考文献中列举几个典型的对树的定义来说明这种情况。
例如,参考文献[1]对树形结构的定义是:
树是由个结点组成的有限集合。如果n=0,称为空树;如果,则
(1)有一个特定的称之为根(root)的结点,它只有直接后继,没有直接前驱。
(2)除根以外的其他结点划分为个互不相交的有限集合,每个集合又是一棵树,并且称之为根的子树(subTree)。每个子树的根结点有且仅有一个直接前驱,但可以有0个或多个直接后继。
这是一个完全用文字进行描述的定义。
参考文献[2]除了有类似参考文献[1]的说明外,对树形结构还给出了如下的定义:
在一棵树中,每个结点被定义为它的每个子树的根结点的前驱,而它的每个子树的根结点就成为它的后继。由此可用二元组给出树的定义:
其中,n为树中的结点数,n=0则为空树,则为非空树。对于一棵非空树,关系R应满足下列条件。
(1)有且仅有一个结点没有前驱,该结点被称为树的根。
(2)除根结点外,其余每个结点有且仅有一个前驱结点。
(3)包括树根结点在内的每个结点,可以有任意多个(含0个)后继。
这是一个对树的结点的集合采用了数学语言,而关系采用了文字描述的定义。
同样,参考文献[3]除了也有类似参考文献[1]的说明外,在树的抽象数据类型定义中对树形结构还给出了如下的描述:
数据对象D:D是具有相同特性的数据元素的集合。
数据关系R:若D为空集,则称为空树。
若D仅含有一个元素,则R为空集,否则R={H},H是如下二元关系:
(1)在D中存在惟一的称为根的数据元素root,它在关系H下无前驱;
(2)若D-{root}≠Φ,则存在D-{root}的一个划分D1,D2,…,Dm(m>0),对任意j≠k(1≤j,k≤m)有Dj∩Dk=Φ,且对任意的i(1≤i≤m),唯一存在数据元素xi∈Di,有
(3)对应于D-{root}的划分,H-{
这个描述尝试对树的关系的定义给出一种数学语言的描述。
树是一个有限的、非空的结点集。
它具有下列性质:
(1)集合指定的结点r叫做树的根结点。
(2)其余的结点可以划分成n个子集,,其中每一个子集都是一棵树。
为方便起见,用符号来表示树T。
该定义对结点的集合给出了一种非常简洁的定义,虽然已经表明了树定义的递归特性,但没有直接给出树中结点之间的关系。
2 对现有数据结构形式定义的分析
为什么会出现前面所述现象呢?其基本原因是什么呢?下面从现有的数据结构形式定义的分析来找出造成这种现象的原因所在。
数据结构的形式定义是对一组关联的数据元素以及这些数据元素之间关系的一种逻辑表示形式。通常采用的是二元组的描述形式,即数据结构是由两部分构成的,其一是一组数据元素的集合(或称为聚集可能更为合适);其二是数据元素之间的关系的集合。数据结构的逻辑表示通常采用如下的形式定义:
其中,D是一组性质相同的数据元素的有限集合,R是D上关系的有限集合。D和R可表示为:
这个形式定义应该普遍适用于各种数据结构的定义,包括线性表、树、图以及广义表等数据结构。在表示线性这样简单结构甚至图这样的复杂结构,无论是形式定义还是一个具体线性表或者图,都能够很好地表示出来。对于树这样的具有递归特性的数据结构,如果是一个具体的树,可以用这样的定义表示出来,然而要给出一个普遍适用的形式定义,却出现了困难,似乎很难用数学语言的形式定义全面地描述出来。
通常认为,在数据结构中D是一组性质相同的数据元素的有限集合。那么,在树这样的数据结构中,D则是由代表数据元素的结点的集合所构成。在这种情况下,对于一棵具体的树,可以用有序偶的集合来表示结点之间的关系R。但是,在进行树的形式定义时,就出现了问题,很难给出一种用数学语言描述的完整形式。问题的根源是认为D是一组性质相同的数据元素的有限集合,而树的基本关系是树的根结点与子树间的关系,这样,用树的结点之间的有序偶就无法表示这种关系了。
3 新的数据结构的定义
【定义】数据结构是一组数据元素及数据元素之间相互关系的静态结构,是数据的逻辑结构和存储结构的统称。
其逻辑结构的形式定义为:
其中,D是数据元素的聚集,R是D上关系的集合。D和R可表示为:
存储结构则是逻辑结构在计算机存储器中的映像。
这个定义与原有定义的区别有两点。第一,它明确地说明了数据结构是一组数据元素及数据元素之间相互关系的静态结构,是其逻辑结构和存储结构的统称。其中,描述为一组数据元素,而不是一组性质相同的数据元素,是对这一部分泛化的描述。例如,广义表是一种数据结构,但是,广义表中的数据元素有原子元素和子表元素两种性质不同的元素。作为形式定义的数据结构应该包括这种情况。第二,它指出形式定义中D是数据元素的聚集(Collection)。聚集的限制要更加宽松一些,允许聚集中元素的性质可以不同,也允许聚集中存在元素值相同(但被看作是不同)的元素。要比说明为集合(Set)更为准确和贴切一些。显然,集合是聚集的特例。同时,D的表示采用的是圆括号,以示区别。是关系集合R中的一个关系,在原来的定义中通常是采用元素之间关系的序偶(有序的或无序的)集来表示。例如一个有a,b,c,d 4个元素的线性表,通常表示为,在新的定义中,为了使表示更为简洁,采用元素之间关系的序列(有序的或无序的)来表示,例如表示a,b,c,d 4个元素的有序序列时用尖括号加元素的序列表示,如,而表示无序序列时用圆括号加元素的序列表示:。当需要表示两个元素之间的关系时,自然就成为有序偶或无序偶。
在这个基础上,递归的数据结构的定义就可以迎刃而解了。
4 递归的数据结构的定义
对于具有递归特性的数据结构的定义,文献[4]的定义给出了一个非常好的启示。下面将对树和广义表这两种具有递归特性的数据结构加以分析,并给出相应的用数学语言描述的形式定义。
4.1 树结构的形式定义
4.1.1 一般树
对于一棵最多具有k个分支的k叉树而言,每个结点的性质是相同的,D应该表示为这些结点的集合。在D中,除了根结点外,其余结点可以按子树的结点划分为k个互不相交的子集,我们可以把这些子集看成是一种特殊的元素,这样,D就可以被认为是由一个根结点元素和k个互不相交的子集元素构成的聚集。即
在这里,D不再是性质相同的元素的集合,而是不同性质的数据元素的聚集,m是聚集中元素的个数,是树的根结点元素的个数,只有0或1两种值,k是结点的子树的个数。这样,当则为空树,m=0,m>0则为非空树,,若k=0时,树中则只有一个根结点。
另外,子树相对于根结点,子树的地位是相同的,它们之间是并列的,且没有顺序之分,为了简化表达式,约定子树集用如下符号表示:
其中,冒号表示子树之间是并列的,且互不相交,圆括号表示相互间无序。
在这个基础上,就可以很容易地给出树的递归的形式定义:
其中,
在这里,是树T的根结点,是树T的一棵子树,子树也是一棵树。是有序偶,表示树T的根结点与子树集的二元关系,也同时表示了树T的根结点与每棵子树之间的二元关系。
这个定义清晰、简洁,并且很好地反映了树的递归特性。
4.1.2 二叉树
对于一棵二叉树,除了一般树的特性外,左右子树又是有序的,定义中还要反映左右之别,其递归的形式定义为:
其中,
在这里,是二叉树BT的根结点,是的BT左子树,是BT的右子树,子树也是一棵二叉树,表示左右子树是并列的且左右有序。有序偶是二叉树BT的根结点与子树之间的二元关系。特别需要说明的是,由于二叉树左右子树是有序的,因此,在只有左子树或只有右子树的情况下,子树中间的冒号不能省略。
4.1.3 二叉树表示示例
给定一棵二叉树如图1所示。
按照上述二叉树的形式定义,这棵二叉树的可表示为:
其中,
在具体描述一棵树时,D只需将其中的元素依次展开用结点元素表示即可。上述描述中,D中的元素展开的结果显然是按先序遍历结点的顺序表示的结点元素的序列,由于D是元素的聚集,与展开的顺序无关,因此,按层序遍历的顺序展开也是可以的。R则需要表现二叉树的层次和左右之别,有序偶是按递归的顺序以嵌套方式展开的,且左右有别,完整地反映了二叉树结点之间的层次和左右关系。
4.2 广义表结构的形式定义
广义表也是一种递归的数据结构,是由原子元素(Atom Elements)和子表元素(Sub General Lists)组成的。子表元素也是一个广义表。
4.2.1 广义表的形式定义
虽然广义表是一种递归的数据结构,但是其递归只是体现在子表中,而表中的元素与树中元素的层次关系不同,是一种线性关系,因此,其形式定义也有差异。参考树形结构的形式定义,广义表的形式定义如下所示:
其中,D是一组原子元素和子表元素构成的有限聚集,是D上关系的有限集合。D和R可表示为:
在这里,是广义表元素的有序序列,这种表示方法要比采用有序偶的序列要更为简洁清晰。
4.2.2 广义表表示示例
给定一个广义表如图2所示。
按照上述广义表的形式定义,这个广义表的可表示为:
其中,
在具体描述一个广义表时,D只需将其中的元素依次展开用原子元素表示即可。R则需要表现广义表的层次和同层元素的顺序之别。同一层次用尖括号表示其顺序性,其中的原子元素用元素值表示,子表则用圆括号表示,子表同样用上述方式递推的表示,从而完整地表示了广义表的层次和顺序关系。
5 结语
采用D和R所作的数据结构的形式定义的描述,有过度概念化之嫌。R本身已经包含有D中所表示的数据元素,没有必要把D刻意分离出来,因此,数据结构的形式定义完全可以将D和R的描述合二为一,即采用如下所述的更为简洁的方式。例如:
线性表结构可以表示为:
集合结构可以表示为:
普通树结构可以表示为:
二叉树结构可以表示为:
广义表结构可以表示为:
图结构可以表示为:
摘要：分析了数据结构的构成,并在此基础上提出了诸如树型结构和广义表结构等递归的数据结构的数学定义。
关键词：数据结构,数学定义,树形结构,广义表结构
参考文献
[1]殷人昆,等.数据结构(用面向对象方法与C++描述)[M].北京:清华大学出版社,1999,7:163.
[2]徐孝凯.数据结构实用教程[M].2版.北京:清华大学出版社,2006,9:178.
[3]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1979,4:118.
【递归问题】推荐阅读：
语言递归08-15
递归网络09-23
递归算法的教学心得05-26
递归最小二乘算法07-10
非递归二叉树初始化08-30
行程问题——流水问题、过桥问题09-24
吸烟问题,处分问题06-01
制造问题还是解决问题07-16
不成问题的问题影评09-27
问个问题，面试中的问题05-30