NOIP基础算法综合--枚举、递推和递归1

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,NOIP,基础算法综合,巴蜀中学 黄新军,第一节 枚举算法,一、枚举法的基本思想,根据实际问题设计多重循环，,一一,枚举所有可能的状态，并用问题给定的约束条件检验哪些状态是需要的，哪些状态是不需要的。能使命题成立的状态，即为其解。,虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法或宽度优先搜索有所不同。,二、枚举法的条件,:,可预先确定每个状态的元素个数,n,。如百钱买百鸡问题，,3,文钱一只鸡的状态元素个数可预先确定；,可预先确定每个状态元素,a1,a2,an,的值域，即枚举的范围。,三、枚举法的框架结构,设,a,11,为状态元素,a,i,的最小值；,a,ik,为状态元素,a,i,的最大值,(1=i=n),即状态元素,a,1,a,2,a,n,的值域分别为,a,11,=a,1,=a,1k,a,21,=a,2,=a,2k,a,i1,=,a,i,=,a,ik,a,n1,=a,n,=,a,nk,。,for a,1,:=a,11,to a,1k,do,for a,2,:=a,21,to a,2k,do,.,for a,i,:=a,i1,to a,ik,do,.,for a,n,:=a,n1,to a,nk,do,if,状态,(a1,.,ai.,an),满足检验条件,then,输出问题的解,;,四、枚举法的优缺点,枚举法的优点：,由于枚举算法一般是现实问题的“直译”，且是建立在考察大量状态、甚至是穷举所有状态的基础之上的，因此比较直观，易于理解，其算法的正确性也比较容易证明。,枚举法的缺点：,枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。,例题,1,：砝码称重,(noip2005),【,问题描述,】,设有,1g,、,2g,、,3g,、,5g,、,10g,、,20g,的砝码各若干枚（其总重,=1000,），求用这些砝码能称出不同的重量个数。,【,文件输入,】,输入,1g,、,2g,、,3g,、,5g,、,10g,、,20g,的砝码个数。,【,文件输出,】,输出能称出不同重量的个数。,【,样例输入,】,1 1 0 0 0 0,【,样例输出,】3,【,分析,】,根据输入的砝码信息，每种砝码可用的最大个数是确定的，而且每种砝码的个数是连续的，能取,0,到最大个数，所以符合枚举法的两个条件，可以使用枚举法。枚举时，重量可以由,1g,2g,20g,砝码中的任何一个或者多个构成，枚举对象可以确定为,6,种重量的砝码，范围为每种砝码的个数。判定时，只需判断这次得到的重量是新得到的，还是前一次已经得到的，即判重。由于重量,=0,）,3.n(n=24),根火柴棍必须全部用上,例题,2,：火柴棒等式（,NOIP2008,）,【,问题简述,】,给你,n(n,=A,，满足条件的,A,的最大取值为,1111,。所以枚举,A,和,B,的范围是从,01111,。,为了加快速度，可以将,0,到,2222,的所有整数需要的火柴棒数目提前算好保存在数组中。,五、,枚举算法的优化,枚举算法的时间复杂度：状态总数*单个状态的耗时,主要优化方法：, 减少状态总数, 降低单个状态的考察代价,优化过程从以下几个方面考虑：, 枚举对象的选取, 枚举方法的确定,采用局部枚举或引进其他算法,【,例题,3】,给你,n,个整数，然后要有,m,个询问。问第,i,个数字到第,j,个数字所有数字之和。,【,朴素算法,】,readln(n);,for i:=1 to n do read(ai);,for i:=1 to m do,begin,read(x,y);,sum:=0;,for j:=x to y do sum:=sum+aj;,writeln(sum,);,end;,时间复杂度为：,O(nm,),【,优化算法,】,先递推计算出,si,=si-1+ai,readln(n,);,for i:=1 to n do,begin,read(ai);si,:=si-1+ai;end;,for i:=1 to m do,begin,read(x,y,);,writeln(sy-sx-1);,end;,【,例题,4】,最大子矩阵问题,【,问题描述,】,给定一个二维的数组（含正数或负数），请从中找出和最大的子矩阵。例如：,1,、“直译”枚举过程,For x1:=1 to n do/,枚举矩形左上角,(x1,y1),for y1:=1 to n do,for x2:=1 to n do/,枚举矩形右下角,(x2,y2),for y2:=1 to n do,/,考察状态左上角为,(x1,y1),右下角为,(x2,y2),内矩形的元素之和；,begin,sum:=0,；,for x:=x1 to x2 do/,计算当前矩形内元素的和,for y:=y1 to y2 do sum:=,sum+ax,y,；,if sumbest then best:=sum,；,/,调整最优解,end;,这个算法相当粗糙，枚举状态的费用为,O(n,6,),2,、从减少重复计算入手,有刚才一维情况可以推广到二维，在统计左上角为,(x1,y1),右下角为,(x2,y2),内矩形的元素之和时，我们同样可以先初始化，计算出左上角为,(1,1),，右下角为,(,x,y,),内矩形的元素之和,sxy,。,for i:=1 to n do /,枚举矩形右下角，求和,for j:=1 to n do,begin,read(ai,j,);,si,j,:=si-1,j+si,j-1-si-1,j-1+ai,j;,end;,对于状态左上角为,(x1,y1),右下角为,(x2,y2),内矩形的元素之和，可以改为：,sum:=sx2,y2-sx1-1,y2-sx2,y1-1+sx1-1,y1-1;,if sumbest then best:=sum,；,/,调整最优解,由于先进行了,预处理,，整个算法的时间复杂度降为,O(n,4,),3,、提取恰当的信息,容易观察到，最大子矩阵问题是最大连续子序列和问题的提升，即将一条线换成一个面，将一维问题提升到二维问题。所以我们计算最大子矩阵的方法就是将一行行的数进行累加以求得最大值。,但是还有一个问题，那就是应该如何高效地存储矩阵？,我们可以想到：在一个一维的数列中，设数组,bi,表示从第,1,个元素到第,i,个元素的和，则如果想要求第,i,个元素到第,j,个元素的和，只需要计算,bj-bi-1,的值就行了。由此推广到二维矩阵，设,bi,j,表示矩阵第,j,列前,i,个元素的和，,ai,j,表示元素数据，则压缩存储：,for i:=1 to n do,for j:=1 to n do,begin,read(ai,j);bi,j,:=bi-1,j+ai,j;,因此，我们可以使用三重循环求出所有的矩形值，即枚举起始行,i,和终止行,j,，压缩子矩形成为一行，变成一维求最大字段和问题。,即,tk,=max(tk-1,0)+bj,k-bi-1,k;,时间复杂度为,O(n,3,),核心代码,sum:=-99999999; /,置初值,for i:=1 to n do /,阶段,:,起始行,begin,for j:=i to n do /,状态,:,结束行,begin,t1:=bj,1-bi-1,1; /,初始化第,1,列的值,for k:=2 to n do /,决策,:,第几列,begin,if tk-10 then,tk,:=tk-1+bj,k-bi-1,k;,else,tk,:=bj,k-bi-1,k;,if,tk,sum,sum,:=,tk,;,end;,end;,end;,writeln(sum);,六、局部枚举,例题,5,：求第一、第二、第三最短路问题,例题,6,：新年好,重庆城里有,n,个车站，,m,条双向公路连接其中的某些车站。每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路上花费的时间等于路径上所有公路需要的时间之和。,佳佳的家在车站,1,，他有五个亲戚，分别住在车站,a,b,c,d,e,。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？,数据范围：,n(n,=50,000),m(mn,0,时,可以用等号,(,或大于号、小于号,),将,H,n,与其前面的某些项,H,i,(0in),联系起来，这样的式子就叫做递推关系。,如,Fibonacci,数列：,fi,=fi-1+fi-2,二、解决递推问题的一般步骤,建立递推关系式,确定边界条件,递推求解,三、递推的两种形式,顺推法和倒推法,四、递推的应用分类,一般递推问题,组合计数类问题,一类博弈问题的求解,动态规划问题的递推关系,例题,1,：,faibonacci,数列,【,问题描述,】,已知,faibonacci,数列的前几个数分别为,0,，,1,，,1,，,2,，,3,，,5,，,编程求出此数列的第,n,项。（,n=60,）,递推的应用（一般递推问题）,思考：当,n=10,9,时，如何求解,递推的应用（一般递推问题）,例题,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 =2,n,-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),=s(x-1)+h(x),=s(x-1)+s(x/2),h(x)=s(x)-s(x-1)=s(x/2),此算法的时间复杂度可降到,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,普及）,【,问题描述,】,上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。 游戏规则是这样的：,n,（,3=n=30,）个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目。 聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了,m,（,3=m2-3-1,和,1-3-2-1,，共两种。,分析,设,fi,k,表示经过,k,次传到编号为,i,的人手中的方案数，传到,i,号同学的球只能来自于,i,的左边一个同学和右边一个同学，这两个同学的编号分别是,i-1,和,i+1,，所以可以得到以下的递推公式：,fi,k,=fi-1,k-1+fi+1,k-1,f1,k=fn,k-1+f2,k-1,当,i=1,时,fn,k,=fn-1,k-1+f1,k-1,当,i=1,时,边界条件：,f1,0=1,；,answer=f1,m,参考代码,readln(n,m,);,f1,0:=1;,for k:=1 to m do,begin,f1,k:=f2,k-1+fn,k-1;,for i:=2 to n-1 do,fi,k,:=fi-1,k-1+fi+1,k-1;,fn,k,:=fn-1,k-1+f1,k-1;,end;,writeln(f1,m);,递推的应用（组合计数）,Catalan,数,例题,7,：,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,),。,Catalan,数的应用（部分和序列）,例题,8,：,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,）,例题,9,：一个栈,(,无穷大,),的进栈序列为,1,2,3,.n,，有多少个不同的出栈序列？,Catalan,数的应用（加括号）,例题,10,：,P=A1A2A3An,，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？,【,分析,】,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),。,递推的应用（组合计数）,例题,11,：错排问题（经典问题）,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),个错位排列。,根据加法原理，我们得到求,错位排列的递推公式,f(k,):,f(k,)=(k-1)*(,f(k,1)+f(k,2),分析,递推的应用（组合计数）,例题,12,：编码问题,【,问题描述,】,编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数字。字母表中共有,26,个小写字母,a,b,c,.,z,。这些特殊的单词长度不超过,6,且字母按照升序排列。把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就对应着它在字典中的位置，例如：,a-1;b-2;z-26;ab-27;ac-28;,你的任务就是对于所给的单词，求出它的编码。,递推的应用（博弈问题）,例题,13,：走直线棋问题。,有如下所示的一个编号为到的方格：,现由计算机和人进行人机对奕，从到，每次可以走个方格，其中为集,=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,递推的应用（动态规划中的递推）,例题,14,：最小伤害,把儿站在一个,N x N,的方阵中最左上角的格子里。他可以从一个格子走到它右边和下边的格子里。每一个格子都有一个伤害值。他想在受伤害最小的情况下走到方阵的最右下角。,分析,Fi,j,：设走到,(,i,j,),这格的最小伤害值,aij,表示,(,i,j,),这格的伤害值。,Fi,j,=min(fi-1,j,fi,j-1)+ai,j,边界条件：,f1,1=a1,1,fi,1=fi-1,1+ai,1(2=i=n),f1,i=f1,i-1+a1,i(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,人,递推的应用（动态规划中的递推,),例题,15,：方格取数,分析,我们用坐标,(,x,y,),唯一确定一个点，其中,(,n,m,),表示图的右上角，而人的出发点是，受人前进方向的限制，能直接到达点,(,x,y,),的点只有,(x-1,y+2),，,(x-1,y+1),，,(x-1,y),，,(x-1,y-1),，,(x-1,y-2),。到点,(,x,y,),的路径中和最大的路径必然要从,(0,m/2),到,(x-1,y+2),，,(x-1,y+1),，,(x-1,y),，,(x-1,y-1),，,(x-1,y-2),的几条路径中产生，既然要求最优方案，当然要挑一条和最大的路径，关系式如下：,Fx,y,=maxFx-1,y+2,Fx-1,y+1,Fx-1,y,Fx-1,y-1,Fx-1,y-2+ax,y,其中,ax,y,表示,(,x,y,),点上的数字。,边界条件为：,F0,m/2=0,F0,x=-,(1=xmax then max:=j;,end;,end;,起始状态就是调用,findmax(1,max),而像上述过程中的变参,max,完全可以省略。将上述方法修改可得下面的算法：,Procedure,findmax(i:integer,);,begin,if i=n then exit,else begin,findmax(i+1);,if,ai,max then max:=,ai,;,end;,end;,起始状态就是调用,findmax(1),，,max,为全局变量，同时还减少了一个局部变量的使用。尽管这只是一个很简单的例子，在本例中不做精简，程序也还是能通过，但它精简的原则对其它使用递归的程序而言却是同样适用的。特别是在递归过程出现堆栈溢出情况时就应该考虑这一问题。,四、递归的优点与缺点,采用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。,五、递归的应用,处理递归定义或解决方法为递归方式的问题,解决搜索问题,实现分治思想,用于输出动态规划的中间过程,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,，用“”标示的分支表示该结点不满足约束条件，不能被扩展出来：,procedure,f(k:integer,) /,搜索第,k,层结点（向第,k,个位置放数）,begin,var,i:integer,;,if k=n+1 then begin for i:=1 to n do,write(ai);writeln;end,/,如果搜索到一条路径，则输出一种解,else for i:=1 to n do/,每一个结点可以分解出,n,个子结点；,if,bi,=0 then /,如果能生成第,k,层的第,i,个结点；,begin,ak,:=i; /,第,k,个位置为数字,i,；,bi,:=1; /,标记数字,i,已用,f(k+1);,/,扩展第,k,层的第,i,个结点,(,向第,k+1,个位置放数,),bi,:=0; /,向上回溯，并恢复数据,end;,end;,我们用递归过程来描述 “解答树”的深度优先搜索,3,、实现分治思想,不难发现，在各种时间复杂度为,nlogn,排序方法中，大都采用了递归的形式。因为无论是分治合并排序，还是堆排序、快速排序，都存在有分治的思想。只要分开处理，就可以采用递归。其实进行分治，也是一个建树的过程。,例题：表达式求值,由键盘输入一个算术表达式，该表达式由数字，加,(+),、减,(-),、乘,(*),、求商,(/),运算符及小括号组成。,例如：,6*(8-1)+(5-(12-7)/5)/2,请编写一个程序，计算输入表达式的值。,funtion,tree(left,right:integer):integer,;,begin,var,tmp,L1,L2,p:integer;,tmp,:=,isnum(left,right,);,if,tmp,-1 begin tree:=,tmp;exit;end,;/,返回值,if (,stleft,=()and (,poskh(left,right,)=right) then,tree:=tree(left+1,right-1);,/,去掉最外层的括号,p:=,findlow(left,right,); /,找运算级别最低的运算符,L1:=tree(left,p-1); /,递归左子树,L2:=tree(p+1,right); /,递归右子树,tree:=cal(L1,stp,L2);,end;,4,、用于输出动态规划的中间过程,例题：复制书稿,【,问题描述,】,假设有,m,本书（编号为,1,2,m,），想将每本复制一份，,m,本书的页数可能不同（分别是,p1,p2,pm,）。任务是将这,m,本书分给,k,个抄写员（,k=m,），每本书只能分配给一个抄写员进行复制，而每个抄写员所分配到的书必须是连续顺序的。 复制工作是同时开始进行的，并且每个抄写员复制的速度都是一样的。所以，复制完所有书稿所需时间取决于分配得到最多工作的那个抄写员的复制时间。,试找一个最优分配方案，使分配给每一个抄写员的页数的最大值尽可能小（如存在多个最优方案，输出结果排序最小的一种）。,分析,该题中,m,本书是顺序排列的，,k,个抄写员选择数也是顺序且连续的。不管以书的编号，还是以抄写员标号作为参变量划分阶段，都符合策略的最优化原理和无后效性。考虑到,k=m,，以抄写员编号来划分阶段会方便些。,设,fi,j,为前,i,个抄写员复制前,j,本书的最小“页数最大数”。,Si,=a1+a2+,ai,，则状态转移方程为：,fi,j=minmax(fi-1,k,Sj-Sk)(i-1=k=j-1),di,j=k,；记录第,i,个人的最佳位置,边界条件,f1,i=,Si,。,输出方案，则递归输出；,procedure,Print(i,j:integer,),begin,if i=1 begin writeln(1, ,j);exit;end;,Print(i-1,di,j);,writeln(di,j+1, ,j);,end,第四部分,归纳策略,归纳法的基本思想,归纳法的基本思想,是通过列举少量的特殊情况，经过分析，最后找出一般的关系,。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径。,归纳法解题,的过程,细心的观察；,丰富的联想；,继续尝试；,总结归纳出结论。,归纳法解题,的过程,归纳是,一,种抽象，即从特殊现象中找出一般关系。由于在归纳的过程中不可能对所有的可能情况进行枚举，因而最后得到的结论还只是一种猜测,(,即归纳假设,),。所以，严格说来对于归纳假设还必须加以严格的证明。,归纳策略解题应注意的问题：,从问题的简单具体状态分析入手，目的是去寻求可以推广的一般性规律，因此应考虑简单状态与一般性状态之间的联系。,从简单状态中分析出来的规律特征应能够被验证是正确的，不能想当然或任意地提出猜想，否则归纳出来的结论是错误的，必然导致整个问题的解是错解。,归纳策略的应用,例题,1,：,求前,n,个自然数的平方之和：,S=1,2,+2,2,+3,2,+,+n,2,【,分析,】,这本是一道很简单的题目，但如果能找出,S,值与,n,的关系，则此题将更进一步得到简化，由数学证明得知：,(1,2,+2,2,+3,2,+,+n,2,)/(1+2+3+,+n) =(2n+1)/3,又由于,1+2+3+,+n=n(n+1)/2,，因此得到：,1,2,+2,2,+3,2,+,+n,2,=n(n+1) (2n+1)/6,但这只是通过总结归纳而得到的一种猜测，是否正确还需证明，对归纳假设的证明通常采用数学归纳法（证略）。,例题,2,：若干个正整数之和为,n,，其中：,n2000,，试求它们乘积的最大值以及该最大值的位数,k,。,【,分析,】,根据数学规律可知,若要使和固定的数的乘积最大，必须使这些数尽可能的多为,3,，于是可推得以下规律：,当,N mod 3,1,时，,N,可分解为一个,4,和若干个,3,的和；,当,N mod 3,2,时，,N,可分解为一个,2,和若干个,3,的和；,当,N mod 3,0,时，,N,直接分解为若干个,3,的和。,按照这一分解方法，所有因数的乘积必定最大。,注意,：因,N,的最大值可达,2000,，乘积将超过长整型数据范围，所以需用高精度运算。,例题,3,：极值问题,已知,m,、,n,为整数，且满足下列两个条件：,m,、,n1,，,2,，,，,K,，（,1K10,9,）,(n,2,mn,m,2,),2,1,编一程序，由键盘输入,K,，求一组满足上述两个条件的,m,、,n,，并且使,m,2,n,2,的值最大。例如，若,K,1995,，则,m,987,，,n,1597,，则,m,、,n,满足条件，且可使,m,2,n,2,的值最大。,【,分析,】,分析小数据会发现：,m,n,是,Fibonacci,数列的相邻两项。,因为：,(n,2,-mn-m,2,),2,=1,故：,(m,2,+mn-n,2,),2,=1,又：,m,2,+mn-n,2,=(m+n),2,-mn-2n,2,=(m+n),2,-(m+n)n-n,2,故：,(m,2,+mn-n,2,),2,=(m+n),2,-(m+n)n-n,2,2,即：,(n,2,-mn-m,2,),2,=(m+n),2,-(m+n)n-n,2,2,【,分析,】,由上述数学变换式可以得出，如果,m,和,n,为一组满足条件和条件的解，设,n,=,m+n,，,m,=n,那么,n,，,m,也是一组满足条件和条件的一组解。,将所有满足条件和条件的,m,和,n,按递增顺序排成一个,Fibomacci,数列 ,1,，,1,，,2,，,3,，,5,，,8,，,数列中小于,k,的最大两个相邻数即为试题所要求的一组,m,和,n,。,算法,：,利用,Fibomacci,数列顺推,m,n,，求出在条件范围内的,m,n,最大值，此时,m,2,n,2,的值最大。,递推进阶,例题,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=N=1000,）。,【,文件输出,】,输出这个图有多少个生成树？由于结果可能很大，你只需要输出这个答案,mod 12345,的值。,【,样例输入,】1,【,样例输出,】4,