第二讲--递推算法.ppt

引例.Fibonacci数列,Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。问题：一个数列的第0项为0，第1项为1，以后每一项都是前两项的和，这个数列就是著名的裴波那契数列，求裴波那契数列的第N项。,由问题,可写出递推方程,解答,算法：F0:=1;F1:=2;FORi:=2TONDOFi:=Fi1+Fi2;,总结,从这个问题可以看出，在计算裴波那契数列的每一项目时，都可以由前两项推出。这样，相邻两项之间的变化有一定的规律性，我们可以将这种规律归纳成如下简捷的递推关系式：Fn=g(Fn-1)，这就在数的序列中，建立起后项和前项之间的关系。然后从初始条件（或是最终结果）入手，按递推关系式递推，直至求出最终结果（或初始值）。很多问题就是这样逐步求解的。对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件（或最终结果），问题就可以递推了，接下来便是让计算机一步步了。让高速的计算机从事这种重复运算，真正起到“物尽其用”的效果。,递推概念,给定一个数的序列H0,H1,Hn,若存在整数n0，使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hn(0=1,z=x输入：x,y,z的数值输出：成虫对数示例：输入：x=1y=2z=8输出：37,分析,首先我们来看样例：每隔1个月产2对卵，求过8月（即第8+1=9月）的成虫个数,分析,设数组Ai表示第i月新增的成虫个数。由于新成虫每过x个月产y对卵，则可对每个Ai作如下操作:Ai+k*x+2:=Ai+k*x+2+Ai*y(1=2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。hn=2hn-1+1边界条件：h1=1,例3:平面分割问题,设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。,分析,设an为n条封闭曲线把平面分割成的区域个数。由图2可以看出：a2-a1=2；a3-a2=4；a4-a3=6。从这些式子中可以看出an-an-1=2(n-1)。当然，上面的式子只是我们通过观察4幅图后得出的结论，它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有n-1条曲线将平面分割成an-1个区域后，第n-1条曲线每与曲线相交一次，就会增加一个区域，因为平面上已有了n-1条封闭曲线，且第n条曲线与已有的每一条闭曲线恰好相交于两点，且不会与任两条曲线交于同一点，故平面上一共增加2(n-1)个区域，加上已有的an-1个区域，一共有an-1+2(n-1)个区域。所以本题的递推关系是an=an-1+2(n-1)边界条件是a1=2。,例4：杨辉三角,分析,组合公式的证明：,例5：Catalan数,在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用hn表示，hn即为Catalan数。例如五边形有如下五种拆分方案，故h5=5。求对于一个任意的凸n边形相应的hn。,分析,设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边形的三角拆分方案总数为:,边界条件C2=1。,例6：贮油点,一辆重型卡车欲穿过1000公里的沙漠，卡车耗汽油为1升/公里，卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点，使卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？每一贮油点应存储多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。格式如下：No.Distance(k.m.)Oil(litre)12,分析,设Wayi第i个贮油点到终点（i=0）的距离；oili第i个贮油点的贮油量；我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。从贮油点i向贮油点i+1倒推的方法是：卡车在贮油点i和贮油点i+1间往返若干次。卡车每次返回i+1点时应该正好耗尽500公升汽油，而每次从i+1点出发时又必须装足500公升汽油。两点之间的距离必须满足在耗油最少的条件下，使i点贮足i*500公升汽油的要求（0in-1）。,倒推第一步,第一个贮油点i=1应距终点i=0处500km，且在该点贮藏500公升汽油，这样才能保证卡车能由i=1处到达终点i=0处，这就是说Way1=500；oil1=500；,倒推第二步,为了在i=1处贮藏500公升汽油，卡车至少从I=2处开两趟满载油的车至i=1处，所以i=2处至少贮有2*500公升汽油，即oil2=500*2=1000；另外，再加上从i=1返回至i=2处的一趟空载，合计往返3次。三次往返路程的耗油量按最省要求只能为500公升，即d1,2=500/3km，Way2=Way1+d1,2=Way1+500/3,倒推第三步,为了在I=2处贮藏1000公升汽油，卡车至少从I=3处开三趟满载油的车至I=2处。所以I=3处至少贮有3*500公升汽油，即oil3=500*3=1500。加上I=2至I=3处的二趟返程空车，合计5次。路途耗油亦应500公升，即d23=500/5，Way3=Way2+d2,3=Way2+500/5；,倒推第k步,为了在i=k处贮藏k*500公升汽油，卡车至少从i=k+1处开k趟满载车至i=k处，即oilk+1=(k+1)*500=oilk+500，加上从i=k返回i=k+1的k-1趟返程空间，合计2k-1次。这2k-1次总耗油量按最省要求为500公升，即dk,k+1=500/(2k-1)Wayk+1=Wayk+dk,k+1=Wayk+500/(2k-1)；,i=n的情形,i=n至始点的距离为1000-Wayn,oiln=500*n。为了在i=n处取得n*500公升汽油，卡车至少从始点开n+1次满载车至I=n，加上从I=n返回始点的n趟返程空车，合计2n+1次，2n+1趟的总耗油量应正好为（1000-Wayn）*(2n+1)