递归算法的教学心得（精选7篇）
递归算法的教学心得 篇1
0.引言
在数据结构课程中, “栈与递归”是一个教学难点, 多数教材都将其作为选讲内容。事实上递归算法贯穿了数据结构课程的始终, 如二叉树的递归遍历、二叉排序树的查找、二叉树的线索化、快速排序、归并排序等, 都是递归算法。笔者在多年的教学实践中发现, 如果跳过“递归算法与实现”不讲, 那么学生们对于后面章节中上述算法很难理解透彻。本文探讨了“递归算法与实现”的教学设计, 主要从教学内容的取舍、简单递归算法设计和分析对数据结构中各典型的递归函数之间关联等方面进行了介绍。
1. 关于“栈与递归”的教学内容
在清华大学出版社出版、严蔚敏等编著的《数据结构》教材中, “栈与递归”这一节以三阶汉诺塔问题的递归算法及实现作为实例, 介绍了递归程序如何利用栈的主要特性“后进先出”实现其相互调用和返回[1]:
实际上, 由于汉诺塔问题的特殊性, 每个hanoi函数会分别二次调用hanoi低阶函数, 而且该函数的参数比较多, 给初学者带来了很大的困扰。如果每个递归函数只调用一次低阶函数, 就会容易理解得多。所以, 在介绍这一节的时候, 我们把实例改成了简单的递归形式的阶乘函数:
以此为例介绍递归程序的调用和返回, 路线清晰, 简单明了, 学生们很容易理解和接受。
2. 简单的递归算法设计
为了给进一步的学习打基础, 学习完“栈与递归”, 对于递归函数及其实现有了初步的认识之后, 可以结合数据结构课程, 进行一些简单的递归算法设计。
递归算法的编写需要确定以下内容:
(1) 终止项:描述递归函数的终止条件;
(2) 递归项:将问题分解为与原问题性质相同, 但规模较小的问题。
对于上述阶乘问题, 终止项就是if (n==1) return (1) , 递归项就是:return (n*fact (n-1) ) 。
清华大学曾有一道考研试题:已知la是带头结点的单链表的头指针, 试编写逆序输出表中各元素的递归算法。
我们分析这个问题的终止项, 应该是当指针为空时算法结束, 即La==NULL, 递归项显然可以描述为:Reverse (La->next) 。
综上, 可以编写出该问题的递归算法如下:
3. 几个递归算法的内在联系
递归实质上是一种特殊的函数调用, 与一般调用不同的是, 递归函数调用的是其自身。在数据结构课程中, 递归算法的设计涉及到各个章节, 其中二叉树的递归遍历函数是最重要、也是最典型的递归函数, 很多递归算法都可以和其进行类比。分析几种算法的内在联系, 对于深化“递归”意识, 加深对递归算法的理解, 大有帮助。
(1) n阶汉诺塔问题的执行过程等价于一棵深度为n的满二叉树的中序遍历过程。仔细观察hanoi函数, 我们可以发现其结构与中序遍历二叉树的递归算法非常结构一致, 且n阶汉诺塔问题移动盘片的总数是2n-1。可以构造一棵汉诺塔二叉树[2], 其每个结点对应于一次移动盘片的过程, 中序遍历该二叉树得到的就是n阶汉诺塔的一个解序列。
(2) 快速排序算法的递归算法执行过程等价于一棵二叉树的中序遍历过程。如果把待排序的数据元素的枢轴做为二叉树的根结点, 其左孩子是第一趟快速排序后左半区的枢轴, 其右孩子是第一趟快速排序后右半区的枢轴, 以此类推, 则可以构造一棵二叉树。显然这棵二叉树是一棵二叉排序树, 其形态取决于枢轴元素在子序列中的大小。最理想的情况, 是一棵完全二叉树;最坏情况下, 是一棵单支二叉树。
(3) 归并排序算法的递归算法执行过程等价于一棵二叉树的后序遍历过程。把整个待排序序列当作根结点, 其左半区做为根结点的左孩子;右半区做为根结点的右孩子, 以此类推, 可以构造一棵二叉树。该二叉树的叶子结点显然都是只含有一个元素的子序列, 且整棵二叉树的形态近似于一棵完全二叉树。如果对该二叉树进行后序遍历, 得到的就是归并排序算法的执行过程。
(4) 二叉排序树的查找算法等价于折半查找的判定树的查找过程。虽然查找算法中也出现了两个调用低阶递归函数的语句, 但其由if-else语句控制, 每层调用只选择执行其中的一个。所以虽然表面上看和二叉树的先序遍历相似, 但实际上二者截然不同。事实上二叉排序树上的查找类似于折半查找, 其执行过程是走过了一条从根结点到叶子结点的路径, 而不是遍历整棵二叉树。
4. 结语
递归算法是数据结构课程中的重点和难点。本文通过内容选择、简单递归函数的设计方法和对各递归函数之间关联的分析, 对其教学过程进行了设计, 实践表明有该做法有效地提高了教学质量。
摘要：递归算法贯穿了数据结构课程的始终, 是数据结构课程中的重点和难点。本文探讨了如何对“递归算法与实现”的教学内容进行取舍, 从简单递归函数入手介绍了递归算法的设计方法, 进而分析了数据结构中各典型的不同递归函数之间关联。教学实践证明该教学方案的设计合理有效。
关键词：数据结构,递归,教学设计
参考文献
[1]严蔚敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版社, 1999:52-54.
[2]陈文.汉诺塔非递归算法[J].电脑编程技巧与维护, 2009 (14) :10-11, 51.
[3]贺存薪.Hanoi塔问题的一种非递归算法的C++实现[J].电脑开发与应用, 2006 (4) 54-56:
递归算法的教学心得 篇2
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;
void PreOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
递归算法的教学心得 篇3
“2006年3月,美国卡内基·梅隆大学计算机科学系主任周以真(Jeannette M.Wing)教授在美国计算机权威期刊《Communications of the ACM》杂志上给出并定义了计算思维(Computational Thinking)。周教授认为:计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。”[1]
从笔者本人对计算思维定义的解读中,可以看出计算思维本身和计算机算法以及数学导论有着密切的联系。很多的算法自身即是计算思维最好的体现。例如,分治算法和本文将要提及的递归算法等。同时,计算思维的影响力不仅局限于计算机科学领域。随着智能设备在各领域中出色的表现,这样的思考方式对人类的学习、工作、生活都产生了深远的影响。对智能设备的选择和依赖也在影响着人类思考问题的方式。笔者认为计算思维已成为学生持续发展所必须具备的一种基本能力。日常的教学工作要以此为中心开展,处理好“道”与“术”的关系。让学生在学习过程中体会计算机学科的本质:“抽象化”和“自动化”。中小学阶段程序设计类课程应避免繁杂的语法,而将问题的抽象、算法的构造、程序的实现和相应结果的评价作为学习的重点。这是笔者选择App Inventor作为学生程序编写平台的主要原因。
App Inventor是Google公司开发,并通过麻省理工学院完善和发展的编程平台。App Inventor是用于在Android平台上开发移动应用的编程工具。在基于Web的图形化用户界面生成器中,学生可以随意拖拽编程模块,像搭积木一样完成代码的拼合,生成应用程序。App Inventor简单易用,对于学生来说,无需记忆太多繁杂的语法。有效避免了学生在体会解决逻辑性问题的乐趣前,就放弃自己的想法。虽然事件驱动机制并非App Inventor所特有,但积木式的搭建过程让这一机制更易于学生的学习和理解,让编程更加贴近生活。
二、初中生计算思维培养的案例分析
接下来,本文将通过一节递归算法的教学实录来和各位老师一起交流关于培养学生计算思维的问题。
整个课程分两个课时完成,第一课时的关键词:抽象、延展。第二课时的关键词:实现、创新。
(一)第一课时:由特例到本质,由本质到一般
教学活动从一个经典的游戏:汉诺塔作为开始。让学生在游戏中总结求解思路,体会递归的本质。游戏及其规则简述如下:有A、B、C,3根柱子,有n个大小不同、编号依次为1,2,3,…,n的圆盘按照从小到大的顺序叠放在A柱上。现要求将这n个圆盘移至B柱上并仍按同样顺序叠放。当盘子数n等于1时,求解过程简单且直观,只需要1步即可将盘子从A柱直接移动到B柱。当盘子数n等于2时,难度也不大。学生可以很快计算出移动步数3。对于移动步骤的表述思路很清晰。其过程为,先将小盘从A柱移动至C柱,再将大盘从A柱移动至B柱,最后将小盘从C柱移动至B柱即可。此时,学生无例外地用自上而下、自小到大顺序式描述方式来表述移动过程。当问题规模再次增加,将盘子总数设为3个时,求解所花费时间明显增加。在对移动步骤的表述中,仅有依靠笔记的小组顺利完成过程性的描述。讲到这里时,笔者开始带领学生一起思考这样的问题:游戏的求解是否有规律可循?当盘子数为1时,答案很明显是1步。当盘子数为2时,对于问题的处理,不妨换一种思考方式,要想将大盘从A柱移动到B柱,并不能直接移动,要先处理小盘,将小盘从A柱移动到C柱。因为小盘上没有别的盘子,所以直接移动即可。此时移动步数是1步。但仅移动小盘,问题并没有得到解决,还需要处理大盘和移回小盘。处理大盘需要1步,移回小盘需要1步,最后得到总步数3。再用同样的思考方式来处理盘数为3的情况。想要将大盘移动至B柱,必须要处理小盘和中盘。如果小盘和中盘能到C柱上,问题就迎刃而解。此时,新问题可以描述为如何将中盘和小盘由A柱借助B柱移动至C柱,需要处理盘子的数量变成2个,整个问题的规模减少1,性质没有发生变化。关于这个问题的处理我们在盘数n等于2的情况下,已经讨论过了,中盘和小盘由A柱借助B柱移动至C柱,完全可行,并且移动步数等于3。当小盘和中盘移动至C柱后,可以顺利将大盘移动至B柱,移动步数加1。最后,再将小盘和中盘由C柱借助A柱移动到B柱,此时,又变为盘数为2的移动情况,依据前面的结果可以得出最后的移动步数为3加1加3,总步数为7。为了加深学生的理解,给学生一个思考的缓冲,笔者请学生计算了当n等于4的情况。很快,就有了7加1加7,总步数为15的结果。
基于这样的思考方式,把刚才的文字表述再抽象化,用数学表达式表示刚才的思考过程。笔者带领学生一起探究:如果用F(n)表示n个盘子借助第三根柱子移动至相邻的柱子所需步数,那么F(n)究竟等于什么?经由先前的分析,想要将第n个盘子直接移动至目标柱子,需要先处理前n-1个盘子。将这n-1个盘子由A柱借助B柱移动到C柱上。从问题描述中,不难发现这n-1个盘子的移动步数恰好是F(n-1)的值。将第n个盘子移动至B柱,需要1步。再用同样的方法移回前n-1个盘子,可以求得F(n)的表达式为:F(n)=F(n-1)+1+F(n-1)。化简可得:F(n)=2F(n-1)+1。由此表达式不难看出,F(n)的求解依赖F(n-1)的值,F(n-1)的求解依赖F(n-2)的值………,直到问题的规模减少到只剩1个盘子。此时,F(1)=1。在求解过程中,所求问题性质没有变化,变化的只是问题的规模:可以移动的盘子数量在不断的减少,直到剩余1个盘子。至此,在学生的脑海中完整建立起递归的概念。“一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。”[2]
课程讲到这里的时候,课堂授课结束。在校学习活动结束并不意味着整个学习活动结束,相反,学生的自主学习才刚刚开始。基于学生的学情和教学目标,笔者希望让学生掌握和运用这样的思考方式理解和处理问题,而非刻意把每个学生培养成程序员,所以课后的学习任务是这样安排的:第一,让学生搜集整理生活中“递归”的现象和实例并给予合理的解释说明,不要将思维局限于计算机科学领域。第二,让学生将关于计算汉诺塔移动步数的代码片段补充完整,并测试结果是否正确。第三,选做,请有能力的学生用递归的思路展示汉诺塔的求解步骤。
(二)第二课时:展示资料搜集和程序运行的成果
以下分享给各位老师的是几个非常有意思的展示实例:
故事中的递归:从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事,他说,从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事,他说,从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事……。
诗句中的递归:“你站在桥上看风景,看风景的人在楼上看你,明月装饰了你的窗子,你装饰了别人的梦”-卞之琳《断章》。关于递归的解释,你成为别人眼中的风景,而别人又是另外人眼中的风景,如此往复。关于梦境也是如此,你在别人的梦中,梦到你的人又在新的人梦中。
图片中的递归:德罗斯特效应,德罗斯特效应是递归的一种视觉形式,图中人物手持的物体中有一幅其相同的小图片,小照片的内容也是该人物手持相同的但更小的照片,如此往复。
声音的递归:当我们将麦克风对准音箱小声说话,这些声音被麦克风捕获,又传至音箱放大,再传回麦克风,如此交替往复,就会出现尖锐的爆音。
文件夹复制的递归:建立目标文件夹,如果源文件夹内有文件,直接复制。如果遇见新的文件夹,继续使用同样的方法,先建立目标文件夹,查看源文件夹内是否有文件,如果有,直接复制,如果遇见文件夹,继续用同样的方式处理,直到把整个文件夹复制完毕。因为文件的存储结构是树状结构,所以上述过程也是对树状结构遍历的过程。
此外还有一些关于计算结果的探究也很有意思:当n=1时,需要1步;当n=3时,需要7步;当n=31时,需要2147483647步;当n=64时,需要18446744073709551615步;当n=100时,需要1267650600228229401496703205375步;实际上,便携式智能设备计算能力都是相当有限的,当计算到n等于10时,就已经无法显示计算步骤了。已经出现了溢出错误,但计算还可以继续。当盘数等于30的时候,如果移动一个盘子需要1秒钟,完成整个移动过程,在人类的有生之年已经成为不可能的事情。关于结果的计算,还有让人更为激动的发现,当n等于100时,平板设备已经无法进行计算了,有溢出错误。那么n等于100时的结果是如何算出来的呢?学生的解释,实际上F(n)还可以等于2n-1。当n=1时,F(n)=1=21-1,当n=2时,F(n)=3=22-1,当n=3时,F(n)=7=23-1,当n=4时,F(n)=15=24-1……,虽然还无法给出证明,但这样的发现足以让人欣慰。
App Inventor递归代码的注解,移动步数的计算和移动过程的显示都是由按钮的点击事件触发。当按钮1被点击时,首先清空全局step变量,便于显示移动步骤。然后调用Hanoi2过程完成移动步数的计算。Hanoi2过程是对F(n)=2F(n-1)+1的翻译。在Hanoi2被调用时,先判断当前盘数是否为1,如果为1,直接返回结果1,否则,返回2倍的Hanoi2(n-1)加1的值。当移动步数计算完毕后,再通过Hanoi过程递归展示移动过程。如果当前只有1个盘子的时候,显示A->B,直接移动即可。如果盘数不为1,调用Hanoi过程,将前n-1个盘子由A借助B,移动到C。然后将最大的盘子由A移动到B,最后再次借助递归的思路,将C柱上的n-1个盘子由C借助A移动到B即可。
三、应用效果
通过本次学习,学生的收获如下:
(一)基本语法层面,掌握了App Inventor中,带返回值的过程模块的定义和调用。
(二)对递归算法本质的认识,通过将原问题不断分解为本质相同但问题规模更小的新问题来求解原问题的过程,以及相对应的数学模型。
(三)能够将递归算法代码化,体会相对于递推写法的短小和易可读性。
在代码化的过程中,因为解决所有的问题都是同一种方法,所以看到了函数调用自身的情况。
(四)突破对算法认识的局限。
算法不仅仅存在于计算机科学领域,在生活中其他地方都有其身影。对于递归算法的表述并非编程语言的专利,利用两块相对的镜子也可轻松制造出递归算法。
(五)程序设计中,递归是难以理解的算法之一。
很多时候,光是读懂代码已经很费力了,特别是提炼不出问题模型的时候,设计递归是非常困难的。对于竞赛生来说,本次学习是帮助其建立递归算法模型的过程。
(六)给学生一个爱上信息课的理由。
很多时候,学生爱上信息课的理由仅仅是能放松,能使用电脑,能上网,并不是得益于思考的收获。通过本次课程,让更多的学生切身感受到信息学科的魅力所在。
四、结束语
课程已经接近尾声,对计算思维培养的探索却只是一个开始。在这个阶段,难免会有一些错误的认识,例如:有时,老师会将学生天马行空的幻想认为是计算思维的体现。幻想和思维二者相差甚远,不可同日而语。我们要培养的是一种能力,是一种思考的习惯,是一种持久的东西,让学生终身受益的东西,需要扎实的知识积累,让学生在学习的过程中更多去体会,理解本质性的东西,为普适性的创新做好准备,而不是胡思乱想。随着计算思维的培养不断提上中小学教育的日程,吸引更多的优秀教师投身于此,不觉让人无比期待这群孩子的明天。
参考文献
[1]周以真.计算思维_百度百科.http://baike.baidu.com/li nk?url=7709Nm Cn NJPKYIbe0WBc BYfej8j Fk JTDZK6ts W8U9Blnp Qocb7sd_nbd9Pl2UNFWG880U6KMX-z DKx JYxam M3K,2016-09-10.
二叉树操作的递归算法分析 篇4
二叉树是数据结构课程内容中的重点和难点,学好数据结构就必须要掌握二叉树的存储结构和基本操作的算法。二叉树最常用的存储结构是二叉链表,根据二叉链表的示意图,我们很容易理解二叉树的这种存储形式。因此,掌握二叉树的关键就是要理解二叉树基本操作的算法。本文将分析二叉树操作的递归求解方法,以求和数据结构爱好者共同学习和研究。
2 递归
递归是一种非常有用的算法设计工具。一个函数、过程如果在其定义或说明内部直接地或间接地出现有其本身的引用,这种用自己定义自己的方法称之为递归[1]。
递归方法实际上是将一个原问题转化为和原问题相同的子问题,只不过子问题的规模比原问题的规模要小。这种转换多次进行,直到满足某个约束条件为止。用递归方法求解问题关键就是要确定两方面内容:(1)子问题(2)递归结束条件。
例如:求n!
因此,可将原问题“求n!”转换为子问题“求(n-1)!”,原问题和子问题为同样的问题,都是求某数的阶乘,但子问题数字小。随着不断转换,子问题数字越来越小,当求1!时,可直接给出值1。所以,递归结束条件就是n=1。
3 二叉树操作的递归求解方法
二叉树的特点是每个结点至多只有两棵子树(左子树和右子树),且左右子树也是二叉树。因此,二叉树或者为空,或者可分为三部分:根结点、左子树、右子树。由于二叉树中的左子树和右子树也是二叉树,因此,二叉树的组成具有递归的特点,那么,二叉树的许多操作可考虑用递归方法来描述。下面将讨论几个常见二叉树操作的递归算法。
3.1 遍历二叉树
遍历二叉树是指按某条搜索路径巡访二叉树中的每个结点,使得每个结点均被访问一次,而且仅被访问一次[2]。常见的二叉树遍历方法有三种:先序遍历、中序遍历、后序遍历,下面以先序遍历为例,分析其递归算法。
先序遍历二叉树的思想是:若二叉树为空,则没有任何结点可访问,因此空操作;当二叉树不为空时,先序遍历二叉树就是要:访问根结点、先序遍历左子树、先序遍历右子树。采用递归方法分析:1)原问题为先序遍历二叉树。2)原问题可分为三步:访问根结点、先序遍历左子树和先序遍历右子树。访问根结点直接对应访问语句,例如输出语句。先序遍历左子树和先序遍历右子树这两个问题都属于先序遍历二叉树的问题,与原问题一样,只不过左子树和右子树比原二叉树规模要小。因此,子问题为先序遍历左子树和先序遍历右子树。3)递归结束条件就是二叉树为空。
确定递归算法的子问题和递归结束条件后,就可写出先序遍历的递归算法:
3.2 建立二叉树的二叉链表
建立二叉树的二叉链表存储结构是二叉树的必备操作,因为在程序中,只有创建了二叉树的二叉链表存储结构,才可以进行二叉树的其他操作。显然,二叉树中的每个结点对应二叉链表中的一个结点,因此,创建二叉链表,就是要为二叉树中的每个结点建立一个结点存储结构。可以按照某种遍历顺序依次为各个结点建立存储结构。若按照中序遍历顺序或后序遍历顺序建立,则在建立二叉链表过程中,已建立的结点是分散的、不能连接成一个链表,这就不易掌控所有已建立的结点。如果按先序遍历顺序建立,则已建立的结点都可链接在根指针所指的二叉链表中。因此,可按先序遍历的顺序为各个结点建立存储结构。
建立二叉树的二叉链表的算法思想是:若二叉树为空树,则根指针应设置为空;若二叉树非空,则为根结点建立存储结构,再建立左子树的二叉链表和右子树的二叉链表。采用递归方法分析:1)原问题为建立二叉树的二叉链表。2)子问题为建立左子树的二叉链表和建立右子树的二叉链表。3)递归结束条件是二叉树为空树。
根据用户输入的序列,建立二叉树的二叉链表的递归算法如下:
使用此算法建立二叉树的二叉链表,用户在输入结点序列时要注意:空子树也要输入,用空格代表空子树。例如图1所示二叉树,应首先标出空子树,见图2,然后对其先序遍历得到输入序列:AB__CD__E__。
3.3 求二叉树的深度
二叉树深度可按如下规则求取:当二叉树为空树,则深度为0;当二叉树只有一个结点,则深度为1;否则,二叉树的深度为左子树深度和右子树深度中的较大值,再加上1。采用递归方法分析:1)原问题为求二叉树的深度。2)子问题为:求左子树深度和求右子树深度。3)递归结束条件是二叉树为空或者二叉树只含有一个结点。根据上面分析,可得到如下递归算法:
3.4 返回结点e的左兄弟
采用递归方法分析:1)原问题为在一棵二叉树中找结点e的左兄弟。2)子问题可设定为在左子树中找结点e的左兄弟,和在右子树中找结点e的左兄弟。3)递归结束条件可有两种情况:a)若二叉树为空树,则结点e的左兄弟不存在;b)若根结点的右孩子为结点e,则结点e的左兄弟为根结点的左孩子。递归算法如下:
4 总结
二叉树是数据结构课程中的重要内容,掌握二叉树关键是掌握二叉树各种操作的算法。本文采用递归方法分析了二叉树的先序遍历、创建二叉链表、求深度、求结点e的左兄弟这四个操作的求解方法。对于二叉树的许多其他操作,也可以与此类似,采用递归方法求解。
摘要：二叉树是数据结构课程中的重点内容。由于二叉树本身具有递归的特点,因此二叉树的许多操作可采用递归方法求解。该文首先介绍了递归方法,然后采用递归方法分析二叉树的几个常见操作,并给出详细算法。
关键词：递归,二叉树,遍历,算法
参考文献
[1]李伟.浅析C语言递归算法[J].电脑知识与技术,2012(10).
递归算法分析中主定理的应用 篇5
1 主定理的引入
主定理:设a≥1, b>1为常数, 为函数, T (n) 为递归式T (n) =αT (n/b) +f (n) ……式①
对非负整数定义, 其中n/b为[n/b]或[n/b]。则T (n) 可能有如下渐进界:某常数, 有, 则;
1.1某常数ε>0, 有f (n) =O (n (logbα) -ε) , 则T (n) =Θ (nlogbα) ;
1.2f (n) =Θ (nlogbα) , 则T (n) =Θ (nlogbαlgn) ;
1.3对某常数ε>0, 有f (n) =O (n (logbα) -ε) , 且对常数c<1与所有足够大的n, 有af (n/b) ≤cf (n) , 则T (n) =Θ (f (n) ) 。
在主定理中, 通过将函数f (n) 与nlogbα函数进行比较, 得出T (n) 的渐进界由其中较大的函数决定。包括了三种情况:
2 主定理的证明
欲证明主定理的正确性, 需分两部分进行:首先分析递归式①, 将其简化成T (n) 仅定义在b>1的整数幂上, 即n=1, b, b2, …;然后证明扩展到所有正整数n都成立。
2.1 三个引理
欲证明递归式①在n=bi正合幂上成立, 需引入如下三个引理。引理1.设a≥1, b>1为常数, f (n) 为定义在b的正合幂上的非负函数, 定义递归式T (n) 为:
引理2.设a≥1, b>1为常数, f (n) 为定义在b的正合整数幂上的非负函数, 函数g (n) 有如下定义:对于b的整数幂, 该函数可被渐进限界为:
引理3.设a≥1, b>1为常数, 为定义在b的整数幂上的非负函数, 按式问定义递归式T (n) , 则T (n) 可能有如下渐进界:
2.2 上取整和下取整时的证明
显然主定理在n取b的整数幂的范围内成立, 下面将n扩展到整个整数范围内, 即主递归式中包含上取整函数或下取整函数的形式:
本文给出含上取整函数式④的证明, 下取整的情况式③类似, 读者可自行证明之。
构造式④的递归数, 如图1所示。其中,
下面确定递归树的深度k, 由于|x|≤x+1, 于是,
一般地, 有
当j=|logbn|时, 有
由此可知, 在深度为[logbn]时, 问题大小至多为常数。因此由图可得:
接着求和式⑥的值,
情况一, 证明类似引理2的证明略。
情况二, 有f (n) =Θ (nlogbα) , 由于j≤|logbn|隐含bj/n≤1, 界f (n) =O (nlogbα) 隐含存在常数c>0, 使对足够大的nj, 有:
于是情况②得证。
情况三, 对n>b+b/ (b-1) , 有αf (|n/b|) ≤cf (n) , c<1为常数, 则αjf (nj) ≤cjf (n) 。于是
此处C为常量, 有g (n) =Θ (f (n) ) 。至此主定理证明完毕。
3 主定理的应用
3.1 二路归并算法的
归并法 (merge) , 是将两个或多个有序表合成一归并算法的思路是将两个有序表合并成一个有序表。对于拥有n个元素的表, 其合并表的时间花费为n, 因此, 二次归并算法的时间复杂度可使用递归式T (n) =2T (n/2) +n表示。
使用主定理求解, a=2, b=2, f (n) =n, 则。第二种情况成立, 故递归式的解为T (n) =Θ (nlogbαlgn) =Θ (nlgn) 。
3.2 大整数乘法的分析
大整数乘法是分治法的具体应用, 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题, 这些子问题相互独立且与原问题相同。设X和Y是n位的二进制整数, 为求它们的乘积XY, 将X和Y分为2段, 每段长为n/2位 (假设n是2的幂) , 如图2所示。
由此, X=A2π/2+B, Y=C2π/2+D, X和Y的乘积为:
这样只需做3次n/2位乘法, 因此,
使用主定理求解a=3, b=2, 则f (n) =O (nlog23-6) , 其中ε=1。第一种情况成立, 故递归式的解为T (n) =Θ (nlogbα) =Θ (n1.59) 。
4 结论
本文给出的基于主定理的递归算法分析能够很好的解决基于分治算法的递归问题分析。
摘要：算法的时间和空间复杂度分析是计算机算法设计的重要内容, 递归算法的时间复杂度分析尤为困难。给出了主定理的证明, 并讨论了如何利用主定理来分析一类递归算法的时间复杂度, 最后给出了主定理实用的范围。
关键词：递归,主定理,递归树,分治算法,算法分析
参考文献
[1]王晓东.算法设计与分析[M].北京:清华大学出版社, 2003, 19.
[2]Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, CliffordStein.潘金贵等译.算法导论第二版[M].北京:机械工业出版社, 2010, 43.
由遍历结果还原二叉树的递归算法 篇6
1 二叉树创建的常规方法
对于二叉树的创建,常规的方法是将二叉树补充成完全二叉树,如图1和图2所示,然后,自上而下,从左到右输入各结点值,假定,第一个结点(根结点)编号为1,第二个结点编号为2,…,依此类推,则第i个结点如果有左孩子,其左孩子结点编号为2i,如果有右孩子,右孩子结点的编号为2i+1,根据这个性质就能建立起结点间的联系,达到创建二叉树的目的。但是,由于补充的虚拟结点太多,在输入相关信息时,容易因少输或多输虚拟结点而出错。
2 由遍历结果生成二叉树
2.1 由中序后序遍历结果生成二叉树的算法实现
2.1.1基本思想
二叉树的遍历通常有前序、中序及后序三种,由二叉树的一种遍历结果是无法唯一确定一棵二叉树,但由二叉树中序及后序的遍历结果可以唯一确定二叉树[2]。这个性质可由如下归纳法证明:
证明:设n为结点个数。(1)当n=0时,此时,后序遍历序列和中序遍历序列都是空,该二叉树是空树,而空二叉树是唯一的,命题成立。
(2)设n<=k-1时,命题成立则
(3)当n=k时,对于有k个结点的二叉树,后序遍历序列中的最后一个结点必然是该二叉树的根结点,所以,根结点是唯一的。
不妨设根结点在中序序列中处于第i个(i>0),则中序序列中,前i-1个为左子树,后k-i个为右子树。后序序列是由左子树序列、右子树序列及根结点构成,所以,后序的前i-1个所包含的元素必然与中序的i-1个一样,后序从第i个往后的k-i个元素必为右子树的元素。
而i-1
也就是说,当n=k时命题成立。
由(1)、(2)、(3)可知对于任意个结点的二叉树都可由后序遍历序列和中序遍历序列唯一确定。
下面举例说明,设二叉树中序遍历结果为d b e a g f h i c,后序遍历结果为d e b g i h f c a则可以完全确定二叉树如图1所示。
其基本思想是:
1)由后序结果的最后一个结点为a可知,该二叉树的根结点必然是a
2)由于根点为a,从中序遍历结果中找到a所在住置,如此,便能断定其左子树必然由d b e三个结点构成,右子树必然由g f h i c构成。
3)由后序遍历的定义可知,在后序遍历结果中,左子树的三结点d b e必然在右子树的五个结点g f h i c之前,于是,根据左子树、右子树的结点个数把后序遍历结果准确分为左子树、右子树及根结点三部分。
4)利用得到的左右子树的中序及后序结果,重复上述步骤,直到某一子树为空为止,如此便完成二叉树的建立。整个过程如图3,图4,图5……
2.1.2算法实现
根据以上的分析,我们可以得到由中序后序的遍历结果构造二叉树的递归方法。
1)二叉树的结点定义
2.2 由前序序列和中序序列生成二叉树的递归算法
基于同样的分析,可以得到由前序和中序的遍历结果还原二叉树的方法,同样可以用递归方法实现。
TREENODE*createTree(int m1,int n1,int len)//m1参与建树结点在中序遍历中的起始位置
2.3 由层次遍历序列和中序遍历序列生成二叉树的递归算法
首先说明中序遍历序列的含义,如图6,中序结果为d b e a g f h i c,二叉树严格按左子树靠左,根结点居中,右子树靠右画法,则中序遍历的结果即为结点从左到右的排列。
利用数学归纳法同样可以证明,由层次遍历结果与中序遍历结果可以唯一确定二叉树。在此,不再作证明,仅用图例说明创建二叉树过程。
设:中序遍历结果为d b e a g f h i c层次遍历结果a b c d e f g h i则
1)结点的左右顺序如图7;
2)层次遍历的第一个结点为a,可知a为根结点,左子树为d b e,左右子树g f h i c,如图8;
3)对于左子树d b e,由层次遍历的次序可知b为根结点,对于右子树g f h i c,由层次遍历的次序可知c为根结点如图9;
4)对于子树的子树,同样按照上述的方法确定结点位置,直到结点个数为0为止。
利用层次遍历结果和中序遍历结果还原二叉树的算法
中序序列中的每个元素,在层次序列的都有相应的序号,序号最小者即为根结点,为计算方便,用数组inOrderValue[]存储每个中序元素在层次序列中的位置(即序号)。方法是:
3 结束语
由二叉树的遍历结果还原二叉树的递归算法,可以省去输入众多虚拟结点的麻烦,减少输入错误的可能性,这样,可以把更多的精力专注于二叉树相关操作算法的实现。
参考文献
[1]耿国华.数据结构――C语言描述[M].西安:西安电子科技大学出版社,2006.
递归算法的教学心得 篇7
神经网络由于具有理论上能逼近任意非线性函数的能力,在非线性系统的辨识中有着广泛的应用。传统的前向神经网络属于静态网络,在处理非线性动态系统的应用中存在很多不足。递归神经网络能通过内部反馈环节自动存储动态信息并实现动态映射,用于系统辨识时无需知道详细的对象知识,特别不需要假定模型的阶次,这是其突出的优点。正因如此,近年来递归神经网络的研究引起了人们的极大兴趣[1]。但目前沿用的仍是Pineda提出的递归神经网络的BP学习算法,它是依据梯度法来进行的,因此会产生局部收敛和收敛速度慢等缺陷。本文将LM算法应用于目前应用较多的对角递归神经网络,并在非线性动态系统建模中与BP学习算法的递归神经网络进行比较,发现前者明显优于后者。
1LM算法
LM算法是牛顿法的变形,用以最小化那些作为其它非线性函数平方和的函数。构造优化性能指数F(W)的算法,其目的是求出使F(W)最小化的W值。假设F(W)是平方函数之和,即:
undefined。 (1)
那么第j个梯度分量[∇F(W)]j为:
undefined。 (2)
由此梯度∇F(W)可以写成矩阵形式:
∇F(W)=2JT(W)e(W) 。 (3)
其中:J(W)为雅可比矩阵,即:
undefined
。 (4)
下一步计算赫森矩阵∇2F(W),其中赫森矩阵的第k,j元素为:
undefined。 (5)
则 ∇2F(W)=2JT(W)J(W)+2S(W) 。 (6)
其中:undefined。如果假设S(W)很小,则:
∇2F(W)≌2JT(W)J(W) 。 (7)
根据牛顿法的迭代关系有:
Wk+1=Wk-(∇2F(W))-1∇F(W) 。 (8)
把式(3)、式(7)代入式(8),可得:
Wk+1=Wk-[JT(Wk)J(Wk)]-1JT(Wk)e(Wk) 。 (9)
由于矩阵H=JTJ可能不可逆,这可以用下述近似赫森矩阵改进:
G=H+μI 。 (10)
其中:I为单位矩阵;μ为系数。该矩阵是可逆的,则:
Wk+1=Wk-[JT(Wk)J(Wk)+μkI]-1JT(Wk)·e(Wk) 。 (11)
或 ΔWk=-[JT(Wk)J(Wk)+μkI]-1JT(Wk)·e(Wk) 。 (12)
这种算法的特点是:不需要计算二阶导数。当μk增加时,它接近于有效学习速度的最速下降算法:
undefined。 (13)
当μk下降到0的时候,算法变成了:
Wk+1=Wk-[JT(Wk)J(Wk)]-1JT(Wk)e(Wk) 。 (14)
式(14)即为牛顿法的变形。
算法开始时,μk取小值。如果某一步不能减小F(W)值,则将μk乘以一个θ>1后再重复这一步,最后F(W)会下降。如果某一步产生了更小的F(W),则μk在下一步被除以θ,可以提高收敛速度。这样该算法提供了快速性和收敛性之间的一个折衷[2]。
2对角递归神经网络的LM学习算法
对角递归神经网络(Diagonal Recurrent Neural Network,DRNN)是一个三层网络[1,3]。设在每个离散时刻k网络输入为ui(k),i=1,2,…,m;网络输出为y(k);隐层输入、输出分别为xj(k)、rj(k),j=1,2…,q;输入层至隐层的连接权为whji;隐层至输出层的连接权为wundefined;递归神经元连接权为wundefined;记ND={Um,Hq,Yn}。为了计算和训练方便,取一个输出(对于多输出情况与此相似),即n=1,ND={Um,Hq,Y1}。则DRNN输入、输出关系为:
undefined。 (15)
rj(k)=f(xj(k)) 。 (16)
undefined。 (17)
设网络的期望输出为z(k),取性能指标函数为:
undefined。 (18)
undefined。 (19)
设undefined,则:
undefined。 (20)
undefined。 (21)
设undefined,则:
undefined。 (22)
undefined。 (23)
所以
undefined
。 (24)
其中:i=1,2,…,m,是待求权的数目。由此得出DRNN的LM学习算法具体步骤如下:
(1) 初始化权值和所有其它参数,使W(0)=random(·),P(0)、Q(0)为适当的值。
(2) k←1。
(3) 取当前最新的样本数据(Uk,Zk),按式(16)和式(17)计算DRNN的隐含层输出rj(k)和网络输出y(k),计算目标函数F(k)。
(4) 计算e(k)=z(k)-y(k)。
(5) 按式(24)构成J(Wk)阵。
(6) 计算ΔWk=-[JT(Wk)J(Wk)+μkI]-1·JT(Wk)e(k)。
(7) 用Wk+ΔWk重复计算目标函数。若新的计算结果小于原来的计算结果,则把μk除以θ,并设Wk+1=Wk+ΔWk,转第(3)步;若新的计算结果没有减少,则μk乘以θ,转第(6)步。当误差平方和减小到某个目标误差时,算法被认为收敛。
3非线性动态系统的仿真研究
严格地讲,实际过程都是非线性的,是非线性动态系统,所以非线性动态系统的建模难以避免。本文应用所提出的算法对非线性动态系统建模进行了仿真研究,取得了很好的效果。
假设系统结构未知,非线性系统模型为:
y(u)=8+2e1-u2cos(2πu) 。
其中:输入样本集u==0∶0.04∶4 。
选择DRNN为模型训练网络,输入为u(k),输出为y(k);选择DRNN的结构为(2,7,1)。为进行比较,分别对BP算法和LM算法进行训练,均训练100步。采用BP算法训练该网络,学习速率η=0.45,仿真结果见图1(a)。采用LM算法,设参数P(0)=0、Q(0)=0,仿真结果见图1(b)。比较二者可知,在同样的训练次数下,用对角递归神经网络LM的学习算法建立的非线性系统模型比用BP算法建立的模型精度要高,说明LM算法较BP算法收敛速度快。
4结论
本文将LM算法引入对角递归神经网络的权值学习中,克服了传统的递归BP算法收敛速度慢的缺陷。仿真结果表明所提出的对角递归神经网络LM算法比传统递归BP算法有更快的收敛性和更高的辨识精度,用于非线性动态系统建模是有效的。
摘要：针对递归神经网络传统BP学习算法收敛慢的缺陷,将Levenberg-Marquardt(LM)算法引入到对角递归神经网络权值的训练,这种算法提供了快速性与收敛性之间的一个折衷。仿真结果表明,该算法比传统BP算法具有更快的收敛速度,用于非线性动态系统的建模是有效的。
关键词：对角递归神经网络,LM算法,非线性动态系统,系统建模
参考文献
[1]徐丽娜.神经网络控制[M].北京:电子工业出版社,2003.
[2]哈根.神经网络设计[M].戴葵,译.北京:机械工业出版社,2002.