收藏 分销(赏)

NOIP基础算法综合.ppt

上传人:丰**** 文档编号:12093387 上传时间:2025-09-11 格式:PPT 页数:92 大小:903KB 下载积分:18 金币
下载 相关
NOIP基础算法综合.ppt_第1页
第1页 / 共92页
NOIP基础算法综合.ppt_第2页
第2页 / 共92页


点击查看更多>>
资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,NOIP,基础算法综合,巴蜀中学 黄新军,第一节 枚举算法,一、枚举法的基本思想,枚举法的基本思想:,根据实际问题设计多重循环,,一一,枚举所有可能的状态,并用问题给定的约束条件检验哪些状态是需要的,哪些状态是不需要的。能使命题成立的状态,即为其解。虽然枚举法本质上属于搜索策略,但是它与后面讲的回溯法或宽度优先搜索有所不同。,二、枚举法的条件,:,可预先确定每个状态的元素个数,n,。如百钱买百鸡问题,,3,文钱一只鸡的状态元素个数可预先确定;,可预先确定每个状态元素,a1,a2,an,的值域。,三、枚举法的框架结构,设,a11,为状态元素,ai,的最小值;,aik,为状态元素,ai,的最大值,(1=i=n),即状态元素,a1,a2,an,的值域分别为,a11=a1=a1k,a21=a2=a2k,ai1=ai=aik,an1=an=ank,。,for(a1=a11;a1=a1k;a1+),for(a2=a21;a2=a2k;a2+),.,for(ai=ai1;ai=aik;ai+),.,for(an=an1;an=ank;an+),if(,状态,(a1,.,ai.,an),满足检验条件,),输出问题的解,;,四、枚举法的优缺点,枚举法的优点:,由于枚举算法一般是现实问题的,“,直译,”,,且是建立在考察大量状态、甚至是穷举所有状态的基础之上的,因此比较直观,易于理解,其算法的正确性也比较容易证明。,枚举法的缺点:,枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价,因此效率比较低。,例题,1,:,砝码称重,【,问题描述,】,设有,1g,、,2g,、,3g,、,5g,、,10g,、,20g,的砝码各若干枚(其总重,=1000,),求用这些砝码能称出不同的重量个数。,【,文件输入,】,输入,1g,、,2g,、,3g,、,5g,、,10g,、,20g,的砝码个数。,【,文件输出,】,输出能称出不同重量的个数。,【,样例输入,】,1 1 0 0 0 0,【,样例输出,】3,例题,1,:,砝码称重,【,思路点拨,】,根据输入的砝码信息,每种砝码可用的最大个数是确定的,而且每种砝码的个数是连续的,能取,0,到最大个数,所以符合枚举法的两个条件,可以使用枚举法。枚举时,重量可以由,1g,2g,20g,砝码中的任何一个或者多个构成,枚举对象可以确定为,6,种重量的砝码,范围为每种砝码的个数。判定时,只需判断这次得到的重量是新得到的,还是前一次已经得到的,即判重。由于重量,=1000g,,所以,可以开一个,a1001,的数组来判重,例题,1,:,砝码称重,伪代码如下:,memset(a,0,sizeof(a);,for(c1=0;c1=a;c1+)/1g,砝码的个数,for(c2=0;c2=b;c2+)/2g,砝码的个数,for(c3=0;c3=c;c3+)/3g,砝码的个数,for(c4=0;c4=d;c4+)/5g,砝码的个数,for(c5=0;c5=e;c5+)/10g,砝码的个数,for(c6=0;c6=f;c6+)/20g,砝码的个数,sum=0;,for(i=1;i=6;i+)sum=sum+ci*wi;,asum=1;/,标记,for(i=1;i=1000;i+)if(ai)num+;/,统计不同重量的个数,coutnum=0,),3.n(n=24),根火柴棍必须全部用上,例题,2,:,火柴棒等式(,NOIP2008,),【,问题简述,】,给你,n(n=A,,满足条件的,A,的最大取值为,1111,。所以枚举,A,和,B,的范围是从,01111,。,为了加快速度,可以将,0,到,2222,的所有整数需要的火柴棒数目提前算好保存在数组中。,五、,枚举算法的优化,枚举算法的时间复杂度:状态总数*单个状态的耗时,主要优化方法:,减少状态总数,降低单个状态的考察代价,优化过程从以下几个方面考虑:,枚举对象的选取,枚举方法的确定,采用局部枚举或引进其他算法,【,例题,3】,给你,n,个整数,然后要有,m,个询问。问第,i,个数字到第,j,个数字所有数字之和。,【,朴素算法,】,cinn;,for(i=1;iai;,for(i=1;ixy;,sum=0;,for(j=x;j=y;j+)sum+=aj;,coutsumn;,for(i=1;iai;si=si-1+ai;,for(i=1;ixy;,coutsy-sx-1endl;,【,例题,4】,最大子矩阵问题,【,问题描述,】,给定一个二维的数组(含正数或负数),请从中找出和最大的子矩阵。例如:,【,例题,4】,最大子矩阵问题,1,、“直译”枚举过程,for(x1=1;x1=n;x1+)/,枚举矩形左上角,(x1,y1),for(y1=1;y1=n;y1+),for(x2=1;X2=n;X2+)/,枚举矩形右下角,(x2,y2),for(y2=1;y2=n;y2+),考察状态左上角为,(x1,y1),右下角为,(x2,y2),内矩形的元素之和;,设,map,为数字矩阵;,sum,为当前矩形内元素的和;,best,为最优解。考察过程如下:,sum=0,;,for(x=x1;x=x2;x+)/,计算当前矩形内元素的和,for(y=y1;ybest)best=sum,;,/,调整最优解,这个算法相当粗糙,枚举状态的费用为,O(n,6,),2,、从减少重复计算入手,有刚才一维情况可以推广到二维,在统计左上角为,(x1,y1),右下角为,(x2,y2),内矩形的元素之和时,我们同样可以先初始化,计算出左上角为,(1,1),右下角为,(x,y),内矩形的元素之和,sxy,。,for(x1=1;x1=n;x1+)/,枚举矩形左上角,(x1,y1),for(y1=1;y1mapij;,sij=si-1j+sij-1-si-1j-1+mapij;,对于状态左上角为,(x1,y1),右下角为,(x2,y2),内矩形的元素之和,可以改为:,sum=sx2y2-sx1-1y2-sx2y1-1+sx1-1y1-1;,if(sumbest)best=sum,;,/,调整最优解,由于利用了计算出的结果,整个算法的时间复杂度降为,O(n,4,),【,例题,4】,最大子矩阵问题,3,、提取恰当的信息,容易观察到,最大子矩阵问题是最大连续子序列和问题的提升,即将一条线换成一个面,将一维问题提升到二维问题。所以我们计算最大子矩阵的方法就是将一行行的数进行累加以求得最大值。,但是还有一个问题,那就是应该如何高效地存储矩阵?,我们可以想到:在一个一维的数列中,设数组,bi,表示从第,1,个元素到第,i,个元素的和,则如果想要求第,i,个元素到第,j,个元素的和,只需要计算,bj-bi-1,的值就行了。由此推广到二维矩阵,设,bij,表示矩阵第,j,列前,i,个元素的和,,aij,表示元素数据,则压缩存储:,for(i=1;iaij;bij=bi-1j+aij;,因此,我们可以使用三重循环求出所有的矩形值,即枚举起始行,i,和终止行,j,,压缩子矩形成为一行,变成一维求最大字段和问题。,即,tk=max(tk-1,0)+bjk-bi-1k;,时间复杂度为,O(n,3,),【,例题,4】,最大子矩阵问题,核心代码,sum=-0 x7fffffff;,for(i=1;i=n;i+)/,阶段,:,起始行,for(j=i;j=n;j+)/,状态,:,结束行,t1=bj1-bi-11;/,初始化第,1,列的值,for(k=2;ksum)sum=tk;,coutsumn,0,时,可以用等号,(,或大于号、小于号,),将,H,n,与其前面的某些项,H,i,(0in),联系起来,这样的式子就叫做递推关系。,解决递推问题的一般步骤,建立递推关系式,确定边界条件,递推求解,递推的形式,顺推法和倒推法,递推的应用分类,一般递推问题,组合计数类问题,一类博弈问题的求解,动态规划问题的递推关系,例题,1,:,faibonacci,数列,【,问题描述,】,已知,faibonacci,数列的前几个数分别为,0,,,1,,,1,,,2,,,3,,,5,,,编程求出此数列的第,n,项。(,n=60,),递推的应用(一般递推问题),递推的应用(一般递推问题),【,例题,2】,输出杨辉三角的前,N,行,【,问题描述,】,输出杨辉三角的前,N,行,(N10),。,【,文件输入,】,输入只有一行,包括,1,个整数,N(N=2),个盘子时,总是先借助,c,柱把上面的,n-1,个盘子移动到,b,柱上,然后把,a,柱最下面的盘子移动到,c,柱上;再借助,a,柱把,b,柱上的,n-1,个盘子移动到,c,柱上;总共移动,h,n-1,+1+h,n-1,个盘次。,h,n,=2h,n-1,+1,边界条件:,h,1,=1,思考:,Hanoi,双塔问题,递推的应用(一般递推问题),【,例题,4】,数的计数,【,问题描述,】,我们要求找出具有下列性质数的个数,(,包含输入的自然数,n),,先输入一个自然数,n(n1000),,然后对此自然数按照如下方法进行处理:,l.,不作任何处理;,2.,在它的左边加上一个自然数,但该自然数不能超过原数的一半;,3.,加上数后,继续按此规则进行处理,直到不能再而 自然数为止;,方法,1,:,用递推,。,用,hn,表示自然数,n,所能扩展的数据个数,,,则:,h1=1,h2=2,h3=2,h4=4,h5=4,h6=6,h7=6,h8=10,h9=10,。分析上数据,,,可得递推公式,:,hi=1+h1+h2+,+hi/2,。时间复杂度,O(n,2,),。,方法,2,:是对方法,1,的改进,。我们定义数组,s.,s(x)=h(1)+h(2)+,+h(x),h(x)=s(x)-s(x-1),此算法的时间复杂度可降到,O(n),。,方法,3,:还是用递推,。,只要做仔细分析,其实我们还可以得到以下的递推公式:,(1),当,i,为奇数时,h(i)=h(i-1);,(2),当,i,为偶数时,h(i)=h(i-1)+h(i/2);,【,思考,】,1.,若,n=10000,怎么计算;,2.,若,n=3000000,怎么计算;,递推的应用(一般递推问题),例题,5,:猴子吃桃问题,1538,猴子吃桃问题。猴子摘了一堆桃,第一天吃了一半,还嫌不过瘾,又吃了一个;第二天又吃了剩下的一半零一个;以后每天如此。到第,n,天,猴子一看只剩下一个了。问最初有多少个桃子?,【,扩展练习,】,猴子分桃,【,问题描述,】,有一堆桃子和,N,只猴子,第一只猴子将桃子平均分成了,M,堆后,还剩了,1,个,它吃了剩下的一个,并拿走一堆。后面的猴子也和第,1,只进行了同样的做法,请问,N,只猴子进行了同样做法后这一堆桃子至少还剩了多少个桃子,(,假设剩下的每堆中至少有一个桃子,),?而最初时的那堆桃子至少有多少个?,【,文件输入,】,输入包含二个数据,数据间用空格隔开。第一个数据为猴子的只数,N(1N10),,第二个数据为桃子分成的堆数,M(2M7),。,【,文件输出,】,输出包含两行数据,第一行数据为剩下的桃子数,第二行数据为原来的桃子数。,【,样例输入,】,3 2,【,样例输出,】,1,15,递推的应用(一般递推问题),【,例题,6】,传球游戏(,NOIP2008,普及),2309,【,问题描述,】,上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着同学们一起做传球游戏。游戏规则是这样的:,n,(,3=n=30,)个同学站成一个圆圈,其中的一个同学手里拿着一个球,当老师吹哨子时开始传球,每个同学可以把球传给自己左右的两个同学中的一个(左右任意),当老师再吹哨子时,传球停止,此时,拿着球没传出去的那个同学就是败者,要给大家表演一个节目。聪明的小蛮提出一个有趣的问题:有多少种不同的传球方法可以使得从小蛮手里开始传的球,传了,m,(,3=m2-3-1,和,1-3-2-1,,共两种。,分析,设,fik,表示,从小蛮开始,,经过,k,次传到编号为,i,的人手中的方案数,传到,i,号同学的球只能来自于,i,的左边一个同学和右边一个同学,这两个同学的编号分别是,i-1,和,i+1,,所以可以得到以下的递推公式:,fik=fi-1k-1+fi+1k-1,f1k=fnk-1+f2k-1,当,i=1,时,fnk=fn-1k-1+f1k-1,当,i=n,时,边界条件:,f10=1,;结果在,f1m,中。,参考代码,cinnm;,memset(f,0,sizeof(f);,f10=1;,for(k=1;k=m;k+),f1k=f2k-1+fnk-1;,for(i=2;i=n-1;i+),fik=fi-1k-1+fi+1k-1;,fnk=fn-1k-1+f1k-1;,coutf1mendl;,样例输入,3 3,样例输出,2,具体过程 见右图,数组的填充过程 按列,递推的应用(组合计数),Catalan,数,定义:,Cn=n+2,条边的多边形,能被分割成三角形的方案数,例如,5,边型的分割方案有:,如图,有一个正,n+2,边形。任取一边,从这边的端点开始,依次给顶点编号为:,0,1,2,3,.,n,n+1(,所取的边端点编号为,:0,n+1),。这样,除线段所在顶点外,还有,n,个顶点:,1,2,3,n,。我们以该线段为三角形的一条边,另一个顶点为,i(1=i=n),。,我们设题意要求的三角形剖分方案数为,H(n),,即除线段顶点,(,编号,0,与,n+1),外,还有,n,个顶点时的三角形剖分方案为,H(n),。则以顶点,0,i,为指定线段,(,上面还有,1,2,i-1,,共,i-1,个顶点,),的剖分数位,H(i-1),;以顶点,n+1,,,i,为指定线段的剖分数为,H(n-i),。根据乘法原理,以,0,i,n+1,为一剖分三角形的剖分数应为:,H(i-1)*H(n-i),,,i=1,2,n,,所得的剖分各不相同,根据加法原理则有:,这与,Catalan,数,C(n),的表达式是一致的。故本题答案为,H(n)=C(n),。,具体实现时,若直接用上述公式计算,对数字的精度要求较高。可将其化为递推式,再进行递推计算,并且注意类型的定义要用,long long,长整型。,Catalan,数的应用(部分和序列),问题:,n,个,1,和,n,个,0,组成一,2n,位的二进制,要求从左到右扫描,,1,的累计数不小于,0,的累计数,试求满足这条件的数有多少?,【,类似,1】,将,n,个,1,和,n,个,-1,排成一行,要求第,1,个数至第,k,个数的累加和均非负,问有几种排列方法?,【,类似,2】,有,2n,个人排成一行进入剧场。入场费,5,元。其中只有,n,个人有一张,5,元钞票,另外,n,人只有,10,元钞票,剧院无其它钞票,问有多少种方法使得只要有,10,元的人买票,售票处就有,5,元的钞票找零?,Catalan,数的应用(栈,NOIp2003,),问题:一个栈,(,无穷大,),的进栈序列为,1,2,3,.n,,有多少个不同的出栈序列?,Catalan,数的应用(加括号),P=A1A2A3,An,,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?,【,分析,】,P(4),:即,4,个数相乘的情况如下:,(a1a2)a3)a4);,(a1(a2a3)a4);,(a1a2)(a3a4);(a1(a2a3)a4);(a1(a2(a3a4),。不失一般性,可以假设最后一次乘法运算如下:,(a1ar)(ar+1an),(1=r=n),。令,P(n),表示,n,个数乘积的,n-1,对括号插入的不同方案数,则:,P(n)=p1pn-1+p2pn-2+.+pn-1p1,p1=p2=1,有:,P(n+1)=p1pn+p2pn-1+.+pnp1 (1),令,C(k)=P(k+1),k=1,2,n,,代入,(1),式,有:,C(n)=C(0)*C(n-1)+C(1)*C(n-2)+C(n-1)*C(0),=,因此,本题的答案为,C(n-1),。,递推的应用(组合计数),错排问题(经典问题),n,个数,分别为,1n,,排成一个长度为,n,的排列。若每一个数的位置都与数的本身不相等,则称这个排列是一个错排。例如,,n=3,,则错排有,2 3 1,、,3 1 2,。编写程序,求,n,的错排个数,分析,我们设,k,个元素的错位全排列的个数记做:,f(k),。,四个元素的错位排列,f(4),我们用穷举法可以找到如下,9,个:,(4,3,2,1);(3,4,1,2);(2,1,4,3),(4,3,1,2);(2,4,1,3);(2,3,4,1),(4,1,2,3);(3,4,2,1);(3,1,4,2),它们有什么规律呢?,通过反复的试验,我们发现事实上有两种方式产生,错位排列,:,A.,将,k,与,(1,,,2,,,,,k-1),的某一个数互换,其他,k-2,个数进行错排,这样可以得到,(k-1),f(k-2),个错位排列。,B.,另一部分是将前,k-1,个元素的每一个错位排列(有,f(k-1),个)中的每一个数与,k,互换,这样可以得到剩下的,(k-1),f(k-1),个错位排列。,根据加法原理,我们得到求,错位排列的递推公式,W(k):,f(k)=(k-1)*(f(k1)+f(k2),分析,递推的应用(组合计数),【,例题,】,编码问题,【,问题描述,】,编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码:把一些有规律的单词编成数字。字母表中共有,26,个小写字母,a,b,c,.,z,。这些特殊的单词长度不超过,6,且字母按照升序排列。把所有这样的单词放在一起,按字典顺序排列,一个单词的编码就对应着它在字典中的位置,例如:,a-1;b-2;z-26;ab-27;ac-28;,你的任务就是对于所给的单词,求出它的编码。,递推的应用(博弈问题),例题:走直线棋问题。有如下所示的一个编号为到的方格:,现由计算机和人进行人机对奕,从到,每次可以走个方格,其中为集,=a,1,a,2,a,3,.a,m,中的元素,(m=4),,规定谁最先走到第,n,格为胜,试设计一个人机对奕方案,摸拟整个游戏过程的情况并力求计算机尽量不败,。,1,2,3,4,5,N-1,N,分析,题设条件:若谁先走到第,N,格谁将获胜,例如,假设,S=1,2,,从第,N,格往前倒推,则走到第,N-1,格或第,N-2,格的一方必败,而走到第,N-3,格者必定获胜,因此在,N,,,S,确定后,棋格中每个方格的胜、负或和态(双方都不能到达第,N,格)都是可以事先确定的。将目标格置为必胜态,由后往前倒推每一格的胜负状态,规定在自己所处的当前格后,若对方无论走到哪儿都必定失败,则当前格为胜态,若走后有任一格为胜格,则当前格为输态,否则为和态。,分析,设,1,表示必胜态,,-1,表示必败态,,0,表示和态或表示无法到达的棋格。,例如,设,N,10,,,S,1,2,,则可确定其每个棋格的状态如下所示:,而,N,10,,,S,2,3,时,其每格的状态将会如下所示:,有了棋格的状态图后,程序应能判断让谁先走,计算机选择必胜策略或双方和(双方均不能到达目标格)的策略下棋,这样就能保证计算机尽可能不败。,1,-1,-1,1,-1,-1,1,-1,-1,1,0,-1,-1,0,1,0,-1,-1,0,1,递推的应用(动态规划中的递推),例题:最小伤害,把儿站在一个,N x N,的方阵中最左上角的格子里。他可以从一个格子走到它右边和下边的格子里。每一个格子都有一个伤害值。他想在受伤害最小的情况下走到方阵的最右下角。,分析,Fij,:设走到,(i,j),这格的最小伤害值,aij,表示,(i,j),这格的伤害值。,Fij=min(fi-1j,fij-1)+aij,边界条件:,f11=a11,fi1=fi-11+ai1(2=i=n),f1i=f1i-1+a1i(2=i=n),在一个,nm,的方格中,,m,为奇数,放置有,nm,个数,如图,方格中间的下方有一人,此人可按照五个方向前进但不能越出方格,见右下图。,人每走过一个方格必须取此方格中的数。要求找到一条从底到顶的路径,使其数相加之和为最大。输出和的最大值。,16,4,3,12,6,0,3,4,-5,6,7,0,0,2,6,0,-1,-2,3,6,8,5,3,4,0,0,-2,7,-1,7,4,0,7,-5,6,0,-1,3,4,12,4,2,人,递推的应用(动态规划中的递推,),例题:方格取数,分析,我们用坐标,(x,y),唯一确定一个点,其中,(m,n),表示图的右上角,而人的出发点是,受人前进方向的限制,能直接到达点,(x,y),的点只有,(x+2,y-1),,,(x+1,y-1),,,(x,y-1),,,(x-1,y-1),,,(x-2,y-1),。到点,(x,y),的路径中和最大的路径必然要从,(m/2,0),到,(x+2,y-1),,,(x+1,y-1),,,(x,y-1),,,(x-1,y-1),,,(x-2,y-1),的几条路径中产生,既然要求最优方案,当然要挑一条和最大的路径,关系式如下:,F,x,y,=MaxF,x+2,y-1,F,x+1,y-1,F,x,y-1,F,x-1,y-1,F,x-2,y-1,+Num,x,y,,,其中,Num,x,y,表示,(x,y),点上的数字。,边界条件为:,动态规划与递推的关系,上题实质上是采用动态规划来求解,那么与递推动态规划之间到底是什么关系呢?,我们不妨画个图,(,如下图,),。而通常人们理解的递推关系就是一般递推关系,故认为动态规划与递推关系是两个各自独立的个体。,动态规划,一般递推关系,递推关系,动态规划与递推的关系,1,、一般递推边界条件很明显,动态规划边界条件比较隐蔽,容易被忽视,2,、一般递推数学性较强,动态规划数学性相对较弱,3,、一般递推一般不划分阶段,动态规划一般有较为明显的阶段,递推进阶,【,例题,1】,位数问题,【,问题描述,】,在所有的,N,位数中,有多少个数中有偶数个数字,3,?由于结果可能很大,你只需要输出这个答案,mod 12345,的值。,【,文件输入,】,读入一个数,N,(,1=N=1000),【,文件输出,】,输出有多少个数中有偶数个数字,3,。,【,样例输入,】,2,【,样例输出,】,73,递推进阶,【,例题,2】,铺磁砖问题,【,问题描述,】,用,1x1,和,2x2,的磁砖不重叠地铺满,Nx3,的地板,问共有多少种不同的方案?,【,文件输入,】,输入一个整数,n,(,1=N=1000,)。,【,文件输出,】,输出方案数,由于结果可能很大,你只需要输出这个答案,mod 12345,的值。,【,样例输入,】2,【,样例输出,】3,递推进阶,【,例题,3】,路程问题,【,问题描述,】,从原点出发,一步只能向右走、向上走或向左走。恰好走,N,步且不经过已走的点共有多少种走法?,【,文件输入,】,输入一个整数,n,(,1=n=1000,)。,【,文件输出,】,输出走法数。由于结果可能很大,你只需要输出这个答案,mod 12345,的值。,【,样例输入,】2,【,样例输出,】7,递推进阶,【,例题,4】,圆周上的弦,【,问题描述,】,圆周上有,N,个点。连接任意多条(可能是,0,条)不相交的弦(共用端点也算相交)共有多少种方案?,【,文件输入,】,输入一个整数,n,(,1=N=1000,)。,【,文件输出,】,输出方案数。由于结果可能很大,你只需要输出这个答案,mod 12345,的值。,【,样例输入,】4,【,样例输出,】9,递推进阶,【,例题,5】,矩形中的树,【,问题描述,】,在网格中取一个,N x 1,的矩形,并把它当作一个无向图。这个图有,2(N+1),个顶点,有,3(N-1)+4,条边。这个图有多少个生成树?,【,文件输入,】,输入一个整数,n,(,1=Nc;,if(c!=!)rever();,coutc;,int main(),rever();,return 0;,【,样例输入,】,gnauh,!,【,样例输出,】,递归的实现,采用递归方法编写的问题解决程序具有结构清晰,可读性强等优点,且递归算法的设计比非递归算法的设计往往要容易一些,所以当问题本身是递归定义的,或者问题所涉及到的数据结构是递归定义的,或者是问题的解决方法是递归形式的时候,往往采用递归算法来解决。,递归的应用,处理递归定义或解决方法为递归方式的问题,解决搜索问题,实现分治思想,用于输出动态规划的中间过程,1,、递归定义问题,树结构是由递归定义的。因此,在解决与树有关的问题时,常常可以采用递归的方法。,2,、解决搜索问题,因为搜索产生的节点成树状结构,所以可以用递归方法解决。这类例子很多,如,“,N,皇后,”,问题,全排列,哈密顿回路,图的可着色性等搜索问题。,例题:全排列,【,问题描述,】,编程列举出,1,、,2,、,、,n,的全排列,要求产生的任一个数字序列中不允许出现重复的数字,【,文件输入,】,输入,n(1=n=9),【,文件输出,】,有,1,到,n,组成的所有不重复数字的序列,每行一个序列,分析,我们假设,n=3,时,如下图:位置,1,可以放置数字,1,、,2,、,3,;位置,2,可以放置数字,1,、,2,、,3,;位置,3,可以放置数字,1,、,2,、,3,,但是当位置,1,放了数字,1,后位置,2,和位置,3,都不能在放,1,,因此画树的约束条件是:各位置的数字不能相同。,分析,我们画,“,解答树,”,时,根结点一般是一个空结点,根结点下面的第,1,、,2,、,3,三层分别对应位置,1,、位置,2,、位置,3,,用,“,”,标示的分支表示该结点不满足约束条件,不能被扩展出来:,void f(int k)/,搜索第,k,层结点(向第,k,个位置放数),int i;,if(k=n+1)for(i=1;i=n;i+)coutai;coutendl;,/,如果搜索到一条路径,则输出一种解,else for(i=1;i=n;i+)/,每一个结点可以分解出,n,个子结点;,if(bi=0)/,如果能生成第,k,层的第,i,个结点;,ak=i;/,第,k,个位置为数字,i,;,bi=1;/,标记数字,i,已用,f(k+1);/,扩展第,k,层的第,i,个结点,(,向第,k+1,个位置放数,),bi=0;/,向上回溯,并恢复数据,我们用递归过程来描述“解答树”的深度优先搜索,3,、实现分治思想,不难发现,在各种时间复杂度为,nlogn,排序方法中,大都采用了递归的形式。因为无论是分治合并排序,还是堆排序、快速排序,都存在有分治的思想。只要分开处理,就可以采用递归。其实进行分治,也是一个建树的过程。,例题:表达式求值,由键盘输入一个算术表达式,该表达式由数字,加,(+),、减,(-),、乘,(*),、求商,(/),运算符及小括号组成。,例如:,6*8+(5-5*(26-1)/2+7),请编写一个程序,计算输入表达式的值。,核心代码,int tree(int left,int right),int tmp,L1,L2,p;,tmp=isnum(left,right);,if(tmp!=-1)return tmp;/,返回值,if(stleft=(),/,去掉最外层的括号,p=findlow(left,right);/,找运算级别最低的运算符,L1=tree(left,p-1);/,递归左子树,L2=tree(p+1,right);/,递归右子树,return cal(L1,stp,L2);,4,、用于输出动态规划的中间过程,动态规划对空间要求较高,若要保存中间过程用于输出,则可能要增加一倍的空间需求。此时,如果采用递归输出,就完全不需要浪费这宝贵的空间。,例题:复制书稿,【,问题描述,】,假设有,m,本书(编号为,1,2,m,),想将每本复制一份,,m,本书的页数可能不同(分别是,p1,p2,pm,)。任务是将这,m,本书分给,k,个抄写员(,k=m,),每本书只能分配给一个抄写员进行复制,而每个抄写员所分配到的书必须是连续顺序的。意思是说,存在一个连续升序数列,0=b0b1,b2,bk-1bk=m,,这样,第,i,号抄写员得到的书稿是从,bi-1+1,到第,bi,本书。复制工作是同时开始进行的,并且每个抄写员复制的速度都是一样的。所以,复制完所有书稿所需时间取决于分配得到最多工作的那个抄写员的复制时间。试找一个最优分配方案,使分配给每一个抄写员的页数的最大值尽可能小(如存在多个最优方案,输出结果排序最小的一种),分析,该题中,m,本书是顺序排列的,,k,个抄写员选择数也是顺序且连续的。不管以书的编号,还是以抄写员标号作为参变量划分阶段,都符合策略的最优化原理和无后效性。考虑到,k=m,,以抄写员编号来划分阶段会方便些。,设,fij,为前,i,个抄写员复制前,j,本书的最小,“,页数最大数,”,。,Sumi=a1+a2+,+ai,,则状态转移方程为:,fij=minmax(fi-1k,Sumj-Sumk)(i-1=k=j-1),dij=k,;记录第,i,个人的最佳位置,边界条件,f1i=Sumi,。,输出方案,则递归输出;,void Print(int i,int j),if(i=1)cout1 jendl;return;,Print(i-1,dij);,coutdij+1 jendl;,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 包罗万象 > 大杂烩

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服