递推算法

递推算法引例:Fibonacci数列•Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。•问题：一个数列的第0项为0，第1项为1，以后每一项都是前两项的和，这个数列就是著名的裴波那契数列，求裴波那契数列的第N项。解答•由问题,可写出递推方程•边界条件：f[0]=0;f[1]=1;•递推公式：f[i]=f[i-1]+f[i-2];算法：f[0]=1;f[1]=2;for(i=2;i=n;i++)f[i]=f[i–1]+f[i–2];总结•从这个问题可以看出，在计算裴波那契数列的每一项目时,都可以由前两项推出。这样，相邻两项之间的变化有一定的规律性，我们可以将这种规律归纳成如下简捷的递推关系式：Fn=g(Fn-1)，这就在数的序列中，建立起后项和前项之间的关系。然后从初始条件（或是最终结果）入手，按递推关系式递推，直至求出最终结果（或初始值）。很多问题就是这样逐步求解的。•对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件（或最终结果），问题就可以递推了，接下来便是让计算机一步步了。让高速的计算机从事这种重复运算，真正起到“物尽其用”的效果。递推概念给定一个数的序列H0,H1,…,Hn,…若存在将Hn与其前面的某些项Hi(0in)联系起来，这样的式子就叫做递推关系。如何建立递推关系递推关系有何性质如何求解递推关系递推的分类递推分倒推法和顺推法两种形式。1、顺推法：从已知条件出发，逐步推出要解决的问题。2、逆推法：从问题出发，逐步推到已知条件。算法流程如下：Description：有一对小兔,过一个月之后长成大兔,到第四个月就可以生下一对小兔,并且以后每个月都生下一对小兔。而所生的一对小兔也同样到一个月之后长成大兔,到第四个月就可以生下一对小兔,并且以后也每个月都生下一对小兔.假设所有的兔子均不死亡，问第n个月后共有多少对兔子？请设计一个程序，解决这一问题。Input：一个整数n（n=50）Output：第n个月后共有多少对兔子SampleInput：5SampleOutput：3顺推举例2——兔子繁殖问题1559知识迁移：昆虫繁殖Description：科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？0=X=20,1=Y=20,X=Z=50fontInput：x,y,z的数值Output：过Z个月以后，共有成虫对数SampleInput：128SampleOutput：37分析•首先我们来看样例：每隔1个月产2对卵，求过8月（即第8+1=9月）的成虫个数月份123456789…新增卵b[i]0222610142646…成虫a[i]111357132337…分析•设数组A[i]表示第i月新增的成虫个数。•由于新成虫每过x个月产y对卵，则可对每个A[i]作如下操作:•A[i+k*x+2]:=A[i+k*x+2]+A[i]*y(1=k,i+k*x+2=z+1）•因为A[i]的求得只与A[1]~A[i-1]有关，即可用递推求法。•则总共的成虫个数为：11][ziiAans#includeiostreamusingnamespacestd;intmain(){longlongi,k,a[1000]={0},x,y,z,sum=0;cinxyz;a[1]=1;for(i=1;i=z+1;i++)for(k=1;k=z+1;k++)a[i+k*x+2]+=y*a[i];for(i=1;i=z+1;i++)sum+=a[i];coutsumendl;return0;}顺推举例3——杨辉三角1547111121133114641………………a[1][1]=1a[2][1]=1a[2][2]=1a[i][j]=a[i-1][j-1]+a[i-1][j]Description：有一堆桃子和N只猴子，第一只猴子将桃子平均分成了M堆后，还剩了1个，它吃了剩下的一个，并拿走一堆。后面的猴子也和第1只进行了同样的做法，请问N只猴子进行了同样做法后这一堆桃子至少还剩了多少个桃子(假设剩下的每堆中至少有一个桃子)？而最初时的那堆桃子至少有多少个？Input：输入包含二个数据，数据间用空格隔开。第一个数据为猴子的只数N(1≤N≤10)，第二个数据为桃子分成的堆数M(2≤M≤7)。Output：输出包含两行数据，第一行数据为剩下的桃子数，第二行数据为原来的桃子数。SampleInput：32SampleOutput115逆推举例4——猴子摘桃1012迭代举例5——楼梯走法问题描述：设有一个N级楼梯，某人每步可以走1级、2级、或者3级，求某人从底层开始走完全部楼梯的走法。n=1f(1)=1:1n=2f(2)=2:11;2n=3f(3)=4:111;21;12;3n=4f(4)=7:1111;211;121;31;112;22;13递推方程：F(n)=f(n-1)+f(n-2)+f(n-3)边界条件：f(1)=1f(2)=2f(3)=4递推举例6:Hanoi塔问题•Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上：(1)一次只能移一个圆盘；(2)圆盘只能在三个柱上存放；(3)在移动过程中，不允许大盘压小盘。•问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？abc图1分析•设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-1+1+hn-1个盘次。•∴hn=2hn-1+1•边界条件：hn-1=1递推应用7——Catalan数1580•在一个凸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边形的三角拆分方案总数为:112inniiCC边界条件C2=1。•设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点,问这些封闭曲线把平面分割成的区域个数。逆推举例8——平面分割问题分析•设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。【问题描述】:集合的划分:设s是一个具有n个元素的集合,s＝{a1,a2,…,an},现将s划分为k个满足下列条件的子集合s1,s2,……,sk,且满足：(1)siф(2)si交sj=ф(3)s1并s2并s3并……并sk＝s则称s1,s2,……,sk是集合s的一个划分。请你确定n个元素a1,a2,…,an放入k个无标号盒子中去的划分数s(n,k)。【文件输入】：n和k(0k=n30)【文件输出】：s(n,k)【样例输入】：43【样例输出】：6逆推举例9——集合划分1577【算法分析】:例如S＝{1，2，3，4}，k＝3。细心的读者稍加分析后，不难得出S有6种不同的划分方案，即划分数为6。其方案为{1，2}∪{3}∪{4}{1，3}∪{2}∪{4}{1，4}∪{2}∪{3}{2，3}∪{1}∪{4}{2，4}∪{1}∪{3}{3，4}∪{1}∪{2}分析如果对于任意的S集合和k值，就不能凭籍直觉和经验计算划分数和枚举划分方案了。必须总结出一个数学规律:设n个元素a1…an放入k个无标号盒的划分数为S(n，k)。在配置过程中，有两种互不相容的情况:1.设{an}是k个子集中的一个子集，于是把{a1…an-1}划分为k－1子集有S(n－1，k－1)个划分数;2.如果{an}不是k个子集中的一个，即an必与其它的元素构成一个子集。首先把{a1，…，an-1}划分成k个子集，这共有S(n－1，k)种划分方式。然后再把an加入到k个子集中的一个子集中去，这有k种加入方式。对于每一种加入方式，都使集合划分为k个子集，因此由乘法原理知，划分数共有k*ｓ(n－1，k)。应用加法原理于上述两种情况，得出{a1，…，an}划分为k个子集的划分数:S(n,k)＝S(n-1,k-1)+k·S(n-1,k)(n1,k≥1)分析下面，我们来确定s(n,k)的边界条件:1.我们不可能把n个元素不放进任何一个集合中去，即ｓ(n，0)＝0;也不可能在不允许空盒的情况下把n个元素放进多于n的k个集合中去，即k＞n时S(n，k)＝0。2.把n个元素放进一个集合或把n个元素放进n个集合，方式数显然是1。即S(n,1)=1;S(n,n)=1显然，通过上述分析可得出划分数S(n，k)的递归关系式:S(n，k)＝S(n－1，k－1)+k·S(n－1，k)(nk，k≥1)S(n，k)＝0(nk)或(k＝0〈n)S(n，k)＝1(k=1)或(k＝n)分析递推关系式的建立10—过河卒用f[i,j]表示到达(i,j)的路径数目,用g[i,j]=1或0表示点(i,j)是否是马点或者马的控制点。BAf[i,j]=0{g[x,y]=1}f[i,0]=f[i-1,0]{i0,g[x,y]=0}f[0,j]=f[0,j-1]{j0,g[x,y]=0}f[i,0]=f[i-1,j]+f[i,j-1]{i0,j0,g[x,y]=0}卒只能向右或者向下走,不能经过马点或者马的控制点,求A到B点所有路径条数。XYDescription如下所示一个数字三角形。请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。●每一步可沿左斜线向下或右斜线向下走；●1＜三角形行数≤100；●三角形中的数字为整数0，1，…99；5738810274445265Input：输入第一行为一个自然数，表示数字三角形的行数n，接下来的n行表示一个数字三角形．Output：输出仅有一行包含一个整数（表示要求的最大总和）逆推举例11——数字