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

《NOIP基础算法综合枚举递推和递归1》由会员分享，可在线阅读，更多相关《NOIP基础算法综合枚举递推和递归1（106页珍藏版）》请在金锄头文库上搜索。

1、NOIP基础算法综合巴蜀中学黄新军2021/8/141第一节第一节 枚举算法枚举算法2021/8/142一、枚举法的基本思想根据实际问题设计多重循环，一一一一枚举所有可能的状态，并用问题给定的约束条件检验哪些状态是需要的，哪些状态是不需要的。能使命题成立的状态，即为其解。虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法或宽度优先搜索有所不同。2021/8/143二、枚举法的条件:可预先确定每个状态的元素个数n。如百钱买百鸡问题，3文钱一只鸡的状态元素个数可预先确定；可预先确定每个状态元素a1,a2,an的值域，即枚举的范围。2021/8/144三、枚举法的框架结构三、枚举法的框架结构设a1

2、1为状态元素ai的最小值；aik为状态元素ai的最大值(1=i=n),即状态元素a1,a2,an的值域分别为a11=a1=a1k,a21=a2=a2k,ai1=ai=aik,an1=an=ank。 for a1:=a11 to a1k do for a2:=a21 to a2k do . for ai:=ai1 to aik do . for an:=an1 to ank do if 状态状态(a1,.,ai.,an)满足检验条件满足检验条件 then 输出问题的解输出问题的解;2021/8/145四、枚举法的优缺点枚举法的优点：枚举法的优点：由于枚举算法一般是现实问题的“直译”，且是建立在考

3、察大量状态、甚至是穷举所有状态的基础之上的，因此比较直观，易于理解，其算法的正确性也比较容易证明。枚举法的缺点：枚举法的缺点：枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。2021/8/146例题例题1：砝码称重：砝码称重(noip2005) 【问题描述问题描述】设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重=1000），求用这些砝码能称出不同的重量个数。【文件输入文件输入】输入1g、2g、3g、5g、10g、20g的砝码个数。【文件输出文件输出】输出能称出不同重量的个数。【样例输入样例输入】110000【样例输出样例输出】32021/8/147

4、【分析分析】根据输入的砝码信息，每种砝码可用的最大个数是确定的，而且每种砝码的个数是连续的，能取0到最大个数，所以符合枚举法的两个条件，可以使用枚举法。枚举时，重量可以由1g,2g, 20g砝码中的任何一个或者多个构成，枚举对象可以确定为6种重量的砝码，范围为每种砝码的个数。判定时，只需判断这次得到的重量是新得到的，还是前一次已经得到的，即判重。由于重量=0）3.n(n=24)根火柴棍必须全部用上2021/8/1410例题例题2：火柴棒等式（：火柴棒等式（NOIP2008） 【问题简述问题简述】给你n(n=A，满足条件的A的最大取值为1111。所以枚举A和B的范围是从01111。为了加快速度，

5、可以将为了加快速度，可以将0到到2222的所有整数需要的所有整数需要的火柴棒数目提前算好保存在数组中。的火柴棒数目提前算好保存在数组中。2021/8/1412五、枚举算法的优化枚举算法的优化枚举算法的时间复杂度：状态总数枚举算法的时间复杂度：状态总数*单个状态的耗时单个状态的耗时主要优化方法：主要优化方法： 减少状态总数减少状态总数 降低单个状态的考察代价降低单个状态的考察代价优化过程从以下几个方面考虑：优化过程从以下几个方面考虑： 枚举对象的选取枚举对象的选取 枚举方法的确定枚举方法的确定 采用局部枚举或引进其他算法采用局部枚举或引进其他算法2021/8/1413【例题例题3】给你给你n个整

6、数，然后要有个整数，然后要有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)2021/8/1414【优化算法优化算法】先递推计算出先递推计算出si=si-1+ai readln(n); for i:=1 to n do begin read(

7、ai);si:=si-1+ai;end; for i:=1 to m do begin read(x,y); writeln(sy-sx-1); end;2021/8/1415【例题例题4】最大子矩阵问题最大子矩阵问题【问题描述问题描述】给定一个二维的数组（含正数或负数），请从中找出和最大的子矩阵。例如：2021/8/14161 1 1 1、“直译直译直译直译”枚举过程枚举过程枚举过程枚举过程For x1:=1 to n do/枚举矩形左上角枚举矩形左上角(x1,y1) for y1:=1 to n do for x2:=1 to n do/枚举矩形右下角枚举矩形右下角(x2,y2) for

8、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(n6)2021/8/14172 2、从减少重复计算入手、从减少重复计算入手 有刚才一维情况可以推广到二维，在统计左上角为

9、有刚才一维情况可以推广到二维，在统计左上角为(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)内矩形的元素之

10、和，可内矩形的元素之和，可以改为：以改为： sum:=sx2,y2-sx1-1,y2-sx2,y1-1+sx1-1,y1-1; if sumbest then best:=sum； /调整最优解调整最优解由于先进行了由于先进行了预处理预处理预处理预处理，整个算法的时间复杂度降为，整个算法的时间复杂度降为O(n4)2021/8/14183、提取恰当的信息、提取恰当的信息 容易观察到，最大子矩阵问题是最大连续子序列和问题的提升，即将一条线换成一个面，将一维问题提升到二维问题。所以我们计算最大子矩阵的方法就是将一行行的数进行累加以求得最大值。 但是还有一个问题，那就是应该如何高效地存储矩阵？ 我们可

11、以想到：在一个一维的数列中，设数组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(n3)2021/8/14

12、19核心代码核心代码 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 tksum sum:=tk; end; end; end; writeln(sum);2021/8/1420六、局部枚举六、

13、局部枚举例题例题5：求第一、第二、第三最短路问题：求第一、第二、第三最短路问题2021/8/1421例题例题6：新年好：新年好重庆城里有重庆城里有n个车站，个车站，m条双向公路连接其中的某些车站。条双向公路连接其中的某些车站。每两个车站最多用一条公路直接相连，从任何一个车站出每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其他车站，但不同的路发都可以经过一条或多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路上花费的时间等于径需要花费的时间可能不同。在一条路上花费的时间等于路径上所有公路需要的时间之和。路径上所有公路需要的时间之和。佳佳的家在车站

14、佳佳的家在车站1，他有五个亲戚，分别住在车站，他有五个亲戚，分别住在车站a,b,c,d,e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时意），给他们送去节日的祝福。怎样走，才需要最少的时间？间？数据范围：数据范围：n(n=50,000),m(mn0时时,可以用等号可以用等号(或大或大于号、小于号于号、小于号)将将Hn与其前面的某些项与其前面的某些项Hi(0in)联系起来，这样的式子就叫做联系起来，这样的式子就叫做递推关系。递推关系。u如如Fibonacci数列：数列：fi=fi-1+fi-

15、22021/8/1425二、解决递推问题的一般步骤二、解决递推问题的一般步骤 n建立递推关系式建立递推关系式n确定边界条件确定边界条件n递推求解递推求解2021/8/1426三、递推的两种形式三、递推的两种形式l顺推法和倒推法顺推法和倒推法2021/8/1427四、递推的应用分类四、递推的应用分类 l 一般递推问题一般递推问题l 组合计数类问题组合计数类问题l 一类博弈问题的求解一类博弈问题的求解l 动态规划问题的递推关系动态规划问题的递推关系2021/8/1428例题例题1：faibonacci数列数列【问题描述问题描述】已知faibonacci数列的前几个数分别为0，1，1，2，3，5，编

16、程求出此数列的第n项。（n=60）递推的应用（一般递推问题）递推的应用（一般递推问题）思考：当思考：当n=10n=109 9时，如何求解时，如何求解2021/8/1429递推的应用（一般递推问题）递推的应用（一般递推问题） 例题例题2：输出杨辉三角的前：输出杨辉三角的前N行行【问题描述问题描述】输出杨辉三角的前N行(N10)。【文件输入文件输入】输入只有一行，包括1个整数N(N=2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。hn=2hn-1+1 =2n-1边界

17、条件：h1=12021/8/1433思考：思考： Hanoi双塔问题双塔问题 2021/8/1434递推的应用（一般递推问题）递推的应用（一般递推问题） 例题例题4:数的计数数的计数 【问题描述问题描述】我们要求找出具有下列性质数的个数我们要求找出具有下列性质数的个数(包含输入的自然数包含输入的自然数n)，先输入一个自然数，先输入一个自然数n(n1000)，然后对此自然数按照如下方法进行处，然后对此自然数按照如下方法进行处理：理： l.不作任何处理；不作任何处理； 2.在它的左边加上一个自然数，但该自然数不能在它的左边加上一个自然数，但该自然数不能超过原数的一半；超过原数的一半； 3.加上数后

18、，继续按此规则进行处理，直到不能加上数后，继续按此规则进行处理，直到不能再而再而 自然数为止；自然数为止；2021/8/1435方法方法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)。2021/8/1436方法方法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)此算法的时

19、间复杂度可降到O(n)。2021/8/1437方法方法3：还是用递推：还是用递推。只要做仔细分析，其实我们还可以得到以下的递推公式：(1)当i为奇数时,h(i)=h(i-1);(2)当i为偶数时,h(i)=h(i-1)+h(i/2);2021/8/1438【思考思考】1.若若n=10000怎么计算；怎么计算； 2.若若n=3000000怎么计算；怎么计算；2021/8/1439递推的应用（一般递推问题）递推的应用（一般递推问题）例题例题5：猴子吃桃问题：猴子吃桃问题1538猴子吃桃问题。猴子摘了一堆桃，第一天吃了一猴子吃桃问题。猴子摘了一堆桃，第一天吃了一半，还嫌不过瘾，又吃了一个；第二天又吃

20、了剩半，还嫌不过瘾，又吃了一个；第二天又吃了剩下的一半零一个；以后每天如此。到第下的一半零一个；以后每天如此。到第n天，猴子天，猴子一看只剩下一个了。问最初有多少个桃子？一看只剩下一个了。问最初有多少个桃子？2021/8/1440【扩展练习扩展练习】猴子分桃猴子分桃 【问题描述问题描述】有一堆桃子和N只猴子，第一只猴子将桃子平均分成了M堆后，还剩了1个，它吃了剩下的一个，并拿走一堆。后面的猴子也和第1只进行了同样的做法，请问N只猴子进行了同样做法后这一堆桃子至少还剩了多少个桃子(假设剩下的每堆中至少有一个桃子)？而最初时的那堆桃子至少有多少个？ 【文件输入文件输入】输入包含二个数据，数据间用空

21、格隔开。第一个数据为猴子的只数N(1N10)，第二个数据为桃子分成的堆数M(2M7)。 【文件输出文件输出】输出包含两行数据，第一行数据为剩下的桃子数，第二行数据为原来的桃子数。 【样例输入样例输入】32 【样例输出样例输出】 1152021/8/1441递推的应用（一般递推问题）递推的应用（一般递推问题）【例题例题6】传球游戏（传球游戏（NOIP2008普及）普及）【问题描述问题描述】上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。游戏规则是这样的：n（3=n=30）个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以

22、把球传给自己左右的两个同学中的一个（左右任意），当老师再吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目。聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m（3=m2-3-1和1-3-2-1，共两种。2021/8/1442分析设fi,k表示经过k次传到编号为i的人手中的方案数，传到i号同学的球只能来自于i的左边一个同学和右边一个同学，这两个同学的编号分别是i-1和i+1，所以可以得到以下的递推公式：fi,k=fi-1,k-1+fi+1,k-1f1,k=fn,k-1+f2,k-1,当i=1时fn,k=fn-1,k-1+f1,k

23、-1,当i=1时边界条件：f1,0=1；answer=f1,m2021/8/1443参考代码 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);2021/8/1444递推的应用（组合计数）递推的应用（组合计数）Catalan数例题7：Cn=n+2条边的多边形，能被分割成三角形的方案数，例如5边形的分割方案有：2021/8/1445 分析：分析：

24、分析：分析：如图有一个n+2边形。任取一边，从这边的端点开始，依次给顶点编号为：0,1,2,3,.,n,n+1(所取的边端点编号为:0,n+1)。这样，除线段所在顶点外，还有n个顶点：1,2,3,n。我们以该线段为三角形的一条边，另一个顶点为i(1=i=n)。2021/8/1446我们设题意要求的三角形剖分方案数为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为一剖分三角形的剖分数应为：

25、H(i-1)*H(n-i)，i=1,2,n，所得的剖分各不相同，根据加法原理则有：这与Catalan数C(n)的表达式是一致的。故本题答案为H(n)=C(n)。2021/8/1447Catalan数的应用（部分和序列）例题例题8 8：n个1和n个0组成2n位的二进制，要求从左到右扫描，1的累计数不小于0的累计数，试求满足这条件的数有多少？ 【类似1】将n个1和n个-1排成一行，要求第1个数至第k个数的累加和均非负，问有几种排列方法？【类似2】有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少种方法使得只要有10元的人买票，售票

26、处就有5元的钞票找零？2021/8/1448Catalan数的应用（栈NOIp2003）例题9：一个栈(无穷大)的进栈序列为1,2,3,.n，有多少个不同的出栈序列？2021/8/1449Catalan数的应用（加括号）例题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(

27、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)。2021/8/1450递推的应用（组合计数）例题11：错排问题（经典问题）n个数，分别为1n，排成一个长度为n的排列。若每一个数的位置都与数的本身不相等，则称这个排列是一个错排。例如，n=3，则错排有231、312。编写程序，求n的错排个数2

28、021/8/1451分析我们设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)它们有什么规律呢？2021/8/1452通过反复的试验，我们发现事实上有两种方式产生错位排列：A.将k与(1，2，k-1)的某一个数互换，其他k-2个数进行错排，这样可以得到(k-1)f(k-2)(k-1)f(k-2)个错位排列。B.另一部分是将前k-1个元素的每一个错位排列（有f(k-1)个）中

29、的每一个数与k互换，这样可以得到剩下的(k-(k-1)f(k-1)1)f(k-1) 个错位排列。根据加法原理，我们得到求错位排列的递推公式f(k):f(k)=(k-1)*(f(k1)+f(k2)f(k)=(k-1)*(f(k1)+f(k2)分析分析2021/8/1453递推的应用（组合计数）递推的应用（组合计数）例题例题12：编码问题：编码问题【问题描述问题描述】编码工作常被运用于密文或压缩传编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数字。字母表中共有把一些有规律的单词编成数字。字母表中共有26个

30、小写字母个小写字母a,b,c.,z。这些特殊的单词长度不超。这些特殊的单词长度不超过过6且字母按照升序排列。把所有这样的单词放在且字母按照升序排列。把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就对应一起，按字典顺序排列，一个单词的编码就对应着它在字典中的位置，例如：着它在字典中的位置，例如：a-1;b-2;z-26;ab-27;ac-28;你的任务就是对于所给的单词，求出它你的任务就是对于所给的单词，求出它的编码。的编码。2021/8/1454递推的应用（博弈问题）递推的应用（博弈问题）例例例例题题题题13131313：走走走走直直直直线线线线棋棋棋棋问问问问题题题题。有如下所示的

31、一个编号为到的方格： 现由计算机和人进行人机对奕，从到，每次可以走个方格，其中为集=a1,a2, a3,.am中的元素(m=4)，规定谁最先走到第n格为胜，试设计一个人机对奕方案，摸拟整个游戏过程的情况并力求计算机尽量不败。12345 N-1 N2021/8/1455分析题设条件：若谁先走到第N格谁将获胜，例如，假设S=1,2，从第N格往前倒推，则走到第N-1格或第N-2格的一方必败，而走到第N-3格者必定获胜，因此在N，S确定后，棋格中每个方格的胜、负或和态（双方都不能到达第N格）都是可以事先确定的。将目标格置为必胜态，由后往前倒推每一格的胜负状态，规定在自己所处的当前格后，若对方无论走到哪

32、儿都必定失败，则当前格为胜态，若走后有任一格为胜格，则当前格为输态，否则为和态。2021/8/1456分析分析 设1表示必胜态，-1表示必败态，0表示和态或表示无法到达的棋格。 例如，设N10，S1,2，则可确定其每个棋格的状态如下所示： 而N10，S2,3时，其每格的状态将会如下所示： 有了棋格的状态图后，程序应能判断让谁先走，计算机选择必胜策略或双方和（双方均不能到达目标格）的策略下棋，这样就能保证计算机尽可能不败。1 1-1-1-1-11 1-1-1-1-11 1-1-1-1-11 10 0-1-1-1-10 01 10 0-1-1-1-10 01 12021/8/1457递推的应用（动

33、态规划中的递推）递推的应用（动态规划中的递推）例题例题14：最小伤害：最小伤害把儿站在一个NxN的方阵中最左上角的格子里。他可以从一个格子走到它右边和下边的格子里。每一个格子都有一个伤害值。他想在受伤害最小的情况下走到方阵的最右下角。2021/8/1458分析分析Fi,j：设走到(i,j)这格的最小伤害值,aij表示(i,j)这格的伤害值。Fi,j=min(fi-1,j,fi,j-1)+ai,j边界条件：f1,1=a1,1fi,1=fi-1,1+ai,1(2=i=n)f1,i=f1,i-1+a1,i(2=i=n)2021/8/1459在一个nm的方格中，m为奇数，放置有nm个数，如图,方格中间

34、的下方有一人，此人可按照五个方向前进但不能越出方格,见右下图。人每走过一个方格必须取此方格中的数。要求找到一条从底到顶的路径，使其数相加之和为最大。输出和的最大值。1643126034-56700260-1-236853400-27-17407-560-1341242人 递推的应用（动态规划中的递推递推的应用（动态规划中的递推) )例题例题例题例题1515：方格取数：方格取数：方格取数：方格取数2021/8/1460分析分析我们用坐标我们用坐标(x,y)唯一确定一个点，其中唯一确定一个点，其中(n,m)表示图的右上角，表示图的右上角，而人的出发点是，受人前进方向的限制，能直接到达点而人的出发点

35、是，受人前进方向的限制，能直接到达点(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,

36、y其中其中ax,y表示表示(x,y) 点上的数字。点上的数字。边界条件为：边界条件为：F0,m/2=0 F0,x=-(1=xmax then max:=j; end;end; 2021/8/1469 起始状态就是调用起始状态就是调用findmax(1,max),而像上述过而像上述过程中的变参程中的变参max完全可以省略。将上述方法修改可得完全可以省略。将上述方法修改可得下面的算法：下面的算法：Procedure findmax(i:integer);begin if i=n then exit else begin findmax(i+1); if aimax then max:=ai; en

37、d;end;2021/8/1470 起始状态就是调用起始状态就是调用findmax(1) ，max为全为全局变量，同时还减少了一个局部变量的使用。尽局变量，同时还减少了一个局部变量的使用。尽管这只是一个很简单的例子，在本例中不做精简，管这只是一个很简单的例子，在本例中不做精简，程序也还是能通过，但它精简的原则对其它使用程序也还是能通过，但它精简的原则对其它使用递归的程序而言却是同样适用的。特别是在递归递归的程序而言却是同样适用的。特别是在递归过程出现堆栈溢出情况时就应该考虑这一问题。过程出现堆栈溢出情况时就应该考虑这一问题。2021/8/1471四、递归的优点与缺点四、递归的优点与缺点采用递归

38、方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。2021/8/1472五、递归的应用五、递归的应用处理递归定义或解决方法为递归方式的问题解决搜索问题实现分治思想用于输出动态规划的中间过程2021/8/14731、递归定义问题、递归定义问题树结构是由递归定义的。因此，在解决与树有关的问题时，常常可以采用递归的方法。2021/8/14742、解决搜索问题、解决搜索问题因为搜索产生的节点成树状结构，所以可以用递归方法解

39、决。这类例子很多，如“N皇后”问题，全排列，哈密顿回路，图的可着色性等搜索问题。2021/8/1475例题：全排列例题：全排列【问题描述问题描述】编程列举出编程列举出1、2、n的全排列，要的全排列，要求产生的任一个数字序列中不允许出现重复的数字。求产生的任一个数字序列中不允许出现重复的数字。【文件输入文件输入】输入输入n(1=n=9)【文件输出文件输出】有有1到到n组成的所有不重复数字的序列，组成的所有不重复数字的序列，每行一个序列每行一个序列2021/8/1476分析我们假设n=3时，如下图：位置1可以放置数字1、2、3；位置2可以放置数字1、2、3；位置3可以放置数字1、2、3，但是当位置

40、1放了数字1后位置2和位置3都不能在放1，因此画树的约束条件是：各位置的数字不能相同。2021/8/1477分析我们画“解答树”时，根结点一般是一个空结点，根结点下面的第1、2、3三层分别对应位置1、位置2、位置3，用“”标示的分支表示该结点不满足约束条件，不能被扩展出来：2021/8/1478procedure 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 / 如果搜索到一条路径，则输出一

41、种解如果搜索到一条路径，则输出一种解 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;我们用递归过程来描述我们用递归过程来描述我们用递归过程来描述我们用递归过程来描述 “ “

42、解答树解答树解答树解答树” ”的深度优先搜索的深度优先搜索的深度优先搜索的深度优先搜索2021/8/14793、实现分治思想、实现分治思想不难发现，在各种时间复杂度为nlogn排序方法中，大都采用了递归的形式。因为无论是分治合并排序，还是堆排序、快速排序，都存在有分治的思想。只要分开处理，就可以采用递归。其实进行分治，也是一个建树的过程。2021/8/14802021/8/1481例题：表达式求值例题：表达式求值由键盘输入一个算术表达式，该表达式由数字，加(+)、减(-)、乘(*)、求商(/)运算符及小括号组成。例如：6*(8-1)+(5-(12-7)/5)/2请编写一个程序，计算输入表达式的

43、值。2021/8/1482funtion tree(left,right:integer):integer;funtion tree(left,right:integer):integer;beginbegin var tmp,L1,L2,p:integer; var tmp,L1,L2,p:integer; tmp:=isnum(left,right); tmp:=isnum(left,right); if tmp-1 begin tree:=tmp;exit;end;/ if tmp-1 begin tree:=tmp;exit;end;/返回值返回值返回值返回值 if (stleft=(

44、)and (poskh(left,right)=right) thenif (stleft=()and (poskh(left,right)=right) then tree:=tree(left+1,right-1); tree:=tree(left+1,right-1); / /去掉最外层的括号去掉最外层的括号去掉最外层的括号去掉最外层的括号 p:=findlow(left,right); /p:=findlow(left,right); /找运算级别最低的运算符找运算级别最低的运算符找运算级别最低的运算符找运算级别最低的运算符 L1:=tree(left,p-1); /L1:=tree(

45、left,p-1); /递归左子树递归左子树递归左子树递归左子树 L2:=tree(p+1,right); /L2:=tree(p+1,right); /递归右子树递归右子树递归右子树递归右子树 tree:=cal(L1,stp,L2);tree:=cal(L1,stp,L2);end;end;2021/8/14834、用于输出动态规划的中间过程、用于输出动态规划的中间过程例题：复制书稿例题：复制书稿 【问题描述问题描述】假设有m本书（编号为1,2,m），想将每本复制一份，m本书的页数可能不同（分别是p1,p2,pm）。任务是将这m本书分给k个抄写员（k=m），每本书只能分配给一个抄写员进行复

46、制，而每个抄写员所分配到的书必须是连续顺序的。复制工作是同时开始进行的，并且每个抄写员复制的速度都是一样的。所以，复制完所有书稿所需时间取决于分配得到最多工作的那个抄写员的复制时间。2021/8/1484试找一个最优分配方案，使分配给每一个抄写员的页数的最大值尽可能小（如存在多个最优方案，输出结果排序最小的一种）。2021/8/1485分析分析该题中m本书是顺序排列的，k个抄写员选择数也是顺序且连续的。不管以书的编号，还是以抄写员标号作为参变量划分阶段，都符合策略的最优化原理和无后效性。考虑到k=m，以抄写员编号来划分阶段会方便些。设fi,j为前i个抄写员复制前j本书的最小“页数最大数”。Si

47、=a1+a2+ai，则状态转移方程为：fi,j=minmax(fi-1,k,Sj-Sk)(i-1=k=j-1)di,j=k；记录第i个人的最佳位置边界条件f1,i=Si。输出方案，则递归输出；2021/8/1486procedure Print(i,j:integer)begin if i=1 begin writeln(1, ,j);exit;end; Print(i-1,di,j); writeln(di,j+1, ,j);end2021/8/1487第四部分第四部分归纳策略归纳策略2021/8/1488归纳法的基本思想归纳法的基本思想 归纳法的基本思想是通过列举少量的特殊情况，经过分析，

48、最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径。2021/8/1489归纳法解题归纳法解题的过程的过程1.细心的观察；2.丰富的联想；3.继续尝试；4.总结归纳出结论。2021/8/1490归纳法解题归纳法解题的过程的过程归纳是一种抽象，即从特殊现象中找出一般关系。由于在归纳的过程中不可能对所有的可能情况进行枚举，因而最后得到的结论还只是一种猜测(即归纳假设)。所以，严格说来对于归纳假设还必须加以严格的证明。2021/8/1491归纳策略解题应注意的问题：归纳策略解题应注意的问题：1.从问题的简单具体状态分析入手，目的是去寻求可以

49、推广的一般性规律，因此应考虑简单状态与一般性状态之间的联系。2.从简单状态中分析出来的规律特征应能够被验证是正确的，不能想当然或任意地提出猜想，否则归纳出来的结论是错误的，必然导致整个问题的解是错解。2021/8/1492归纳策略的应用归纳策略的应用例题例题1：求前n个自然数的平方之和：S=12+22+32+n22021/8/1493【分分析析】这本是一道很简单的题目，但如果能找出S值与n的关系，则此题将更进一步得到简化，由数学证明得知：(12+22+32+n2)/(1+2+3+n)=(2n+1)/3又由于1+2+3+n=n(n+1)/2，因此得到：12+22+32+n2=n(n+1)(2n+

50、1)/6但这只是通过总结归纳而得到的一种猜测，是否正确还需证明，对归纳假设的证明通常采用数学归纳法（证略）。2021/8/1494例例题题2：若干个正整数之和为n，其中：n2000，试求它们乘积的最大值以及该最大值的位数k。2021/8/1495【分析分析分析分析】根据数学规律可知,若要使和固定的数的乘积最大，必须使这些数尽可能的多为3，于是可推得以下规律：当Nmod31时，N可分解为一个4和若干个3的和；当Nmod32时，N可分解为一个2和若干个3的和；当Nmod30时，N直接分解为若干个3的和。按照这一分解方法，所有因数的乘积必定最大。注意注意：因N的最大值可达2000，乘积将超过长整型数

51、据范围，所以需用高精度运算。2021/8/1496例题例题例题例题3 3：极值问题已知m、n为整数，且满足下列两个条件：m、n1，2，K，（1K109）(n2mnm2)21编一程序，由键盘输入K，求一组满足上述两个条件的m、n，并且使m2n2的值最大。例如，若K1995，则m987，n1597，则m、n满足条件，且可使m2n2的值最大。2021/8/1497【分析分析】分析小数据会发现：m,n是Fibonacci数列的相邻两项。因为：(n2-mn-m2)2=1故：(m2+mn-n2)2=1又：m2+mn-n2=(m+n)2-mn-2n2=(m+n)2-(m+n)n-n2故：(m2+mn-n2)

52、2=(m+n)2-(m+n)n-n22即：(n2-mn-m2)2=(m+n)2-(m+n)n-n222021/8/1498【分析分析分析分析】由上述数学变换式可以得出，如果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最大值，此时m2n2的值最大。2021/8/1499递推进阶递推进阶例题例题1：位数问题：位数问题【问题描述问题描

53、述】在所有的N位数中，有多少个数中有偶数个数字3？由于结果可能很大，你只需要输出这个答案mod 12345的值。【文件输入文件输入】读入一个数N( (1=N=1000)【文件输出文件输出】输出有多少个数中有偶数个数字3。【样例输入样例输入】2【样例输出样例输出】732021/8/14100递推进阶递推进阶例题例题2：铺磁砖问题：铺磁砖问题【问题描述问题描述】用用1x1和和2x2的磁砖不重叠地铺满的磁砖不重叠地铺满Nx3的地板，的地板，问共有多少种不同的方案？问共有多少种不同的方案？【文件输入文件输入】输入一个整数输入一个整数n（1=N=1000）。）。【文件输出文件输出】输出方案数，由于结果可

54、能很大，你只需要输输出方案数，由于结果可能很大，你只需要输出这个答案出这个答案mod 12345的值。的值。【样例输入样例输入】2【样例输出样例输出】32021/8/14101递推进阶递推进阶例题例题3：路程问题：路程问题【问题描述问题描述】从原点出发，一步只能向右走、向上走或向左从原点出发，一步只能向右走、向上走或向左走。恰好走走。恰好走N步且不经过已走的点共有多少种走法？步且不经过已走的点共有多少种走法？【文件输入文件输入】输入一个整数输入一个整数n（1=n=1000）。）。【文件输出文件输出】输出走法数。由于结果可能很大，你只需要输输出走法数。由于结果可能很大，你只需要输出这个答案出这个

55、答案mod 12345的值。的值。【样例输入样例输入】2【样例输出样例输出】72021/8/14102递推进阶递推进阶例题例题4：圆周上的弦：圆周上的弦【问题描述问题描述】圆周上有圆周上有N个点。连接任意多条（可能是个点。连接任意多条（可能是0条）条）不相交的弦（共用端点也算相交）共有多少种方案？不相交的弦（共用端点也算相交）共有多少种方案？【文件输入文件输入】输入一个整数输入一个整数n（1=N=1000）。）。【文件输出文件输出】输出方案数。由于结果可能很大，你只需要输输出方案数。由于结果可能很大，你只需要输出这个答案出这个答案mod 12345的值。的值。【样例输入样例输入】4【样例输出样

56、例输出】92021/8/14103递推进阶递推进阶例题例题5：矩形中的树：矩形中的树【问题描述问题描述】在网格中取一个在网格中取一个N x 1的矩形，并把它当作一的矩形，并把它当作一个无向图。这个图有个无向图。这个图有2(N+1)个顶点，有个顶点，有3(N-1)+4条边。这个条边。这个图有多少个生成树？图有多少个生成树？【文件输入文件输入】输入一个整数输入一个整数n（1=N=1000）。）。【文件输出文件输出】输出这个图有多少个生成树？由于结果可能很输出这个图有多少个生成树？由于结果可能很大，你只需要输出这个答案大，你只需要输出这个答案mod 12345的值。的值。【样例输入样例输入】1【样例输出样例输出】42021/8/14104个人观点供参考，欢迎讨论部分资料从网络收集整理而来，供大家参考，感谢您的关注！