递推算法PPT课件

.,1,递推算法,.,2,引例:Fibonacci数列,Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。问题：一个数列的第0项为0，第1项为1，以后每一项都是前两项的和，这个数列就是著名的裴波那契数列，求裴波那契数列的第N项。,.,3,解答,由问题,可写出递推方程边界条件：f0=0;f1=1;递推公式：fi=fi-1+fi-2;,算法：f0=1;f1=2;for(i=2;i=n;i+)fi=fi1+fi2;,.,4,总结,从这个问题可以看出，在计算裴波那契数列的每一项目时,都可以由前两项推出。这样，相邻两项之间的变化有一定的规律性，我们可以将这种规律归纳成如下简捷的递推关系式：Fn=g(Fn-1)，这就在数的序列中，建立起后项和前项之间的关系。然后从初始条件（或是最终结果）入手，按递推关系式递推，直至求出最终结果（或初始值）。很多问题就是这样逐步求解的。对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件（或最终结果），问题就可以递推了，接下来便是让计算机一步步了。让高速的计算机从事这种重复运算，真正起到“物尽其用”的效果。,.,5,递推概念,给定一个数的序列H0,H1,Hn,若存在将Hn与其前面的某些项Hi(0in)联系起来，这样的式子就叫做递推关系。如何建立递推关系递推关系有何性质如何求解递推关系,.,6,递推的分类,递推分倒推法和顺推法两种形式。1、顺推法：从已知条件出发，逐步推出要解决的问题。2、逆推法：从问题出发，逐步推到已知条件。算法流程如下：,.,7,Description：有一对小兔,过一个月之后长成大兔,到第四个月就可以生下一对小兔,并且以后每个月都生下一对小兔。而所生的一对小兔也同样到一个月之后长成大兔,到第四个月就可以生下一对小兔,并且以后也每个月都生下一对小兔.假设所有的兔子均不死亡，问第n个月后共有多少对兔子？请设计一个程序，解决这一问题。Input：一个整数n（n=50）Output：第n个月后共有多少对兔子SampleInput：5SampleOutput：3,顺推举例2兔子繁殖问题1559,.,8,知识迁移：昆虫繁殖,Description：科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？0=Input：x,y,z的数值Output：过Z个月以后，共有成虫对数SampleInput：128SampleOutput：37,.,9,分析,首先我们来看样例：每隔1个月产2对卵，求过8月（即第8+1=9月）的成虫个数,.,10,分析,设数组Ai表示第i月新增的成虫个数。由于新成虫每过x个月产y对卵，则可对每个Ai作如下操作:Ai+k*x+2:=Ai+k*x+2+Ai*y(1xyz;a1=1;for(i=1;i=z+1;i+)for(k=1;k=z+1;k+)ai+k*x+2+=y*ai;for(i=1;i=z+1;i+)sum+=ai;coutsum=2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上,然后把a柱最下面的盘子移动到c柱上;再借助a柱把b柱上的n-1个盘子移动到c柱上;总共移动hn-1+1+hn-1个盘次。hn=2hn-1+1边界条件：hn-1=1,.,17,递推应用7Catalan数1580,在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用hn表之，hn即为Catalan数。例如五边形有如下五种拆分方案，故h5=5。求对于一个任意的凸n边形相应的hn。,.,18,分析,设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。,.,19,设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点,问这些封闭曲线把平面分割成的区域个数。,逆推举例8平面分割问题,.,20,分析,设an为n条封闭曲线把平面分割成的区域个数。由图2可以看出：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=1。,.,21,【问题描述】:集合的划分:设s是一个具有n个元素的集合,sa1,a2,an,现将s划分为k个满足下列条件的子集合s1,s2,sk,且满足：(1)si(2)si交sj=(3)s1并s2并s3并并sks则称s1,s2,sk是集合s的一个划分。请你确定n个元素a1,a2,an放入k个无标号盒子中去的划分数s(n,k)。【文件输入】：n和k(0kk，k1)S(n，k)0(n0,gx,y=0,f0,j=f0,j-1j0,gx,y=0,fi,0=fi-1,j+fi,j-1i0,j0,gx,y=0,卒只能向右或者向下走,不能经过马点或者马的控制点,求A到B点所有路径条数。,X,Y,.,26,Description如下所示一个数字三角形。请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。每一步可沿左斜线向下或右斜线向下走；1三角形行数100；三角形中的数字为整数0，1，99；5738810274445265Input：输入第一行为一个自然数，表示数字三角形的行数n，接下来的n行表示一个数字三角形Output：输出仅