高中信息技术全国青少年奥林匹克联赛教案递归算法汇总.doc

该【高中信息技术全国青少年奥林匹克联赛教案递归算法汇总 】是由【泰山小桥流水】上传分享，文档一共【4】页，该文档可以免费在线阅读，需要了解更多关于【高中信息技术全国青少年奥林匹克联赛教案递归算法汇总 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总1/4高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总信息学奥赛中的基本算法(递归算法)递归算法的定义:若是一个对象的描述中包含它自己,我们就称这个对象是递归的,这类用递回来描述的算法称为递归算法。我们先来看看大家熟知的一个的故事:从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事,他说从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事,他说上边的故事自己是递归的,用递归算法描述:procedurebonze-tell-story;beginif讲话被打断then故事结束elsebegin从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事;bonze-tell-story;endend;从上边的递归事例不难看出,递归算法存在的两个必要条件:1)必定有递归的停止条件;2)过程的描述中包含它自己;在设计递归算法中,如何将一个问题转变成递归的问题,是初学者面对的难题,下面我们经过解析汉诺塔问题,看看如何用递归算法来求解问题;递归算法应用例1:汉诺塔问题,以以下图,有A、B、C三根柱子。A柱子上按从小到大的序次堆放了N个盘子,现在要把全部盘子从A柱搬动到C柱,搬动过程中可以借助B柱。搬动时有以下要求:1)一次只能搬动一个盘子;2)不一样意把大盘放在小盘上边;3)盘子只能放在三根柱子上;算法解析:当盘子比很多的时,问题比较复杂,所以我们先解析简单的情况:若是只有一个盘子,只要一步,直接把它从A柱搬动到C柱;若是是二个盘子,共需要搬动3步:1)把A柱上的小盘子搬动到B柱;2)把A柱上的大盘子搬动到C柱;3)把B柱上的大盘子搬动到C柱;若是N比较大时,需要很多步才能完成,我们先考虑可否能把复杂的搬动过程转变成简单的搬动过程,若是要把A柱上最大的盘子搬动到C柱上去,必定先把上边的N-1个盘子从A柱搬动到B柱上暂存,按这类思路,就可以把N个盘子的搬动过程分作3大步:(1)把A柱上边的N-1个盘子搬动到B柱;1高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总4/4高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总2)把A柱上剩下的一个盘子搬动到C柱;3)把B柱上边的N-1个盘子搬动到C柱;其中N-1个盘子的搬动过程又可按同样的方法分为三大步,这样就把搬动过程转变成一个递归的过程,直到最后只剩下一个盘子,依照搬动一个盘子的方法搬动,递归纳束。递归过程:procedureHanoi(N,A,B,C:integer;);{以B柱为中转柱将N个盘子从A柱搬动到C柱}beginifN=1thenwrite(A,’->’,C){把盘子直接从A搬动到C}elsebeginHanoi(N-1,A,C,B);{以C柱为中转柱将N-1个盘子从A柱搬动到B柱}write(A,’->’,C);{把剩下的一个盘子从A搬动到C}Hanoi(N-1,B,A,C);{以A柱为中转柱将N-1个盘子从B柱搬动到C柱}end;end;从上边的例子我们可以看出,在使用递归算法时,第一弄清楚简单情况下的解法,尔后弄清楚如何把复杂情况归纳为更简单的情况。在信息学奥赛中有的问题的结构或所办理的数据自己是递归定义的,这样的问题特别适合用递归算法来求解,对于这类问题,我们把它分解为拥有同样性质的若干个子问题,若是子问题解决了,原问题也就解决了。例2求先序排列(NOIP2001pj)[问题描述]给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度≤8)。[样例]输入:BADCBDCA输出:ABCD算法解析:我们先看看三种遍历的定义:先序遍历是先接见根结点,再遍历左子树,最后遍历右子树;中序遍历是先遍历左子树,再接见根结点,最后遍历右子树;后序遍历是先遍历左子树,再遍历右子树,最后接见根结点;从遍历的定义可知,后序排列的最后一个字符即为这棵树的根节点;在中序排列中,根结点前面的为其左子树,根结点后边的为其右子树;我们可以由后序排列求得根结点,再由根结点在中序排列的地址确定左子树和右子树,把左子树和右子树各看作一个单独的树。这样,就把一棵树分解为拥有同样性质的二棵子树,素来递归下去,当分解的子树为空时,递归纳束,在递归过程中,按先序遍历的规则输出求得的各个根结点,输出的结果即为原问题的解。源程序programnoip2001_3;varz,h:string;proceduremake(z,h:string);{z为中序排列,h为后序排列}vars,m:integer;beginm:=length(h);{m为树的长度}write(h[m]);{输出根节点}s:=pos(h[m],z);{求根节点在中序排列中的地址}ifs>1thenmake(copy(z,1,s-1),copy(h,1,s-1));{办理左子树}ifm>sthenmake(copy(z,s+1,m-s),copy(h,s,m-s));{办理右子树}高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总3/4高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总2高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总4/4高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总end;beginreadln(z);readln(h);make(z,h);,在其他很多问题中也可以用到递归思想,如回溯法、分治法、动向规划法等算法中都可以使用递归思想来实现,从而使编写的程序更加简洁。比方上期回溯法所讲的例2《数的划分问题》,若用递回来求解,程序特别短小且效率很高,源程序以下varn,k:integer;tol:longint;proceduremake(sum,t,d:integer);vari:integer;beginifd=ktheninc(tol)elsefori:=ttosumdiv2domake(sum-i,i,d+1);end;beginreadln(n,k);tol:=0;make(n,1,1);writeln(tol);,但它其实不适合用递归算法来求解,如斐波那契(i)数列,它的递归定义为:F(n)=1(n=1,2)F(n)=F(n-2)+F(n-1)(n>2)用递归过程描述为:Funtionfb(n:integer):integer;Beginifn<3thenfb:=1elsefb:=fb(n-1)+fb(n-2);End;上边的递归过程,调用一次产生二个新的调用,递归次数呈指数增添,时间复杂度为O(2n),把它改为非递归:x:=1;y:=1;fori:=3tondobeginz:=y;y:=x+y;x:=z;end;高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总5/4高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总3高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总4/4高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总更正后的程序,它的时间复杂度为O(n)。我们在编写程序时可否使用递归算法,要点是看问题可否适合用递归算法来求解。由于递归算法编写的程序逻辑性强,结构清楚,正确性易于证明,程序调试也十分方便,在NOIP中,数据的规模一般也不大,只要问题适合用递归算法求解,我们还是可以英勇地使用递归算法。高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总7/4高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总4高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总4/4高中信息技术全国青少年奥林匹克联赛教课方案递归算法汇总