信息学奥林匹克竞赛辅导课件-归纳策略.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=n;i+) fi=g(fi-1); /从边界条件f1出发进行顺推 推出顺推结果fn; ,由此可见，递推算法的时间复杂度一般为W(n)。我们之所以将递推法划入归纳策略，是因为初始条件（或最终结果）除试题己明确给定外，都是通过对问题的整理与化简而确定的，其递推式也是对实际问题的分析与归纳而得到的，因此递推本质上属于归纳。,2递推关系的建立,递推关系中存在着三大基本问题： 如何建立递推关系， 已给出的递推关系有何性质， 以及如何求解递推关系。 其中核心问题是如何建立递推关系。,建立递推关系的关键在于寻找第n项与前面（或后面）几项的关系式，以及初始项的值（或最终结果值）。它不是一种抽象的概念，而是针对某一具体题目或一类题目而言的。 下面，我们对五种典型的递推关系的建立作比较深入具体的讨论。递推程序一般是将递推公式“直译”成一重循环，模式性很强。,( 1 ) Fibonacci 数列,Fibonacci数列的代表问题是由意大利著名数学家 Fibonacci于1202年提出的“兔子繁殖问题”（又称“Fibonacci问题”)： 有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？ 分析：设满X月共有兔子Fx对，其中当月新生的兔子数目为Nx对。第x-1个月留下的兔子数设为Ox 对。则：,Fx=Nx+Ox 而Ox=Fx-1 Nx=Ox-1=Fx-2(即第x-2个月的所有兔子到第x个月都有繁殖能力了) 所以 Fx=Fx-1+Fx-2 边界条件： F0=0， F1=1 由上面的递推关系可依次得到： F2=F1+F0=1,F3= F2+F1=2,F4=F3+F2=3 ，, Fibonacci 数列常出现在比较简单的组合计数问题中，例如【例9】极值问题、【例10】取石子问题、【例13】蜜蜂爬行等问题都可以用这种方法来解决。,( 2 ) Hanoi 塔问题,Hanoi塔由n个大小不同的圆盘和三根木柱a, b, c 组成。开始时，这n个圆盘由大到小依次套在 a柱上，如图所示。,要求把a柱上n个圆盘按下述规则移到c柱上： 1.一次只能移一个圆盘； 2.圆盘只能在三个柱上存放； 3.在移动过程中，不允许大盘压小盘。 问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？,分析：设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=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(1kn)，与P1, Pn共同构成一个三角形的三个顶点，就将n边形分成了三个不相交的部分，我们分别称之为区域、区域和区域。,其中区域必定是一个三角形，区域是一个凸k边形，区域是一个凸n-k+1边形，区域的拆分方案总数是Ck，区域的拆分方案数Cn-k+1，故包含P1PkPn 的n边形的拆分方案数为 CkCn-k+1种，而Pk可以是P2, P3， ， Pn-1 中任一点，根据加法原理，凸n边形的三角拆分方案总数为,加法原理和乘法原理,(1)加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，在第n类办法中有mn种不同的方法，那么完成这件事共有Nm1m2mn种不同方法 (2)乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事共有Nm1m2mn种不同的方法 要做一件事，完成它若是有n类办法，是分类问题，第一类中的方法都是独立的，因此用加法原理；做一件事，需要分n个步骤，步与步之间是连续的，只有将分成的若干个互相联系的步骤，依次相继完成，这件事才算完成，因此用乘法原理,同时考虑到计算的方便，约定边界条件C2=1. Catalan 数是比较复杂的递推关系，尤其在竞赛的时候，选手很难在较短的时间里建立起正确的递推关系。当然，Catalan数类的问题也可以用搜索的方法来完成，但是，搜索的方法与利用递推关系的方法比较起来，不仅效率低，编程复杂度也陡然提高。,( 5 ）第二类 stirling 数,苏格兰数学家斯特林（J. Stirling, 1692-1770）首次发现这些数并说明了它们的重要性。 n个有区别的球放到m个相同的盒子中，要求无一空盒，不同的方案数用s2(n,m)表示，称为第二类Stirling数。 分析：设有n个不同的球，分别用b1, b2， ，bn表示。从中取出一个球bn，bn的放法有以下两种： bn独自占一个盒子，那么剩下的球只能放在 m-1 个盒子中，方案数为S2(n-1，m-1)； bn与别的球共占一个盒子，那么可以事先将b1, b2，bn-1这n-1个球放入m个盒子中，然后再将球bn可以放入其中一个盒子中，方案数为mS2(n-1,m)。,综合以上两种情况，可以得出第二类stirling数定理： S2(n,m)=m S2(n-1,m)+ S2(n-1,m-1) (n1,m=1) 边界条件为： S2(n,0)=0 S2(n,1)=1，S2(n,n)=1 S2(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+2=n=b), 边界条件为 fa1，fa+11.,【 例14 】 分割平面,同一平面内的n(n=2)条直线相交于同一点，则这n条直线最多能将平面分割成多少个不同的区域？ 分析：直线的平面分割与封闭曲线的平面分割十分相似，不同之处就在于线条的曲直以及是否存在共点的直线。由于共点直线的特殊性，我们决定先考虑p条相交于一点的直线，然后再考虑剩下的n-p条直线。,首先可以直接求出p条相交于一点的直线将平面划分成的区域数为2*p个 然后在平面上已经有k(k=p)条直线的基础上，加上一条直线，最多可以与k条直线相交，而每次相交都会增加一个区域,与最后一条直线相交后，由于直线可以无限延伸，还会再增加一个区域。 所以 fm=fm-1+m(mP) ， 边界条件在前面己经计算过了，是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) 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=r=m) 显然，计算不同交点数的问题是递归的,可以描述成如下递归算法：,/m是直线数，j是交点数 void cross(int m,int j) if (m0) /若直线存在，则递归计算所有的交叉情况 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分解成若干互不相等的自然数的和，且使这些自然数的乘积最大呢？如果我们对这个问题不探究解析方法而去盲目搜索所有分解方案的话，则代价相当大。但是如果我们一旦耐心地对问题认真思考一番，是不难得出其中隐含着的数学规律的。设：,由于 11 。很明显，要使得乘积 a1a2 an最大，则必须使得项数n最大，且相邻两数ai+1-ai的差最小，这就是解决问题的目标方案。,为了达到这个目标，我们不妨设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,若ak+1=1,由于1x2x, ,xak2x3x,x(ak+1)，因此ak+1=1加到ak上； 若1ak+1ak,我们从ak出发，依次向尾部ak+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 由此可见，上述目标方案是分解自然数的依据。,有了这个目标方案，相应的算法也就可以设计出来了。,#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); /当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 ,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=fk，所以b中的活动是兼容的。又因为b与a的活动数相同，所以b也是最优的。由此证明总存在一个以贪心选择开始的最优调度。,(2)证明经过若干次贪心选择后可以得出一个最优解 当我们作出了对活动1的贪心选择后，原问题就变成在活动2至活动n中找与活动1兼容的那些活动的子问题。 也就是说，如果问题a为原问题的一个最优解，则a=a-1就是活动选择问题s的一个最优解。为什么会这样呢？如果我们能找到s的一个含有比a更多活动的解b则将活动1加入了b,就得到s的一个包含比a更多活动的解b,这就与a的最优性相矛盾。所以在每一次贪心选择后,留下的是一个与原问题具有相同形式的最优化问题.通过对所做选择次数的归纳可以证明,对每一步进行贪心选择就可得到一个最优解. 由此得出，按照这个贪心选择得出的解一定是最优的。,2801【例19】打包（ Packaging ),某个工厂生产出的产品都要被打包放入正四棱柱的盒子内。所有盒子的高度都为h,但底面的尺寸不同，可以为1x1,2x2,3x3,4x4,5x5,或 6x6，如图所示。,这些盒子将被放入高度为h,底面尺寸为6x6的箱子里,送到消费者手中。为了降低运送成本，工厂希望尽量减少箱子的数量。如果有一个好的算法，能使箱子的数量降到最低，这将给工厂节省不少资金。请你写一个这样的程序。 输入：六个非负整数a1,a2,a3,a4,a5,a6。它们分别为底面尺寸为1x1,2x2,3x3,4x4,5x5,6x6的盒子的个数。 输出：一个数b，即箱子的最少个数。,分析：让我们来看看可供选择的装箱方法： (1)如果有6x6的盒子，则将它放入箱子，这个箱子就满了，该过程直到6x6的盒子全部装箱为止； (2)如果有5x5的盒子，则将它放入箱子，这个箱子还有空余，可以放入尽可能多的1x1的盒子，这个过程的结束条件是5x5的盒子全部装箱，并且1x1的盒子全部装箱或者箱子全部装满； (3)如果有4x4的盒子，箱子中的剩余空间可以放2x2的盒子，如果还有剩余，则放1x1的盒子，这个过程直到4x4的盒子全部装箱，并且剩余空间被充分利用； ,简而言之就是每次找出最大的盒子放入当前的箱子中，直到无法再放；再拿一个空箱继续这一过程，直到所有的盒子都被装箱。解决这一类问题我们通常采用贪心算法。 下面我们使用第一种方法来证明对于打包问题，贪心法可以得出最优解。设要装下a1个1x1的盒子,a2个2x2的盒子， ，a6个6x6的盒子需要的箱子数为f(a1,a2,a3,a4,a5,a6)个。由前面的分析可知：,(1)由每一个 6x6 的盒子都刚好放入一个6x6的箱子可得等式:f(a1,a2,a3,a4,a5,a6)=f(a1,a2,a3,a4,a5,0)+a6 (2)己知放置每一个5x5的盒子都需要一个箱子，但每个箱子放入一个5x5的盒子后还有6x6-5x5=11 个单位的空间，而这些空间只能放1x1的盒子，最多放11个,可得等式：f(a1,a2,a3,a4,a5,0)=f(max0,a1-11*a5,a2, a3,a4,0,0)+a5,(3)已知放置每一个4x4 的盒子都需要一个箱子，之后还有 6x6-4x4=20个单位的空间。这些空间恰好可以放入 5个2x2的盒子，或20个1x1的盒子。根据尽可能先放大盒子的贪心策略， 我们尽量先放2x2的盒子。放置a4个4x4的盒子需要a4个箱子，剩余 5*a4个2x2的空间。,若a2=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; coutpack(a1,a2,a3,a4,a5,a6); ,#include /优化 #include 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) ,贪心算法的基本要素,可以用贪心算法求解的问题一般具有两个重要的性质：贪心选择性质和最优子结构性质 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 =300)。最后一行是：0 0 Output:对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号,Sample Input 6 2 12 4 8 3 0 0 Sample Output 5 1 7,解题思路1： 用数组loop来存放n个数，相当于n个数排成的圈，用整型变量nPtr指向当前数到的数组元素，相当于人的手指，划掉一个数就将该数置0，在数数时，要跳过为0的元素。当nPtr指向最后一个元素时再数下一个时则指向数组的头一个元素。,#include const 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(loopnPtr=0) nPtr=(nPtr+1)%n; nCount+; nPtr=(nPtr+1)%n; nPtr-; if(nPtr0) nPtr=n-1; if (i=n-1) coutloopnPtr; loopnPtr=0; ,采用循环链表实现如下,#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; 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指令，因此次数上限为26=64。我们可以用数组来表示多项式，既方便又不会导致时间和空间上的问题。 (2)本题也没有说明系数的最大值。稍微细心的选手会发现：它最大可能为232, 未超过长整数的范围，不存在非得用高精度的必要。,#include #include void main() static int degree13;/存储系数个数的栈 s