信息学奥林匹克竞赛辅导归纳策略.pptx

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,第三节、归纳策略,如果说对应策略的核心是举一反三、触类旁通地对已经解决的类似问题和有关事实作联想，外推出事物间联系的话，那么归纳策略则是通过列举试题本身的特殊情况，经过深入分析，最后概括出事物内在的一般规律，并得到一种高度抽象的解题模型。,归纳法要比搜索的方法（例如以后将讲解的枚举法、回溯法等）更能反映问题的本质。但是并不是所有实际问题都可以总结归纳出一般规律，即便是可以，归纳也不是一件容易的事情，尤其要归纳出一个数学模型更为困难。而且归纳过程通常没有一定的规则可供遵循。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径。,通常，归纳的过程分四个步骤：,(1),细心的观察,(2),丰富的联想,(3),继续尝试,(4),总结归纳出结论,归纳是一种抽象，即从特殊现象中找出一般关系。但在归纳过程中不可能列举所有情况，因而最后得出的结论还只是一种猜测（即归纳假设）。通过精心观察而提出的归纳假设得不到证实或最后证明是错的，也是常有的事。因此要尽可能对归纳假设加以严格的证明，证明的方法通常使用数学归纳法。即便找不到证明方法，也必须尽可能多地提出那些容易出错和疏漏的边界情况加以验证，使归纳出的结论和解决问题的途径经得起各种测试数据的检验。,问题经过分析归纳后，一般产生四种结果：,(1),递推式,(2),递归式,(3),制定目标,(4),贪心方案,当然，经过分析直接概括出高度抽象的数学公式亦是一种归纳过程、一种解题的途径。但是怎样进行这种归纳，这个问题太宽泛，与其说它是计算机算法的策略，还不如说它是一种数学知识和数学能力，取决于解题者本身的数学功底。我们已经在,“,对应策略,”,一节中，对如何将试题与数学公式对应的问题作了一些讨论，这里不再赘述,。,一、递推法,瞬息变幻的世界，每一件事物都在随时间的流逝发生着微妙的变化。而在这纷繁的变幻中，许多现象的变化是有规律的，这种规律往往呈现出前因和后果的关系。即某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。所谓,“,三岁看老,”,，说的就是这个道理。这一道理也正体现了递推的思想。递推关系几乎在所有的数学分支中都有重要作用，在联赛中更因其简捷高效而显示出独特的魅力。,1.,递推关系的定义和求解方法,有一类试题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如下简捷的递推关系式：,f,n,=g(f,n-1,),或者,f,n-1,=g,(f,n,),这样就在数的序列中，建立起后项和前项之间的关系。然后从初始条件,(,或最终结果,),入手，一步步地按递推关系式递推，直至求出最终结果,(,或初始值,),。很多程序就是按这样的方法逐步求解的。如果对一个试题，我们要是能找到后一项数与前一项数的关系并清楚其起始条件（或最终结果），问题就比较容易解决，让计算机一步步计算就是了。让高速的计算机从事这种重复运算，可真正起到,“,物尽其用,”,的效果,。,顺推法,就是由边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推出再后项值，依次递推，直到从问题初始陈述向前推进到这个问题的解为止。,倒推法,就是在不知初始值的情况下，经推理而获知问题的最终解或目标，再倒过来，推知它的初始条件。因为这种问题的运算过程是一一映射的，故可分析其倒推公式。然后再从最终解或目标出发，采用倒推手段，一步步地倒推到这个问题的初始陈述。,递推分倒推法和顺推法两种形式：,一般分析思路：,if(,求解初始条件,f,1,)/,倒推,由题意,(,或递推关系,),确定最终结果,f,n,;,求出倒推关系式,f,i-1,=g,(f,i,);,for(i=n;i=2;i-)f,i-1,=g,(f,i,);,/,从最终结果,f,n,进行倒推,推出倒推结果,f,1,;,else /,顺推,由题意,(,或递推关系,),确定初始值,f,1,(,边界条件,);,求出顺推关系式,f,i,=g(f,i-1,);,for(i=2;i=2),个盘子时，总是先借助,c,柱把上面的,n-1,个盘子移动到,b,柱上，然后把,a,柱最下面的盘子移动到,c,柱上；再借助,a,柱把,b,柱上的,n-1,个盘子移动到,c,柱上；总共移动,h,n,=2h,n-1,+1,边界条件：,h,1,=1,(3,）平面分割问题,设有,n,条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。,分析：设,an,为,n,条封闭曲线把平面分割成的区域个数。由图可得,:a2-a1=2;a3-a2=4;a4-a3=6,。,从这些式子中可以看出,a,n,-a,n-1,=2(n-1),当然，上面的式子只是我们通过观察,4,幅图后得出的结论，它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有,n-1,条曲线将平面分割成,a,n-1,个区域后，第,n,条曲线每与其他曲线相交一次，就会增加一个区域，因为平面上已经有了,n-1,条封闭曲线，且第,n,条曲线与己有的每一条闭曲线恰好相交于两点，不会与任两条曲线交于同一点，故平面上一共增加,2(n-1),个区域，加上已有的,a,n-1,个区域，一共有,a,n-1,+2(n-1),个区域。所以本题的递推关系是,a,n,=a,n-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(1k1,m=1),边界条件为：,S,2,(n,0)=0,S,2,(n,1)=1,，,S,2,(n,n)=1,S,2,(n,k)=0 (kn),第二类,stirling,数在竞赛中较少出现，但在竞赛中也有一些题目与其类似，甚至更为复杂。读者不妨自己来试着建立其中的递推关系。,通过上面对五种典型的递推关系建立过程的探讨，可知对待递推类的题目，要具体情况具体分析，通过找到某状态与其前面状态的联系，建立相应的递推关系。,3,递推关系的应用,递推关系的应用十分广泛，其中一个非常重要的应用就是著名的杨辉三角（又称,“,Pascal,三角,”,。杨辉三角是根据组合公式,C,n,r,=C,n-1,r,+C,n-1,r-1,画出来的。很显然，组合公式、杨辉三角都属于递推关系的范围。,在今天的信息学竞赛中，递推关系的应用也日趋广泛，下面就让我们从近年来的两道竞赛题中体会递推关系的应用。,【,例,13】,蜜蜂爬行,有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行，如图所示。,试求出蜜蜂从蜂房,a,爬到蜂房,b,的可能路线数,分析：这是一道很典型的,Fibonacci,数列类题目，其中的递推关系很明显。由于,“,蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行,”,的限制，决定了蜜蜂到,n,点的路径只能是从,n-1,点或,n-2,点到达的，故,:,f,n,=f,n-1,+f,n-2,(a+2=n=b),边界条件为,f,a,1,，,f,a+1,1.,【,例,14】,分割平面,同一平面内的,n(n=2),条直线相交于同一点，则这,n,条直线最多能将平面分割成多少个不同的区域？,分析：直线的平面分割与封闭曲线的平面分割十分相似，不同之处就在于线条的曲直以及是否存在共点的直线。由于共点直线的特殊性，我们决定先考虑,p,条相交于一点的直线，然后再考虑剩下的,n-p,条直线。,首先可以直接求出,p,条相交于一点的直线将平面划分成的区域数为,2*p,个,然后在平面上已经有,k(k=p),条直线的基础上，加上一条直线，最多可以与,k,条直线相交，而每次相交都会增加一个区域,与最后一条直线相交后，由于直线可以无限延伸，还会再增加一个区域。,所以,f,m,=f,m-1,+m(mP),，,边界条件在前面己经计算过了，是,f,p,=2*p,。,虽然这题看上去有两个参数，但是在实际做题中会发现，本题还是属于带一个参数的递推关系,。,【,例,15】,平面分割空间问题,一个平面把空间分成独立的两个部分，两个平面把空间分成,4,个部分。,n,个平面，最多能把整个空间分割成多少个部分。,分析：立体空间的情况是陌生的，但是空间和平面的关系与平面和直线的关系是相似的。平面把空间分割成两个部分，直线也把平面分割成两个部分。于是得到了另一个与例题相类似的问题：,n,条直线，最多能把整个平面分割成多少个部分，如图所示。,一条直线,把平面分割为两个部分,;,增加一条直线，它与第一条直线相交,被分为两段射线，每一段射线又把所在的区域分成两部分,;,因此增加了,2,个部分。再增加一条直线，它与前两条直线相交，被分为三段，每一段又把所在区域分成两部分,;,共增加了,3,个部分。,由此类推，设前,k-1,条直线共把平面分为,a,k-1,个部分。加入第,k,条直线，与前,k-1,条直线相交，被分为,k,段，每一段把所在区域分为两部分；总共增加了,k,部分；总共有,a,k-1,+k,个部分。于是得到了递推关系,:,a,1,=2;a,k,=a,k-1,+k;,即,a,k,=1+k*(1+k)/2,于是直线分割平面的问题就解决了。,既然空间和平面，与平面和直线的关系相似，那么直接把平面换成空间，把直线换成平面，就可以直接用以上的过程来证明未知的问题了吗？,显然是不可以的，这种仅仅根据主观的相似性得出的机械模仿是错误的。,但是如果仔细分析一下错误的原因，将会发现问题的关键,:,线线相交得到的是交点,面面相交得到的是直线,k,个点把直线分成,k+1,个部分,而,k,条直线则不是简单的把平面分成,k+1,个部分。事实上,k,条直线最多把平面分成,a,k,个部分！,因此两个问题真正的相似之处在于，一个为了计算直线把平面分割成几部分，先计算这条直线被点（线线交点）分割成几部分，把二维的问题化为一维的问题；另一个要计算平面把空间分割成几部分，先计算这个平面被线（面面交线）分割成几部分，把三维的问题化为二维的问题。而二维的问题是已经被解决了的，于是反过来，三维的问题也解决了。,同样是利用数学归纳法：,一个平面把空间分割成两部分；设前,k-1,个平面共把空间分割成,b,k-1,个部分。加入第,k,个平面后，与前,k-1,个平面相交，共有,k-1,条交线。,k-1,条交线把这个平面分为几块呢？这买际上就是刚刚解决过的回题：,k-1,条直线，把平面分割成：,a,k-1,=1+k*(1+k)/2,分别把所在原来空间一分为二，总共增加了,a,k-1,个部分，于是平面总共把空间分割成,个部分。于是得到了递推关系：,利用这一递推关系来编写程序，不难求出,bn,，而且即便对很大的,n,，程序的运算速度仍然是很快的。（当然，也可以计算出,bn,的通项公式,:,二、递归法,设一个未知函数,f,，用其自身构成的已知函数,g,来定义：,f(n)=g(n,f(n-1)n0,f(0)=a n=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=4 g4=1,当相交时,(n-2)x2+1=5 g5=1,(4),四条直线互不平行，交点数为：,1+2+3=6 g6=1,即,n=4,时，有,0,、,3,、,4,、,5,、,6,个不同的交点数,由此得出：,m,条直线的交点方案,=,r,条平行线与,(m-r),条直线交叉的交点数,+,(m-r),条直线本身的交点方案,=(m-r)r,+,(m-r),条直线本身的交点数,(1=r0),/,若直线存在，则递归计算所有的交叉情况,for(int r=m;r=1;r-)cross(m-r,j+r*(m-r);,else,/,否则确定,m,条直线存在,j,个交点,gj=1;,计算和输出,n,条直线的交点方案如下：,#include,using namespace std;,const int MAX=10000;,static int gMAX;,void main(),int n,k,total=0;,cinn;,k=n*(n-1)/2;,cross(n,0);,for(int i=0;i=k;i+),if(gi=1)total+;coutiendl;,三、制定目标,有些问题看似棘手，主要是没有找到解决问题的路子，或者说目标不明确。一旦建立了评判好坏的标准,(,目标函数或者目标方案,),，求解问题的算法也就自然而然地产生了。关键是建立标准。而这个标准是通过对实际问题的分析与归纳得到的。因此，我们将之划入归纳的范畴。,【,例,17】,最优分解方案,把正整数,n,分解成若干个互不相等的自然数的和，且使这些自然数的乘积最大。请你编写一个算法，由键盘输入,n,求满足条件的分解方案。,输入：,n(3=n=1000),输出：乘积,分析：如何把正整数,n,分解成若干互不相等的自然数的和，且使这些自然数的乘积最大呢？如果我们对这个问题不探究解析方法而去盲目搜索所有分解方案的话，则代价相当大。但是如果我们一旦耐心地对问题认真思考一番，是不难得出其中隐含着的数学规律的。设：,由于,1=a,1,a,2,1,。很明显，要使得乘积,a,1,a,2,a,n,最大，则必须使得项数,n,最大，且相邻两数,a,i+1,-a,i,的差最小，这就是解决问题的目标方案。,为了达到这个目标，我们不妨设,a1=2(,因为,a1=1,时,a1,在乘式中无意义），先求出：,n=2+3+4+,+a,k,+a,k+1,a,k,=a,k+1,这种分解方案的项数无疑最多。问题是要保证,a,k+1,=a,k,a,k+1,要么为,1,要么重复其中某一项，因此必须撤去。为了保证撤去,a,k+1,后的各个自然数依然互不相等，其和还是等于,n,且乘积最大，我们将,a,k+1,尽量平均地加在后几项。并尽可能使得相邻两数的差不超过,2,若,a,k+1,=1,由于,1x2x,xa,k,2x3x,x(a,k,+1),，因此,a,k+1,=1,加到,a,k,上；,若,1a,k+1,n;,if(n=3)|(n=4)mul=1*(n-1);,/,当,n=3,或,4,时，输出分解方案,。,else,int k=1;ak=2;n=n-ak;,/,从,2,开始分解,while(nak),/,分解直到,ak+1=ak,k+;ak=ak-1+1;n=n-ak;,if(n=1)ak+;n-;,/ak+1=1,else,if(n=ak),/ak+1=ak,ak+;n-;,/1ak+1ak,for(int i=0;i=n-1;i+)ak-i+;,for(int i=1;i=k;i+)mul=mul*ai;,coutmul;,四、贪心法,和前面所讲的递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标推进。但不同的是，推进的每一步不是依据某一固定的递推式，而是做一个当时看似最佳的贪心选择，不断地将问题实例归纳为更小的相似的子问题，并期望通过所做的局部最优选择产生出一个全局最优解。对于贪心法，我们并不陌生。例如求最小生成树、求单源最短路径使用的算法策略实际上就是贪心法。,贪心法建议通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完整解为止。这个问题的核心是，所做的每一步选择都必须满足以下条件：,可行的：即它必须满足问题的约束。,局部最优：它是当前步骤中所有可行选择中最佳的局部选择,不可取消：即选择一旦做出，在算法的后面步骤中就无法改变。,在每一步中，它要求,“,贪婪,”,地选择最佳操作，并希望通过一系列局部的最佳选择，能够产生一个整个问题的（全局的）最佳解。,那么如何证明按贪心选择得出的解是最优解呢？有两种方法：,(1),对贪心选择进行数学分析，从理论上证明是最优的。,(2),构造一个最优解，然后对该解进行修正，使其第一步为一个贪心选择，证明总是存在一个以贪心选择开始的求解方案，然后证明经过若干次贪心选择后可以得出一个最优解。,第二种证明方法相对比较容易。,由于贪心选择的设计及其产生最优解的证明是对实际问题分析归纳的结果,.,因此,我们将贪心法列为一种归纳策略。,【,例,18】,活动选择,假设有一个需要使用某一资源的,n,个活动组成的集合,S=1,n,。该资源一次只能被一个活动所占用，每一个活动有一个开始时间,Si,和结束时间,Fi(Si=Fj,或者,Sj=Fi,，则活动,i,和活动,j,兼容。选择由互相兼容的活动组成的最大集合。,输入：,n,S1 F1,Sn Fn,输出：占用时间,t,最大集合,A,中的活动序号,分析：我们使用尽可能逼近目标的贪心策略来选择活动，即每一步总是选择这样一个活动来占用资源,它能够使得余下的未调度时间最大化，使得兼容的活动尽可能多。为了达到这个目的，我们将,n,个待选活动按结束时间递增的顺序排列：,F1=F2=,=Fn,递增序列中的活动,1,进入集合,A,。然后依次分析序列中的活动,2,到活动,n,，将那些与,A,中活动兼容的活动送入集合,A,。,例如,活动 开始时间 结束时间,1 3 5,2 1 4,3 12 14,4 8 12,5 0 6,6 8 11,7 6 10,8 5 7,9 3 8,10 5 9,11 2 13,#include,using namespace std;,const int N=11;,/,活动序号,int noN=1,2,3,4,5,6,7,8,9,10,11;,/,开始时间,int sN=3,1,12,8,0,8,6,5,3,5,2;,/,结束时间,int fN=5,4,14,12,6,11,10,7,8,9,13;,void swap(int&x,int&y),int temp=x;x=y;y=temp;,/,选择排序,void sort(),for(int i=0;iN-1;i+),int min=i;,for(int j=i+1;jfj)min=j;,swap(fmin,fi);,swap(nomin,noi);,swap(smin,si);,void main(),static int aN;/a,是兼容集合,int t=0;/t,是占用时间,sort();/,按结束时间递增的顺序排序,int k=0;int j=0;ak=no0;,/,初始活动表为,NO0,for(int i=1;i=fj),k+;ak=noi;t=fi;j=i;,couttendl;,for(i=0;i=k;i+)coutai ;,贪心选择的过程,t=14 a=2,8,6,3,我们使用第二种方法证明按照这个贪心选择的解一定是最优的：,(1),构造一个最优解，然后对该解进行修正，使其第一步为一个贪心选择，证明总是存在一个以贪心选择开始的求解方案。,设最优解为,a,。第一个选中的活动为,k(k,不等于,1),。如果另一个解,b,开始于贪心选择活动,1(b=(a-k)U1),。因为,f1=5*a4,则这些空间全部用掉，否则剩下的空间还可以,“,见缝插针,”,地放入,1x1,的盒子。由此可得等式：,(4),已知每个箱子可以放,4,个,3x3,的盒子。这样,4,个,4,个放完后，可能还剩余,0,1,2,3,个,3x3,的盒子。与放置,4x4,的盒子时同样的原理，还是先放,2x2,的盒子,再放,1x1,的盒子。,在这,4,种情况下分别还能放,0,1,3,5,个,2x2,的盒子。剩余的空间再放入,1x1,的盒子。,(5),一个箱子可放,9,个,2x2,的盒子，放完,2x2,的盒子后，多余的空间放,1x1,的盒子。等式如下：,(6),放置,1x1,的盒子时有关系式,(,图,j),：,这六个等式的顺序即为贪心策略。由此证明贪心法可以求得最优解,int pack(int a1,int a2,int a3,int a4,int a5,int a6),int c=a6;,c=c+a5;/,加上放入,6x6,5X5,的盒子数,a1=max(0,a1-11*a5);,c=c+a4;,if(a2=5*a4),a2=a2-5*a4;,else,a1=max(0,a1-(20*a4-4*a2);,a2=0;,if(a3%4=0)c=c+a3/4;,else c=c+a3/4+1;,if(a3%4=3),a1=max(0,a1-(9-4*min(1,a2);,a2=max(0,a2-1);,else if(a3%4=2),a1=max(0,a1-(18-4*min(3,a2);,a2=max(0,a2-3);,else a1=max(0,a1-(27-4*min(5,a2);,a2=max(0,a2-5);/a3%4=1,if(a2%9=0)c=c+a2/9;,else c=c+a2/9+1;,if(a2%9!=0),a1=max(0,a1-(36-4*(a2%9);,if(a1%36=0)c=c+a1/36;,else c=c+a1/36+1;,return c;,#include,using namespace std;,inline int max(int a,int b),return ab?a:b;,inline int min(int a,int b),return aa1a2a3a4a5a6;,couta1a2a3a4a5a6),if(a1=0)&(a2=0)&(a3=0)&,(a4=0),c=a6+a5+a4+ceil(a3/4.0);y=5*a4+ua3%4;,if(a2y)c+=ceil(a2-y)/9.0);,x=36*c-36*a6-25*a5-16*a4-9*a3-4*a2;,if(a1x)c+=ceil(a1-x)/36.0);,coutcendl;,return 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(0 m,n nm;,if(n=0)break;,for(i=0;in;i+),loopi=i+1;,int nPtr=0;,for(i=0;in;i+),int nCount=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(int i=0;iID=i+1;,if(link=NULL)link=lastMonkey=monkey;,else lastMonkey-next=monkey;lastMonkey=monkey;,lastMonkey-next=link;,count=1;,while(link!=NULL),if(link-next=link),coutID;,delete link;break;,if(count=m-1),monkey=link-next;,link-next=monkey-next;,delete monkey;,count=0;,link=link-next;,count+;,return 0;,【,例,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,指令，因此次数上限为,2,6,=64,。我们可以用数组来表示多项式，既方便又不会导致时间和空间上的问题。,(2),本题也没有说明系数的最大值。稍微细心的选手会发现：它最大可能为,2,32,未超过长整数的范围，不存在非得用高精度的必要。,#include,#include,void main(),static int degree13;/,存储系数个数的栈,static long co1365;/,存储多项式的栈,long tmp65;/,系数序列,char s13;/DAM,程序,int i,j;,int top=1;/,栈顶指针,degree1=1;,co11=1;,cins;,for(i=0;istrlen(s);i+),switch(si),case D:,top+;,degreetop=degreetop-1;,for(j=0;j=degreetop;j+),cotopj=cotop-1j;,break;,case A:,top-;,if(degreetop=degreetop+1),degreetop=degreetop+1;,for(j=0;j=degreetop;j+)cotopj=cotopj+cotop+1j;,break;,case M:,top-;,for(j=0;j65;j+)tmpj=0;,int d=degreetop+degreetop+1;,for(int a=0;a=degreetop;a+),for(int b=0;b=degreetop+1;b+),tmpa+b=tmpa+b+cotopa*cotop+1b;,degreetop=d;,for(j=0;j=1;i-),if(cotopi!=0),if(first)first=false;,else cout+;,if(cotopi!=1.0)coutcotopi;,cout1)couti;,cout=f(xi),，则该点从筛中过滤掉。,最后有,m,个随机数点留在筛中,(,这些随机数点落在曲边梯形,abfe,内,),。曲边梯形,abfe,面积应该为,m,和,n,的比值乘以长方形,abcd,的面积：,按照定积分的几何定义，,s,即为定积分的值,#include,#include,#include,const int MAX=100;/f(x),函数的最大次数,double amoncar(int a,int b,int d,double co,int n),int m=0;,for(int i=0;i=0;j-)f=f+coj*pow(x,j);,if(yabdn;,while(cincoi+);,coutamoncar(a,b,d,co,n);,在主程序中，输入随机点的个数,n,以及,a,b,d,等,调用函数,amoncar,计算和输出定积分的值。,注意，,n,愈大，定积分的值愈精确，速度愈慢。,三、构造法模拟,构造法模拟需要完整精确地构造出反映问题本质的数学模型，根据该模型设计状态变化的参数，计算模拟结果。,由于数学模型建立了客观事物间准确的运算关系，因此其效率一般比较高。构造法模拟的关键是找到数学模型。问题是，能产生正确结果的数学模型并不是惟一的，从不同的思维角度看问题，可以得出不同的数学模型，而模拟效率和编程复杂度往往因数学模型而异。即便有数学模型，但解该模型的准确方法是否有现成算法、编程复杂度如何，这些都是我们要考虑的问题。,本节作业与练习,一、简要回答如下问题：,模拟策略主要有哪两种形式？,模拟解题方法一般有三种类型？,二、给出下列问题的解题思路及算法实现,【,例,20】DAM,语言,【,例,21】,蒙特卡洛法,