信息学奥林匹克竞赛辅导课件-归纳策略.ppt

第三节、归纳策略,如果说对应策略的核心是举一反三、触类旁通地对已经解决的类似问题和有关事实作联想，外推出事物间联系的话，那么归纳策略则是通过列举试题本身的特殊情况，经过深入分析，最后概括出事物内在的一般规律，并得到一种高度抽象的解题模型。,归纳法要比搜索的方法（例如以后将讲解的枚举法、回溯法等）更能反映问题的本质。但是并不是所有实际问题都可以总结归纳出一般规律，即便是可以，归纳也不是一件容易的事情，尤其要归纳出一个数学模型更为困难。而且归纳过程通常没有一定的规则可供遵循。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径。,通常，归纳的过程分四个步骤：,(1)细心的观察(2)丰富的联想(3)继续尝试(4)总结归纳出结论,归纳是一种抽象，即从特殊现象中找出一般关系。但在归纳过程中不可能列举所有情况，因而最后得出的结论还只是一种猜测（即归纳假设）。通过精心观察而提出的归纳假设得不到证实或最后证明是错的，也是常有的事。因此要尽可能对归纳假设加以严格的证明，证明的方法通常使用数学归纳法。即便找不到证明方法，也必须尽可能多地提出那些容易出错和疏漏的边界情况加以验证，使归纳出的结论和解决问题的途径经得起各种测试数据的检验。,问题经过分析归纳后，一般产生四种结果：,(1)递推式(2)递归式(3)制定目标(4)贪心方案,当然，经过分析直接概括出高度抽象的数学公式亦是一种归纳过程、一种解题的途径。但是怎样进行这种归纳，这个问题太宽泛，与其说它是计算机算法的策略，还不如说它是一种数学知识和数学能力，取决于解题者本身的数学功底。我们已经在“对应策略”一节中，对如何将试题与数学公式对应的问题作了一些讨论，这里不再赘述。,一、递推法,瞬息变幻的世界，每一件事物都在随时间的流逝发生着微妙的变化。而在这纷繁的变幻中，许多现象的变化是有规律的，这种规律往往呈现出前因和后果的关系。即某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。所谓“三岁看老”，说的就是这个道理。这一道理也正体现了递推的思想。递推关系几乎在所有的数学分支中都有重要作用，在联赛中更因其简捷高效而显示出独特的魅力。,1.递推关系的定义和求解方法,有一类试题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如下简捷的递推关系式：fn=g(fn-1)或者fn-1=g(fn)这样就在数的序列中，建立起后项和前项之间的关系。然后从初始条件(或最终结果)入手，一步步地按递推关系式递推，直至求出最终结果(或初始值)。很多程序就是按这样的方法逐步求解的。如果对一个试题，我们要是能找到后一项数与前一项数的关系并清楚其起始条件（或最终结果），问题就比较容易解决，让计算机一步步计算就是了。让高速的计算机从事这种重复运算，可真正起到“物尽其用”的效果。,顺推法就是由边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推出再后项值，依次递推，直到从问题初始陈述向前推进到这个问题的解为止。倒推法就是在不知初始值的情况下，经推理而获知问题的最终解或目标，再倒过来，推知它的初始条件。因为这种问题的运算过程是一一映射的，故可分析其倒推公式。然后再从最终解或目标出发，采用倒推手段，一步步地倒推到这个问题的初始陈述。,递推分倒推法和顺推法两种形式：,一般分析思路：,if(求解初始条件f1)/倒推由题意(或递推关系)确定最终结果fn;求出倒推关系式fi-1=g(fi);for(i=n;i=2;i-)fi-1=g(fi);/从最终结果fn进行倒推推出倒推结果f1;else/顺推由题意(或递推关系)确定初始值f1(边界条件);求出顺推关系式fi=g(fi-1);for(i=2;i=2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn=2hn-1+1边界条件：h1=1,(3）平面分割问题,设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。分析：设an为n条封闭曲线把平面分割成的区域个数。由图可得:a2-a1=2;a3-a2=4;a4-a3=6。,从这些式子中可以看出an-an-1=2(n-1)当然，上面的式子只是我们通过观察4幅图后得出的结论，它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有n-1条曲线将平面分割成an-1个区域后，第n条曲线每与其他曲线相交一次，就会增加一个区域，因为平面上已经有了n-1条封闭曲线，且第n条曲线与己有的每一条闭曲线恰好相交于两点，不会与任两条曲线交于同一点，故平面上一共增加2(n-1)个区域，加上已有的an-1个区域，一共有an-1+2(n-1)个区域。所以本题的递推关系是an=an-1+2(n-1)，边界条件是a1=2。,平面分割问题是竞赛中经常触及到的一类问题，由于其灵活多变，常常让选手感到棘手，下题是另一种平面分割问题，有兴趣的读者不妨自己先试着求一下其中的递推关系。,(4)Catalan数,在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用hn表之，hn即为Catalan数。例如五边形有如图所示的五种拆分方案，故h5=5。求对于一个任意的凸n边形相应的hn。Catalan数首先是由Euler在精确计算对凸n边形不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。,分析：设Cn表示凸n边形的拆分方案总数。由题目中的要求可知一个凸n边形的任意一条边都必然是一个三角形的一条边，边P1Pn也不例外，再根据“不在同一直线上的三点可以确定一个三角形”，只要在P2，P3，Pn-1，点中找一个点Pk(1=1)边界条件为：S2(n,0)=0S2(n,1)=1，S2(n,n)=1S2(n,k)=0(kn),第二类stirling数在竞赛中较少出现，但在竞赛中也有一些题目与其类似，甚至更为复杂。读者不妨自己来试着建立其中的递推关系。通过上面对五种典型的递推关系建立过程的探讨，可知对待递推类的题目，要具体情况具体分析，通过找到某状态与其前面状态的联系，建立相应的递推关系。,3递推关系的应用,递推关系的应用十分广泛，其中一个非常重要的应用就是著名的杨辉三角（又称“Pascal三角”。杨辉三角是根据组合公式Cnr=Cn-1r+Cn-1r-1画出来的。很显然，组合公式、杨辉三角都属于递推关系的范围。,在今天的信息学竞赛中，递推关系的应用也日趋广泛，下面就让我们从近年来的两道竞赛题中体会递推关系的应用。,【例13】蜜蜂爬行,有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行，如图所示。试求出蜜蜂从蜂房a爬到蜂房b的可能路线数,分析：这是一道很典型的Fibonacci数列类题目，其中的递推关系很明显。由于“蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行”的限制，决定了蜜蜂到n点的路径只能是从n-1点或n-2点到达的，故:fn=fn-1+fn-2(a+2P)，边界条件在前面己经计算过了，是fp=2*p。虽然这题看上去有两个参数，但是在实际做题中会发现，本题还是属于带一个参数的递推关系。,【例15】平面分割空间问题,一个平面把空间分成独立的两个部分，两个平面把空间分成4个部分。n个平面，最多能把整个空间分割成多少个部分。分析：立体空间的情况是陌生的，但是空间和平面的关系与平面和直线的关系是相似的。平面把空间分割成两个部分，直线也把平面分割成两个部分。于是得到了另一个与例题相类似的问题：n条直线，最多能把整个平面分割成多少个部分，如图所示。,一条直线,把平面分割为两个部分;增加一条直线，它与第一条直线相交,被分为两段射线，每一段射线又把所在的区域分成两部分;因此增加了2个部分。再增加一条直线，它与前两条直线相交，被分为三段，每一段又把所在区域分成两部分;共增加了3个部分。由此类推，设前k-1条直线共把平面分为ak-1个部分。加入第k条直线，与前k-1条直线相交，被分为k段，每一段把所在区域分为两部分；总共增加了k部分；总共有ak-1+k个部分。于是得到了递推关系:,a1=2;ak=ak-1+k;即ak=1+k*(1+k)/2于是直线分割平面的问题就解决了。既然空间和平面，与平面和直线的关系相似，那么直接把平面换成空间，把直线换成平面，就可以直接用以上的过程来证明未知的问题了吗？显然是不可以的，这种仅仅根据主观的相似性得出的机械模仿是错误的。,但是如果仔细分析一下错误的原因，将会发现问题的关键:线线相交得到的是交点,面面相交得到的是直线,k个点把直线分成k+1个部分,而k条直线则不是简单的把平面分成k+1个部分。事实上,k条直线最多把平面分成ak个部分！因此两个问题真正的相似之处在于，一个为了计算直线把平面分割成几部分，先计算这条直线被点（线线交点）分割成几部分，把二维的问题化为一维的问题；另一个要计算平面把空间分割成几部分，先计算这个平面被线（面面交线）分割成几部分，把三维的问题化为二维的问题。而二维的问题是已经被解决了的，于是反过来，三维的问题也解决了。,同样是利用数学归纳法：一个平面把空间分割成两部分；设前k-1个平面共把空间分割成bk-1个部分。加入第k个平面后，与前k-1个平面相交，共有k-1条交线。k-1条交线把这个平面分为几块呢？这买际上就是刚刚解决过的回题：k-1条直线，把平面分割成：ak-1=1+k*(1+k)/2分别把所在原来空间一分为二，总共增加了ak-1个部分，于是平面总共把空间分割成个部分。于是得到了递推关系：,利用这一递推关系来编写程序，不难求出bn，而且即便对很大的n，程序的运算速度仍然是很快的。（当然，也可以计算出bn的通项公式:,二、递归法,设一个未知函数f，用其自身构成的已知函数g来定义：f(n)=g(n,f(n-1)n0f(0)=an=0为了定义f(n)，必须先定义f(n-1),为了定义f(n-1)，又必须先定义f(n-2),上述这种用自身的简单情况来定义自己的方式称为递归定义。一个递归定义必须是有确切含义的，也就是说，必须一步比一步简单，最后是有终结的，决不能无限循环下去。在f(n)的定义中，当n为0时定义一个已知数a，是最简单的情况，称为递归边界，它本身不再使用递归的定义。,与递推一样，每一个递归定义都有其边界条件。但不同的是，递推是由边界条件出发，通过递推公式求f(n)的值，从边界到求解的全过程十分清楚；而递归则是从函数自身出发来达到边界条件。在通往边界条件的递归调用过程中，系统用堆栈把每次调用的中间结果保存在栈区，直至求出递归边界值f(0)=a。然后返回调用函数。返回过程中，中间结果相继出栈恢复，f(1)=g(1,a)f(2)=g(2,f(1)直到f(n)=g(n,f(n-1)描述递归定义的函数或求解递归问题的过程称为递归算法。一个递归算法，本质上是将较复杂的处理归结为简单处理，直到最简单的处理。,从实际问题中抽象递归定义和边界条件的过程是一种归纳，通过这种归纳方式能使一个蕴含递归关系且结构复杂的程序简捷精炼，增加可读性。特别是在难于找到从边界到解的全过程的情况下，如果把问题推进一步，其结果仍维持原问题的关系，则采用递归算法编程比较合适。但递归算法也有致命的缺点，其执行的效率比较低，尤其在边界条件设置不当的情况，极有可能陷入死循环或者内存溢出的窘境。,递归算法适用的一般场合为：(1)数据的定义形式按递归定义。这类递归问题可直接转化为递推算法，递归边界作为递推的边界条件。(2)数据之间的关系(即数据结构)按递归定义。如树的遍历，图的搜索等。(3)有些问题本身没有明显的递归结构，但使用递归求解比其他方法更简单。如递归的分治策略。对于(2)、(3)，可利用堆栈结构将其转换为非递归算法，但结构不如递归算法简单清晰，可读性较差。,编写递归程序时应注意如下几个问题：(1)问题的递归定义，即如何用自身的简单情况定义自己；(2)递归边界，即递归至哪个边界值后开始回溯；(3)参与递归运算的变量有哪些，其中哪些作为值参，哪些作为局部变量。如果有全局变量参与递归运算的话(初始值由主程序传入，受内存限制不便作为值参)，回溯过程中必须恢复其递归前状态。,【例16】计算交点数,在平面上有n条直线，且无三线共点。问这些直线能有多少种不同的交点数？输入：n输出：以下若干行列出所有相交方案。其中每一行为某一方案的交点个数。分析：我们将n条直线排成一个序列。直线2与直线1最多有一个交点；直线3与直线1和直线2最多有2个交点，直线n与其他n-1条直线最多有n-1个交点。由此得出n条直线互不平行且无三线交于一点的最多交点数中1+2+，+(n-1)=n*(n-1)/2.,设,我们来具体分析n=4的情况(1)四条直线全部平行，无交点，g0=1(2)其中三条(n-1)直线平行，交点数为(n-1)x1+0=3,g3=1(3)其中两条(n-2)直线平行，这两条直线与另外两条直线之间的交点数为(n-2)x2=4而另外两条直线本身既可能平行也可能相交，因此交点数分别为：当平行时(n-2)x2+0=4g4=1当相交时(n-2)x2+1=5g5=1(4)四条直线互不平行，交点数为：1+2+3=6g6=1即n=4时，有0、3、4、5、6个不同的交点数,由此得出：m条直线的交点方案=r条平行线与(m-r)条直线交叉的交点数+(m-r)条直线本身的交点方案=(m-r)r+(m-r)条直线本身的交点数(1=1;r-)cross(m-r,j+r*(m-r);else/否则确定m条直线存在j个交点gj=1;,计算和输出n条直线的交点方案如下：,#includeusingnamespacestd;constintMAX=10000;staticintgMAX;voidmain()intn,k,total=0;cinn;k=n*(n-1)/2;cross(n,0);for(inti=0;i=k;i+)if(gi=1)total+;coutiendl;,三、制定目标,有些问题看似棘手，主要是没有找到解决问题的路子，或者说目标不明确。一旦建立了评判好坏的标准(目标函数或者目标方案)，求解问题的算法也就自然而然地产生了。关键是建立标准。而这个标准是通过对实际问题的分析与归纳得到的。因此，我们将之划入归纳的范畴。,【例17】最优分解方案,把正整数n分解成若干个互不相等的自然数的和，且使这些自然数的乘积最大。请你编写一个算法，由键盘输入n,求满足条件的分解方案。输入：n(3=n=ak+1这种分解方案的项数无疑最多。问题是要保证ak+1=ak,ak+1要么为1,要么重复其中某一项，因此必须撤去。为了保证撤去ak+1后的各个自然数依然互不相等，其和还是等于n且乘积最大，我们将ak+1尽量平均地加在后几项。并尽可能使得相邻两数的差不超过2,若ak+1=1,由于1x2x,xak2x3x,x(ak+1)，因此ak+1=1加到ak上；若1n;if(n=3)|(n=4)mul=1*(n-1);/当n=3或4时，输出分解方案。else,intk=1;ak=2;n=n-ak;/从2开始分解while(nak)/分解直到ak+1=akk+;ak=ak-1+1;n=n-ak;if(n=1)ak+;n-;/ak+1=1elseif(n=ak)/ak+1=akak+;n-;/1ak+1akfor(inti=0;i=n-1;i+)ak-i+;for(inti=1;i=k;i+)mul=mul*ai;cout=Fi，则活动i和活动j兼容。选择由互相兼容的活动组成的最大集合。输入：nS1F1SnFn输出：占用时间t最大集合A中的活动序号,分析：我们使用尽可能逼近目标的贪心策略来选择活动，即每一步总是选择这样一个活动来占用资源它能够使得余下的未调度时间最大化，使得兼容的活动尽可能多。为了达到这个目的，我们将n个待选活动按结束时间递增的顺序排列：F1=F2=Fn递增序列中的活动1进入集合A。然后依次分析序列中的活动2到活动n，将那些与A中活动兼容的活动送入集合A。,例如活动开始时间结束时间13521431214481250668117610857938105911213,#includeusingnamespacestd;constintN=11;/活动序号intnoN=1,2,3,4,5,6,7,8,9,10,11;/开始时间intsN=3,1,12,8,0,8,6,5,3,5,2;/结束时间intfN=5,4,14,12,6,11,10,7,8,9,13;,voidswap(int,voidmain()staticintaN;/a是兼容集合intt=0;/t是占用时间sort();/按结束时间递增的顺序排序intk=0;intj=0;ak=no0;/初始活动表为NO0for(inti=1;i=fj)k+;ak=noi;t=fi;j=i;couttendl;for(i=0;i=k;i+)coutai=5*a4)a2=a2-5*a4;elsea1=max(0,a1-(20*a4-4*a2);a2=0;,if(a3%4=0)c=c+a3/4;elsec=c+a3/4+1;if(a3%4=3)a1=max(0,a1-(9-4*min(1,a2);a2=max(0,a2-1);elseif(a3%4=2)a1=max(0,a1-(18-4*min(3,a2);a2=max(0,a2-3);elsea1=max(0,a1-(27-4*min(5,a2);a2=max(0,a2-5);/a3%4=1,if(a2%9=0)c=c+a2/9;elsec=c+a2/9+1;if(a2%9!=0)a1=max(0,a1-(36-4*(a2%9);if(a1%36=0)c=c+a1/36;elsec=c+a1/36+1;returnc;,#includeusingnamespacestd;inlineintmax(inta,intb)returnab?a:b;inlineintmin(inta,intb)returnaa1a2a3a4a5a6;couta1a2a3a4a5a6)if(a1=0),贪心算法的基本要素,可以用贪心算法求解的问题一般具有两个重要的性质：贪心选择性质和最优子结构性质1.贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。贪心算法所做的贪心选择可以依赖于以往所做过的选择，但决不依赖于将来所做的选择，也不依赖于子问题的解。,贪心算法通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。2.最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。,本节作业,一、简要回答如下问题：简述归纳过程步骤？递推方法一般分析思路是什么？递归算法适用的一般场合是什么？简述贪心算法的基本要素,二、根据题意，建立如下问题的递推公式或递归公式？(1)Fibonacci数列(2)Hanoi塔问题(3)封闭曲线分割平面问题(4)Catalan数(5)第二类stirling数【例13】蜜蜂爬行【例14】直线分割平面【例15】平面分割空间问题,第四节、模拟策略,在自然界和日常生活中，许多现象具有不确定的性质，有些问题甚至很难建立数学模型，或者很难用计算机建立递推、递归、枚举、回溯等算法。在这种情况下，一般采用模拟策略。所谓模拟策略就是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。,模拟题没有固定的模式，一般形式有两种：(1)随机模拟：题目给定或者隐含某一概率。设计者利用随机函数和取整函数设定某一范围的随机值，将符合概率的随机值作为参数。然后根据这一模拟的数学模型展开算法设计。由于解题过程借助了计算机的伪随机数发生器，其随机的意义要比实际问题中真实的随机变量稍差一些，因此模拟效果有不确定的因素。,(2)过程模拟：题目不给出概率，要求编程者按照题意设计数学模型的各种参数，观察变更这些参数所引起过程状态的变化，由此展开算法设计。模拟效果完全取决于过程模拟的真实性和算法的正确性，不含任何不确定因素。由于过程模拟的结果无二义性，因此竞赛大都采用过程模拟。,模拟的解题方法一般有三种类型：(1)直叙式模拟(2)筛选法模拟(3)构造法模拟,一、直叙式模拟,直叙式模拟，即按照试题要求展开模拟过程。编程者要忠实于原题，认真审题，千万不要疏漏任何条件，精心设计方便模拟的数据结构。直叙式模拟的难度取决于模拟对象所包含的动态变化的属性个数，动态属性愈多，则难度愈大。,【例19】约瑟夫问题,有n只猴子，按顺时针方向围成一圈选大王（编号从1到n），从第1号开始报数，一直数到m，数到m的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入n，m后，输出最后猴王的编号。Input:每行是用空格分开的两个整数，第一个是n,第二个是m(0nm;if(n=0)break;for(i=0;in;i+)loopi=i+1;intnPtr=0;for(i=0;in;i+),intnCount=0;while(nCountm)while(loopnPtr=0)nPtr=(nPtr+1)%n;nCount+;nPtr=(nPtr+1)%n;nPtr-;if(nPtr0)nPtr=n-1;if(i=n-1)coutnm;link=NULL;for(inti=0;iID=i+1;if(link=NULL)link=lastMonkey=monkey;elselastMonkey-next=monkey;lastMonkey=monkey;lastMonkey-next=link;,count=1;while(link!=NULL)if(link-next=link)coutID;deletelink;break;if(count=m-1)monkey=link-next;link-next=monkey-next;deletemonkey;count=0;link=link-next;count+;return0;,【例20】DAM语言,有个机器执行一种DAM语言。该机器有一个栈，初始时栈里只有一个元素x，随着DAM语言程序的执行，栈里的元素会发生变化。DAM语言有三种指令：D指令：把栈顶元素复制一次加到栈顶。A指令：把栈顶元素取出，加到新的栈顶元素中。M指令：把栈顶元素取出，乘到新的栈顶元素中。,如果执行A或M指令的时候栈内只有一个元素，则机器会发出错误信息。如果程序无误，那么执行完毕以后，栈顶元素应该是X的多项式，例如，程序DADDMA的执行情况为（栈内元素按照从底到顶的顺序从左至右排列，用逗号隔开）：,给出一段DAM程序，求出执行完毕后栈顶元素。输入：输入仅一行，包含一个不空的字符串s，长度不超过12，代表一段DAM程序。输入程序保证合法且不会导致错误。输出：仅输出一行，即栈顶多项式。须按照习惯写法降幂输出，即等于1的系数不要打印，系数为0的项不打印，第一项不打印正号。一次方不打印“1”。分析：本题是一道“直叙式模拟”题，即按照DAM指令的顺序模拟执行过程。在模拟的时候有些问题是需要注意的：,(1)多项式的表示方式。有的选手或许会觉得本题没有说明次数的上限，因此最好用链表做。其实完全没有必要。由于指令不超过12条，而D指令和A、M指令总数应该相等，因此最多有6条M指令，因此次数上限为26=64。我们可以用数组来表示多项式，