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

《信息学奥林匹克竞赛辅导归纳策略》由会员分享，可在线阅读，更多相关《信息学奥林匹克竞赛辅导归纳策略（121页珍藏版）》请在装配图网上搜索。

1、 归纳法要比搜索的方法（例如以后将讲解的枚举法、回溯法等）更能反映问题的本质。但是并不是所有实际问题都可以总结归纳出一般规律，即便是可以，归纳也不是一件容易的事情，尤其要归纳出一个数学模型更为困难。而且归纳过程通常没有一定的规则可供遵循。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径。第1页/共121页 通常，归纳的过程分四个步骤：(1)细心的观察(2)丰富的联想(3)继续尝试(4)总结归纳出结论第2页/共121页 归纳是一种抽象，即从特殊现象中找出一般关系。但在归纳过程中不可能列举所有情况，因而最后得出的结论还只是一种猜测（即归纳假设）。通过精心观

2、察而提出的归纳假设得不到证实或最后证明是错的，也是常有的事。因此要尽可能对归纳假设加以严格的证明，证明的方法通常使用数学归纳法。即便找不到证明方法，也必须尽可能多地提出那些容易出错和疏漏的边界情况加以验证，使归纳出的结论和解决问题的途径经得起各种测试数据的检验。第3页/共121页问题经过分析归纳后，一般产生四种结果：(1)递推式(2)递归式(3)制定目标(4)贪心方案第4页/共121页 当然，经过分析直接概括出高度抽象的数学公式亦是一种归纳过程、一种解题的途径。但是怎样进行这种归纳，这个问题太宽泛，与其说它是计算机算法的策略，还不如说它是一种数学知识和数学能力，取决于解题者本身的数学功底。我们

3、已经在“对应策略”一节中，对如何将试题与数学公式对应的问题作了一些讨论，这里不再赘述。第5页/共121页一、递推法 瞬息变幻的世界，每一件事物都在随时间的流逝发生着微妙的变化。而在这纷繁的变幻中，许多现象的变化是有规律的，这种规律往往呈现出前因和后果的关系。即某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。所谓“三岁看老”，说的就是这个道理。这一道理也正体现了递推的思想。递推关系几乎在所有的数学分支中都有重要作用，在联赛中更因其简捷高效而显示出独特的魅力。第6页/共121页1.递推关系的定义和求解方法 有一类试题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如下简捷

4、的递推关系式：fn=g(fn-1)或者fn-1=g(fn)这样就在数的序列中，建立起后项和前项之间的关系。然后从初始条件(或最终结果)入手，一步步地按递推关系式递推，直至求出最终结果(或初始值)。很多程序就是按这样的方法逐步求解的。如果对一个试题，我们要是能找到后一项数与前一项数的关系并清楚其起始条件（或最终结果），问题就比较容易解决，让计算机一步步计算就是了。让高速的计算机从事这种重复运算，可真正起到“物尽其用”的效果。第7页/共121页顺推法就是由边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推出再后项值，依次递推，直到从问题初始陈述向前推进到这个问题的解为止。倒推法就是在

5、不知初始值的情况下，经推理而获知问题的最终解或目标，再倒过来，推知它的初始条件。因为这种问题的运算过程是一一映射的，故可分析其倒推公式。然后再从最终解或目标出发，采用倒推手段，一步步地倒推到这个问题的初始陈述。递推分倒推法和顺推法两种形式：第8页/共121页一般分析思路：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

6、)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动 h hn n=2h=2hn-1n-1+1 +1 边界条件：边界条件：h h1 1=1=1第18页/共121页(3）平面分割问题 设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。分析：设an为n条封闭曲线把平面分割成的区域个数。由图可得:a2-a1=2;a3-a2=4;a4-a3=6。第19页/共121页从这些式子中可以看出 an-an-1=2(n-1)当然，上

7、面的式子只是我们通过观察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。第20页/共121页平面分割问题是竞赛中经常触及到的一类问题，由于其灵活多变，常常让选手感到棘手，下题是另一种平面分

8、割问题，有兴趣的读者不妨自己先试着求一下其中的递推关系。第21页/共121页(4)Catalan 数在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用 hn表之，hn即为Catalan数。例如五边形有如图所示的五种拆分方案，故h5=5。求对于一个任意的凸n边形相应的hn。Catalan 数首先是由Euler在精确计算对凸n边形不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。第22页/共121页分析：设Cn表示凸n边形的拆分方案总数。由题目中的要求可知一个凸n边形的任意一条边都必然是一个三角形的一条边，边P1Pn也不例外，再根据“不在

9、同一直线上的三点可以确定一个三角形”，只要在P2，P3，Pn-1，点中找一个点Pk(1k1,m=1)边界条件为：S2(n,0)=0S2(n,1)=1，S2(n,n)=1S2(n,k)=0 (kn)第28页/共121页第二类 stirling 数在竞赛中较少出现，但在竞赛中也有一些题目与其类似，甚至更为复杂。读者不妨自己来试着建立其中的递推关系。通过上面对五种典型的递推关系建立过程的探讨，可知对待递推类的题目，要具体情况具体分析，通过找到某状态与其前面状态的联系，建立相应的递推关系。第29页/共121页3递推关系的应用递推关系的应用十分广泛，其中一个非常重要的应用就是著名的杨辉三角（又称“Pas

10、cal三角”。杨辉三角是根据组合公式Cnr=Cn-1r+Cn-1r-1画出来的。很显然，组合公式、杨辉三角都属于递推关系的范围。第30页/共121页在今天的信息学竞赛中，递推关系的应用也日趋广泛，下面就让我们从近年来的两道竞赛题中体会递推关系的应用。第31页/共121页【例13】蜜蜂爬行有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行，如图所示。试求出蜜蜂从蜂房a 爬到蜂房b 的可能路线数 第32页/共121页分析：这是一道很典型的Fibonacci数列类题目，其中的递推关系很明显。由于“蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行”的限制，决定了蜜蜂到 n 点的路径只能是从 n-1 点或

11、 n-2 点到达的，故:fn=fn-1+fn-2 (a+2=n=b),边界条件为 fa1，fa+11.第33页/共121页【例14】分割平面同一平面内的n(n=2)条直线相交于同一点，则这n条直线最多能将平面分割成多少个不同的区域？分析：直线的平面分割与封闭曲线的平面分割十分相似，不同之处就在于线条的曲直以及是否存在共点的直线。由于共点直线的特殊性，我们决定先考虑p条相交于一点的直线，然后再考虑剩下的n-p条直线。第34页/共121页首先可以直接求出p条相交于一点的直线将平面划分成的区域数为2*p个然后在平面上已经有k(k=p)条直线的基础上，加上一条直线，最多可以与k条直线相交，而每次相交都

12、会增加一个区域,与最后一条直线相交后，由于直线可以无限延伸，还会再增加一个区域。所以 fm=fm-1+m(mP)，边界条件在前面己经计算过了，是fp=2*p。虽然这题看上去有两个参数，但是在实际做题中会发现，本题还是属于带一个参数的递推关系。第35页/共121页【例15】平面分割空间问题一个平面把空间分成独立的两个部分，两个平面把空间分成4个部分。n个平面，最多能把整个空间分割成多少个部分。分析：立体空间的情况是陌生的，但是空间和平面的关系与平面和直线的关系是相似的。平面把空间分割成两个部分，直线也把平面分割成两个部分。于是得到了另一个与例题相类似的问题：n条直线，最多能把整个平面分割成多少个

13、部分，如图所示。第36页/共121页第37页/共121页一条直线,把平面分割为两个部分;增加一条直线，它与第一条直线相交,被分为两段射线，每一段射线又把所在的区域分成两部分;因此增加了2个部分。再增加一条直线，它与前两条直线相交，被分为三段，每一段又把所在区域分成两部分;共增加了3个部分。由此类推，设前k-1条直线共把平面分为ak-1个部分。加入第k条直线，与前k-1条直线相交，被分为k段，每一段把所在区域分为两部分；总共增加了k部分；总共有ak-1+k个部分。于是得到了递推关系:第38页/共121页a1=2;ak=ak-1+k;即 ak=1+k*(1+k)/2于是直线分割平面的问题就解决了。

14、既然空间和平面，与平面和直线的关系相似，那么直接把平面换成空间，把直线换成平面，就可以直接用以上的过程来证明未知的问题了吗？显然是不可以的，这种仅仅根据主观的相似性得出的机械模仿是错误的。第39页/共121页但是如果仔细分析一下错误的原因，将会发现问题的关键:线线相交得到的是交点,面面相交得到的是直线,k个点把直线分成k+1个部分,而k条直线则不是简单的把平面分成k+1个部分。事实上,k条直线最多把平面分成ak个部分！因此两个问题真正的相似之处在于，一个为了计算直线把平面分割成几部分，先计算这条直线被点（线线交点）分割成几部分，把二维的问题化为一维的问题；另一个要计算平面把空间分割成几部分，先

15、计算这个平面被线（面面交线）分割成几部分，把三维的问题化为二维的问题。而二维的问题是已经被解决了的，于是反过来，三维的问题也解决了。第40页/共121页 同样是利用数学归纳法：一个平面把空间分割成两部分；设前k-1个平面共把空间分割成 bk-1个部分。加入第k个平面后，与前k-1个平面相交，共有k-1条交线。k-1 条交线把这个平面分为几块呢？这买际上就是刚刚解决过的回题：k-1条直线，把平面分割成：ak-1=1+k*(1+k)/2 分别把所在原来空间一分为二，总共增加了ak-1个部分，于是平面总共把空间分割成 个部分。于是得到了递推关系：第41页/共121页利用这一递推关系来编写程序，不难求

16、出 bn，而且即便对很大的 n，程序的运算速度仍然是很快的。（当然，也可以计算出 bn的通项公式:第42页/共121页二、递归法设一个未知函数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，是最简单的情况，称为递归边界，它本身不再使用递归的定义。第43页/共12

17、1页 与递推一样，每一个递归定义都有其边界条件。但不同的是，递推是由边界条件出发，通过递推公式求f(n)的值，从边界到求解的全过程十分清楚；而递归则是从函数自身出发来达到边界条件。在通往边界条件的递归调用过程中，系统用堆栈把每次调用的中间结果保存在栈区，直至求出递归边界值f(0)=a。然后返回调用函数。返回过程中，中间结果相继出栈恢复，f(1)=g(1,a)f(2)=g(2,f(1)直到 f(n)=g(n,f(n-1)描述递归定义的函数或求解递归问题的过程称为递归算法。一个递归算法，本质上是将较复杂的处理归结为简单处理，直到最简单的处理。第44页/共121页 从实际问题中抽象递归定义和边界条件

18、的过程是一种归纳，通过这种归纳方式能使一个蕴含递归关系且结构复杂的程序简捷精炼，增加可读性。特别是在难于找到从边界到解的全过程的情况下，如果把问题推进一步，其结果仍维持原问题的关系，则采用递归算法编程比较合适。但递归算法也有致命的缺点，其执行的效率比较低，尤其在边界条件设置不当的情况，极有可能陷入死循环或者内存溢出的窘境。第45页/共121页递归算法适用的一般场合为：(1)数据的定义形式按递归定义。这类递归问题可直接转化为递推算法，递归边界作为递推的边界条件。(2)数据之间的关系(即数据结构)按递归定义。如树的遍历，图的搜索等。(3)有些问题本身没有明显的递归结构，但使用递归求解比其他方法更简

19、单。如递归的分治策略。对于(2)、(3)，可利用堆栈结构将其转换为非递归算法，但结构不如递归算法简单清晰，可读性较差。第46页/共121页 编写递归程序时应注意如下几个问题：(1)问题的递归定义，即如何用自身的简单情况定义自己；(2)递归边界，即递归至哪个边界值后开始回溯；(3)参与递归运算的变量有哪些，其中哪些作为值参，哪些作为局部变量。如果有全局变量参与递归运算的话(初始值由主程序传入，受内存限制不便作为值参)，回溯过程中必须恢复其递归前状态。第47页/共121页【例16】计算交点数 在平面上有 n 条直线，且无三线共点。问这些直线能有多少种不同的交点数？输入：n 输出：以下若干行列出所有

20、相交方案。其中每一行为某一方案的交点个数。分析：我们将n条直线排成一个序列。直线2与直线1最多有一个交点；直线3与直线1和直线2最多有2个交点，直线n与其他n-1条直线最多有n-1个交点。由此得出n条直线互不平行且无三线交于一点的最多交点数中1+2+，+(n-1)=n*(n-1)/2.第48页/共121页设第49页/共121页我们来具体分析 n=4 的情况(1)四条直线全部平行，无交点，g0=1(2)其中三条(n-1)直线平行，交点数为 (n-1)x1+0=3,g3=1(3)其中两条(n-2)直线平行，这两条直线与另外两条直线之间的交点数为(n-2)x2=4而另外两条直线本身既可能平行也可能相

21、交，因此交点数分别为：当平行时(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 个不同的交点数 第50页/共121页由此得出：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;第52页/共121页计算和输出 n 条直

22、线的交点方案如下：#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;第53页/共121页三、制定目标 有些问题看似棘手，主要是没有找到解决问题的路子，或者说目标不明确。一旦建立了评判好坏的标准(目标函数或者目标方案)，求解问题的算法也就自然而然地产生了。关键是建立标准。而这个标准是通过对实际问题的分析与归纳得到的。因此，

23、我们将之划入归纳的范畴。第54页/共121页【例17】最优分解方案 把正整数n分解成若干个互不相等的自然数的和，且使这些自然数的乘积最大。请你编写一个算法，由键盘输入n,求满足条件的分解方案。输入：n(3=n=1000)输出：乘积 分析：如何把正整数n分解成若干互不相等的自然数的和，且使这些自然数的乘积最大呢？如果我们对这个问题不探究解析方法而去盲目搜索所有分解方案的话，则代价相当大。但是如果我们一旦耐心地对问题认真思考一番，是不难得出其中隐含着的数学规律的。设：第55页/共121页由于 1=a1 a21。很明显，要使得乘积 a1a2 an最大，则必须使得项数n最大，且相邻两数ai+1-ai的

24、差最小，这就是解决问题的目标方案。第56页/共121页为了达到这个目标，我们不妨设a1=2(因为a1=1 时,a1在乘式中无意义），先求出：n=2+3+4+,+ak+ak+1 ak=ak+1这种分解方案的项数无疑最多。问题是要保证ak+1=ak,ak+1要么为1,要么重复其中某一项，因此必须撤去。为了保证撤去ak+1后的各个自然数依然互不相等，其和还是等于n且乘积最大，我们将 ak+1尽量平均地加在后几项。并尽可能使得相邻两数的差不超过2第57页/共121页若ak+1=1,由于1x2x,xak2x3x,x(ak+1)，因此ak+1=1加到ak上；若1ak+1ak,我们从ak出发，依次向尾部ak

25、+1个数加1;若ak+1=ak,则ak加上2,其余k-1个数依次加1;当然，还必须考虑一个例外情况：当n=3或n=4 时，只能分解出一个表达式：3=1+2 mul=1x2=2 4=1+3 mul=1x3=3 由此可见，上述目标方案是分解自然数的依据。第58页/共121页有了这个目标方案，相应的算法也就可以设计出有了这个目标方案，相应的算法也就可以设计出来了。来了。#include using namespace std;const int MAX=1000;static int aMAX;void main()int n,mul=1;cinn;if(n=3)|(n=4)mul=1*(n-1);

26、/当n=3或4时，输出分解方案。else 第59页/共121页 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;第60页/共121页四、贪心法 和前面所讲的递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标推进。但不同的是，推进的每一步不是依据某

27、一固定的递推式，而是做一个当时看似最佳的贪心选择，不断地将问题实例归纳为更小的相似的子问题，并期望通过所做的局部最优选择产生出一个全局最优解。对于贪心法，我们并不陌生。例如求最小生成树、求单源最短路径使用的算法策略实际上就是贪心法。第61页/共121页 贪心法建议通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完整解为止。这个问题的核心是，所做的每一步选择都必须满足以下条件：可行的：即它必须满足问题的约束。局部最优：它是当前步骤中所有可行选择中最佳的局部选择不可取消：即选择一旦做出，在算法的后面步骤中就无法改变。在每一步中，它要求“贪婪”地选择最佳操作，并希望通

28、过一系列局部的最佳选择，能够产生一个整个问题的（全局的）最佳解。第62页/共121页 那么如何证明按贪心选择得出的解是最优解呢？有两种方法：(1)对贪心选择进行数学分析，从理论上证明是最优的。(2)构造一个最优解，然后对该解进行修正，使其第一步为一个贪心选择，证明总是存在一个以贪心选择开始的求解方案，然后证明经过若干次贪心选择后可以得出一个最优解。第二种证明方法相对比较容易。由于贪心选择的设计及其产生最优解的证明是对实际问题分析归纳的结果.因此,我们将贪心法列为一种归纳策略。第63页/共121页【例 18】活动选择 假设有一个需要使用某一资源的n个活动组成的集合S=1,n。该资源一次只能被一个

29、活动所占用，每一个活动有一个开始时间Si和结束时间Fi(Si=Fj或者Sj=Fi，则活动i和活动j兼容。选择由互相兼容的活动组成的最大集合。输入：n S1 F1 Sn Fn输出：占用时间t 最大集合A中的活动序号第64页/共121页分析：我们使用尽可能逼近目标的贪心策略来选择活动，即每一步总是选择这样一个活动来占用资源它能够使得余下的未调度时间最大化，使得兼容的活动尽可能多。为了达到这个目的，我们将n个待选活动按结束时间递增的顺序排列：F1=F2=Fn 递增序列中的活动1进入集合A。然后依次分析序列中的活动2到活动n，将那些与A中活动兼容的活动送入集合A。第65页/共121页例如活动 开始时间

30、 结束时间 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第66页/共121页#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;第67页/共121页void swap(int&x,int&y)int temp=x;x=y;y=temp;/选

31、择排序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);第68页/共121页void main()static int aN;/a是兼容集合int t=0;/t是占用时间sort();/按结束时间递增的顺序排序int k=0;int j=0;ak=no0;/初始活动表为NO0for(int i=1;i=fj)k+;ak=noi;t=fi;j=i;couttendl;for(i=0;i=k;i+)coutai ;第69页/共121

32、页 贪心选择的过程 t=14 a=2,8,6,3第70页/共121页我们使用第二种方法证明按照这个贪心选择的解一定是最优的：(1)构造一个最优解，然后对该解进行修正，使其第一步为一个贪心选择，证明总是存在一个以贪心选择开始的求解方案。设最优解为a。第一个选中的活动为k(k不等于1)。如果另一个解b开始于贪心选择活动1(b=(a-k)U1)。因为f1=5*a4,则这些空间全部用掉，否则剩下的空间还可以“见缝插针”地放入1x1的盒子。由此可得等式：第79页/共121页(4)已知每个箱子可以放4个3x3的盒子。这样4个4个放完后，可能还剩余0,1,2,3个3x3的盒子。与放置 4x4 的盒子时同样的

33、原理，还是先放2x2的盒子,再放1x1的盒子。第80页/共121页在这4种情况下分别还能放 0,1,3,5个2x2的盒子。剩余的空间再放入1x1的盒子。第81页/共121页(5)一个箱子可放9个2x2的盒子，放完 2x2 的盒子后，多余的空间放 1x1 的盒子。等式如下：第82页/共121页(6)放置 1x1 的盒子时有关系式(图j)：这六个等式的顺序即为贪心策略。由此证明贪心法可以求得最优解 第83页/共121页int pack(int a1,int a2,int a3,int a4,int a5,int a6)int c=a6;c=c+a5;/加上放入6x6,5X5的盒子数 a1=max(

34、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;第84页/共121页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第85页/共121页 if(

35、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;第86页/共121页#include using namespace std;inline int max(int a,int b)return ab?a:b;inline int min(int a,int b)return aa1a2a3a4a5a6;coutpack(a1,a2,a3,a4,a5,a6);第87页/共121页#include /优化#includ

36、e using namespace std;int main()int c,a1,a2,a3,a4,a5,a6,x,y;int u4=0,5,3,1;/当放3*3产品时剩余放2*2数while(cina1a2a3a4a5a6)if(a1=0)&(a2=0)&(a3=0)&(a4=0)&(a5=0)&(a6=0)break;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;ret

37、urn 0;第88页/共121页贪心算法的基本要素可以用贪心算法求解的问题一般具有两个重要的性质：贪心选择性质和最优子结构性质1.贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。贪心算法所做的贪心选择可以依赖于以往所做过的选择，但决不依赖于将来所做的选择，也不依赖于子问题的解。第89页/共121页 贪心算法通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。2.最优子结构性质：当一个问题的最优解包含其子

38、问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。第90页/共121页本节作业一、简要回答如下问题：简述归纳过程步骤？递推方法一般分析思路是什么？递归算法适用的一般场合是什么？简述贪心算法的基本要素第91页/共121页二、根据题意，建立如下问题的递推公式或递归公式？(1)Fibonacci 数列(2)Hanoi 塔问题(3)封闭曲线分割平面问题(4)Catalan 数(5)第二类 stirling 数【例13】蜜蜂爬行【例14】直线分割平面【例15】平面分割空间问题第92页/共121页第四节、模拟策略 在自然界和日常生活中，许多现

39、象具有不确定的性质，有些问题甚至很难建立数学模型，或者很难用计算机建立递推、递归、枚举、回溯等算法。在这种情况下，一般采用模拟策略。所谓模拟策略就是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。第93页/共121页模拟题没有固定的模式，一般形式有两种：(1)随机模拟：题目给定或者隐含某一概率。设计者利用随机函数和取整函数设定某一范围的随机值，将符合概率的随机值作为参数。然后根据这一模拟的数学模型展开算法设计。由于解题过程借助了计算机的伪随机数发生器，其随机的意义要比实际问题中真实的随机变量稍差一些，因此模拟效果有不确定的因素。第94页/共

40、121页(2)过程模拟：题目不给出概率，要求编程者按照题意设计数学模型的各种参数，观察变更这些参数所引起过程状态的变化，由此展开算法设计。模拟效果完全取决于过程模拟的真实性和算法的正确性，不含任何不确定因素。由于过程模拟的结果无二义性，因此竞赛大都采用过程模拟。第95页/共121页模拟的解题方法一般有三种类型：(1)直叙式模拟(2)筛选法模拟(3)构造法模拟 第96页/共121页一、直叙式模拟 直叙式模拟，即按照试题要求展开模拟过程。编程者要忠实于原题，认真审题，千万不要疏漏任何条件，精心设计方便模拟的数据结构。直叙式模拟的难度取决于模拟对象所包含的动态变化的属性个数，动态属性愈多，则难度愈大

41、。第97页/共121页【例 19】约瑟夫问题 有n只猴子，按顺时针方向围成一圈选大王（编号从1到n），从第1号开始报数，一直数到m，数到m的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入n，m后，输出最后猴王的编号。Input:每行是用空格分开的两个整数，第一个是 n,第二个是 m(0 m,n=300)。最后一行是：0 0 Output:对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号 第98页/共121页Sample Input6 212 48 30 0Sample Output517第99页/共121页解题思路

42、1：用数组loop来存放n个数，相当于n个数排成的圈，用整型变量nPtr指向当前数到的数组元素，相当于人的手指，划掉一个数就将该数置0，在数数时，要跳过为0的元素。当nPtr指向最后一个元素时再数下一个时则指向数组的头一个元素。第100页/共121页#includeconst int MAX=300;int loopMAX;void main()int n,m,i;while(1)cinnm;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(loopnPt

43、r=0)nPtr=(nPtr+1)%n;nCount+;nPtr=(nPtr+1)%n;nPtr-;if(nPtr0)nPtr=n-1;if(i=n-1)coutloopnPtr;loopnPtr=0;第101页/共121页采用循环链表实现如下#include 采用循环链表实现struct Monkey int ID;Monkey*next;int main()Monkey*link,*monkey,*lastMonkey;int n,m,count;cinnm;link=NULL;for(int i=0;iID=i+1;if(link=NULL)link=lastMonkey=monkey;

44、else lastMonkey-next=monkey;lastMonkey=monkey;lastMonkey-next=link;第102页/共121页 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;第103页/共121页【例 20】DAM 语言 有个机器执行一种DAM语言。该机器有一个栈，初始

45、时栈里只有一个元素x，随着DAM语言程序的执行，栈里的元素会发生变化。DAM语言有三种指令：D 指令：把栈顶元素复制一次加到栈顶。A 指令：把栈顶元素取出，加到新的栈顶元素中。M 指令：把栈顶元素取出，乘到新的栈顶元素中。第104页/共121页 如果执行A或M指令的时候栈内只有一个元素，则机器会发出错误信息。如果程序无误，那么执行完毕以后，栈顶元素应该是X的多项式，例如，程序 DADDMA 的执行情况为（栈内元素按照从底到顶的顺序从左至右排列，用逗号隔开）：第105页/共121页给出一段DAM程序，求出执行完毕后栈顶元素。输入：输入仅一行，包含一个不空的字符串s，长度不超过12，代表一段DAM

46、程序。输入程序保证合法且不会导致错误。输出：仅输出一行，即栈顶多项式。须按照习惯写法降幂输出，即等于1的系数不要打印，系数为0的项不打印，第一项不打印正号。一次方不打印“1”。分析：本题是一道“直叙式模拟”题，即按照 DAM指令的顺序模拟执行过程。在模拟的时候有些问题是需要注意的：第106页/共121页(1)多项式的表示方式。有的选手或许会觉得本题没有说明次数的上限，因此最好用链表做。其实完全没有必要。由于指令不超过12条，而D指令和A、M指令总数应该相等，因此最多有6条M指令，因此次数上限为26=64。我们可以用数组来表示多项式，既方便又不会导致时间和空间上的问题。(2)本题也没有说明系数的

47、最大值。稍微细心的选手会发现：它最大可能为232,未超过长整数的范围，不存在非得用高精度的必要。第107页/共121页#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;第108页/共121页for(i=0;istrlen(s);i+)switch(si)case D:top+;degreetop=degreetop-1;for

48、(j=0;j=degreetop;j+)cotop j=cotop-1 j;break;第109页/共121页case A:top-;if(degreetop=degreetop+1)degreetop=degreetop+1;for(j=0;j=degreetop;j+)cotop j=cotop j+cotop+1 j;break;第110页/共121页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+)tm

49、pa+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)，则该点从筛中过滤掉。第115页/共121页最后有m个随机数点留在筛中(这些随机数点落在曲边梯形abfe内)。曲边梯形abfe面积应该为m和n的比值乘以长方形abcd的面积：按照定积分的几何定义，s即为定积分的值 第116页/共121页#include#include#include const int

50、 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 愈大，定积分的值愈精确，速度愈慢。第118页/共121页三、构造法模拟 构造法模拟需要完整精确地构造出反映问题本质的数学模型，根据该模型设计状态变化的参数，计算模拟结果。由于数学模型建立了客观事物间准确的运算关系，因此其效率一般比较高。构造法模拟的关键是找到数学模型。问题是，能产生正确结果的数学模型并不是惟一的，从不同的思维角度看问题，可以得出不同的数学模型，而模拟效率和编程复杂度往往因数学模型而异。即便有数学模型，但解该模型的准确方法是否有现成算法、编程复杂度如何，这些都是我们要考虑的问题。第119页/共121页本节作业与练习一、简要回答如下问题：模拟策略主要有哪两种形式？模拟解题方法一般有三种类型？二、给出下列问题的解题思路及算法实现 【例20】DAM语言【例21】蒙特卡洛法第120页/共121页谢谢您的观看！第121页/共121页