NOIP基础算法综合.ppt

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+; /统计不同重量的个数 coutnumendl;,例题2：火柴棒等式（NOIP2008）,给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示： 注意： 1.加号与等号各自需要两根火柴棍 2.如果AB，则A+B=C与B+A=C视为不同的等式（A、B、C=0） 3.n(n=24)根火柴棍必须全部用上,例题2：火柴棒等式（NOIP2008）,【问题简述】给你n(n=24)根火柴棒,叫你拼出 “A + B = C“这样的等式,求方案数. 【思路点拨】本题主要考查对枚举法的掌握，可以枚举A和B的取值，考查等式是否刚好用了24根火柴棒。1S的时限对枚举的范围有所要求，必须要仔细分析A和B的取值。,例题2：火柴棒等式（NOIP2008）,本题最多24根火柴，等号和加号共用4根火柴，所以A,B,C这3个数字需用20根火柴。我们考查A和B的最大的取值可能：09这10个数字所用的火柴数为6,2,5,5,4,5,6,3,7,6，很明显数字1用的火柴棒最少只要2根，不妨让B为1，那么A和C最多可以使用18根火柴，而C=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; coutsumendl; ,【优化算法】先计算si=si-1+ai cinn; for(i=1;iai;si=si-1+ai; for(i=1;ixy; coutsy-sx-1endl; ,【例题4】最大子矩阵问题,【问题描述】给定一个二维的数组（含正数或负数），请从中找出和最大的子矩阵。例如：,【例题4】最大子矩阵问题,1、“直译”枚举过程 for(x1=1;x1best)best=sum；/调整最优解 这个算法相当粗糙，枚举状态的费用为O(n6),2、从减少重复计算入手 有刚才一维情况可以推广到二维，在统计左上角为(x1,y1)右下角为(x2,y2)内矩形的元素之和时，我们同样可以先初始化，计算出左上角为(1,1)右下角为(x,y)内矩形的元素之和sxy。 for(x1=1;x1mapij; 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(n4),【例题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(n3),【例题4】最大子矩阵问题,核心代码 sum=-0x7fffffff; for(i=1;isum)sum=tk; coutsumendl;,六、局部枚举,例题5：求第一、第二、第三最短路问题,例题6：新年好,重庆城里有n个车站，m条双向公路连接其中的某些车站。每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路上花费的时间等于路径上所有公路需要的时间之和。 佳佳的家在车站1，他有五个亲戚，分别住在车站a,b,c,d,e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？,算法分析,这一题中的边数远小于n2，所以复杂度也只有nlogn+m 算法框架是： （1）用5次最短路，计算出6个点两两之间的距离 （2）枚举5个结点的全排列，找到一个使得总路程长度最短的方案。,第二部分 递推策略,递推的概念与基本思想,给定一个数的序列H0,H1,Hn,若存在整数n0，使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0in)联系起来，这样的式子就叫做递推关系。,解决递推问题的一般步骤,建立递推关系式 确定边界条件 递推求解,递推的形式,顺推法和倒推法,递推的应用分类,一般递推问题 组合计数类问题 一类博弈问题的求解 动态规划问题的递推关系,例题1：faibonacci数列,【问题描述】已知faibonacci数列的前几个数分别为0，1，1，2，3，5，编程求出此数列的第n项。（ n=60）,递推的应用（一般递推问题）,递推的应用（一般递推问题）,【例题2】输出杨辉三角的前N行 【问题描述】输出杨辉三角的前N行(N10)。 【文件输入】输入只有一行，包括1个整数N(N10)。 【文件输出】输出只有N行。 【样例输入】3 【样例输出】 1 1 1 1 2 1,递推的应用（一般递推问题）,例题3 : Hanoi塔问题 . Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上： (1)一次只能移一个圆盘； (2)圆盘只能在三个柱上存放； (3)在移动过程中，不允许大盘压小盘。 问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？,分析,2,1,3,当n=1时：AC 当n=2时：AB,AC,BC 当n=3时：,分析,设hn为n 个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a 柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c 柱；最后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=3。以此类推，当a柱上有n(n=2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。 hn=2hn-1+1 边界条件：h1=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(n2)。,方法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（32-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=1时 边界条件：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;,递推的应用（组合计数）,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=A1×A2×A3××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;你的任务就是对于所给的单词，求出它的编码。,递推的应用（博弈问题）,例题：走直线棋问题。有如下所示的一个编号为到的方格： 现由计算机和人进行人机对奕，从到，每次可以走个方格，其中为集=a1,a2, a3,am中的元素(m=4)，规定谁最先走到第n格为胜，试设计一个人机对奕方案，摸拟整个游戏过程的情况并力求计算机尽量不败。,分析,题设条件：若谁先走到第N格谁将获胜，例如，假设S=1,2，从第N格往前倒推，则走到第N-1格或第N-2格的一方必败，而走到第N-3格者必定获胜，因此在N，S确定后，棋格中每个方格的胜、负或和态（双方都不能到达第N格）都是可以事先确定的。将目标格置为必胜态，由后往前倒推每一格的胜负状态，规定在自己所处的当前格后，若对方无论走到哪儿都必定失败，则当前格为胜态，若走后有任一格为胜格，则当前格为输态，否则为和态。,分析,设1表示必胜态，-1表示必败态，0表示和态或表示无法到达的棋格。 例如，设N10，S1,2，则可确定其每个棋格的状态如下所示： 而N10，S2,3时，其每格的状态将会如下所示： 有了棋格的状态图后，程序应能判断让谁先走，计算机选择必胜策略或双方和（双方均不能到达目标格）的策略下棋，这样就能保证计算机尽可能不败。,递推的应用（动态规划中的递推）,例题：最小伤害 把儿站在一个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),在一个n×m的方格中，m为奇数，放置有n×m个数 ，如图,方格中间的下方有一人，此人可按照五个方向前进但不能越出方格,见右下图。 人每走过一个方格必须取此方格中的数。要求找到一条从底到顶的路径，使其数相加之和为最大。输出和的最大值。,递推的应用（动态规划中的递推),例题：方格取数,分析,我们用坐标(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)的几条路径中产生，既然要求最优方案，当然要挑一条和最大的路径，关系式如下： Fx,y= MaxFx+2,y-1 ,Fx+1,y-1,Fx,y-1,Fx-1,y-1,Fx-2,y-1+Numx,y， 其中Numx,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=N=1000）。 【文件输出】输出这个图有多少个生成树？由于结果可能很大，你只需要输出这个答案mod 12345的值。 【样例输入】1 【样例输出】4,第三部分 递归策略,递归的概念与基本思想,一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。,递归的实现方法,递归是借助于一个递归工作栈来实现；递归=递推+回归； 1.递推：问题向一极推进,这一过程叫做递推；这一过程相当于压栈。 2.回归：问题逐一解决，最后回到原问题，这一过程叫做回归。这一过程相当于弹栈。,用递归算法求 n! 定义：函数 fact(n)=n! fact(n-1)=(n-1)! 则有 fact(n)=n*fact(n-1) 已知 fact(1)=1,74,下面画出了调用和返回的递归示意图,递归的实现,递归实现的代价是巨大的栈空间的耗费，那是因为过程每向前递推一次，程序将本层的实在变量（值参和变参）、局部变量构成一个“工作记录”压入工作栈的栈顶，只有退出该层递归时，才将这一工作记录从栈顶弹出释放部分空间。由此可以想到，减少每个“工作记录”的大小便可节省部分空间。例如某些变参可以转换为全局变量，某些值参可以省略以及过程内部的精简。,【例题】写出结果 void rever() char c; cinc; 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='(') ,4、用于输出动态规划的中间过程,动态规划对空间要求较高，若要保存中间过程用于输出，则可能要增加一倍的空间需求。此时，如果采用递归输出，就完全不需要浪费这宝贵的空间。,例题：复制书稿,【问题描述】假设有m本书（编号为1,2,m），想将每本复制一份，m本书的页数可能不同（分别是p1,p2,pm）。任务是将这m本书分给k个抄写员（k=m），每本书只能分配给一个抄写员进行复制，而每个抄写员所分配到的书必须是连续顺序的。 意思是说，存在一个连续升序数列 0=b0b1 b2bk-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; ,