第3章递推算法（C版）课件

第三章第三章递推算法递推算法第三章递推算法1递推法是一种重要的数学方法，在数学的各个领域中都递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。有广泛的运用，也是计算机用于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。计算机擅长于重复处理的特点。递推算法的首要问题是得到相邻的数据项间的关系（即递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。来，可以将递推算法看成是一种特殊的迭代算法。递推法是一种重要的数学方法，在数学的各个领域中2【例例1】数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。1、一步可沿左斜线向下或右斜线向下走；2、三角形行数小于等于100；3、三角形中的数字为0，1，99；测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：5738810274445265【算法分析算法分析】此题解法有多种，从递推的思想出发，设想，当从顶层沿某条路径走到第i层向第i+1层前进时，我们的选择一定是沿其下两条可行路径中最大数字的方向前进，为此，我们可以采用倒推的手法，设aij存放从i,j出发到达n层的最大值，则aij=maxaij+ai+1j，aij+ai+1j+1，a11即为所求的数字总和的最大值。【例1】数字三角形。如下所示为一个数字三角形。请编一个程序计3【参考程序参考程序】#includeusingnamespacestd;intmain()intn,i,j,a101101;cinn;for(i=1;i=n;i+)for(j=1;jaij;/输入数字三角形的值for(i=n-1;i=1;i-)for(j=1;j=ai+1j+1)aij+=ai+1j;/路径选择elseaij+=ai+1j+1;couta110),输出铺法总数。输出铺法总数。【算法分析算法分析】（1）面对上述问题，如果思考方法不恰当，要想获得问题的解）面对上述问题，如果思考方法不恰当，要想获得问题的解答是相当困难的。可以用递推方法归纳出问题解的一般规律。答是相当困难的。可以用递推方法归纳出问题解的一般规律。（2）当）当n=1时，只能是一种铺法，铺法总数有示为时，只能是一种铺法，铺法总数有示为x1=1。（3）当）当n=2时：骨牌可以两个并列竖排，也可以并列横排，再时：骨牌可以两个并列竖排，也可以并列横排，再无其他方法，如下左图所示，因此，铺法总数表示为无其他方法，如下左图所示，因此，铺法总数表示为x2=2；【例2】有2n的一个长方形方格，用一个1*2的骨牌铺满5（4）当n=3时：骨牌可以全部竖排，也可以认为在方格中已经有一个竖排骨牌，则需要在方格中排列两个横排骨牌（无重复方法），若已经在方格中排列两个横排骨牌，则必须在方格中排列一个竖排骨牌。如上右图，再无其他排列方法，因此铺法总数表示为x3=3。由此可以看出，当n=3时的排列骨牌的方法数是n=1和n=2排列方法数的和。（5）推出一般规律：对一般的n，要求xn可以这样来考虑，若第一个骨牌是竖排列放置，剩下有n-1个骨牌需要排列，这时排列方法数为xn-1；若第一个骨牌是横排列，整个方格至少有2个骨牌是横排列（1*2骨牌），因此剩下n-2个骨牌需要排列，这是骨牌排列方法数为xn-2。从第一骨牌排列方法考虑，只有这两种可能，所以有：xn=xn-1+xn-2（n2）x1=1x2=2xn=xn-1+xn-2就是问题求解的递推公式。任给n都可以从中获得解答。例如n=5，x3=x2+x1=3x4=x3+x2=5x5=x4+x3=8（4）当n=3时：骨牌可以全部竖排，也可以认为在方格中已经6下面是输入下面是输入n，输出，输出x1xn的的c+程序：程序：#includeusingnamespacestd;intmain()intn,i,j,a101;coutn;a1=1;a2=2;coutx1=a1endl;coutx2=a2endl;for(i=3;i=n;i+)/递推过程递推过程ai=ai-1+ai-2;coutxi=aiendl;下面是运行程序输入下面是运行程序输入n=30，输出的结果：，输出的结果：inputn:30 x1=1x2=2x3=3.x29=832040 x30=1346269问题的结果就是有名的斐波那契数。问题的结果就是有名的斐波那契数。下面是输入n，输出x1xn的c+程序：7【例【例3】棋盘格数】棋盘格数设有一个N*M方格的棋盘（lN100，1M100）。求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）。例如：当N=2，M3时：正方形的个数有8个：即边长为1的正方形有6个；边长为2的正方形有2个。长方形的个数有10个：即2*1的长方形有4个：1*2的长方形有3个：3*1的长方形有2个：3*2的长方形有1个：程序要求：输入：N，M输出：正方形的个数与长方形的个数如上例：输入：23输出：810【算法分析】【算法分析】1.计算正方形的个数s1边长为1的正方形个数为n*m边长为2的正方形个数为(n-1)*(m-1)边长为3的正方形个数为(n-2)*(m-2)边长为minn，m的正方形个数为(m-minn，m+1)*(n-minn，m+1)根据加法原理得出s1=【例3】棋盘格数82.长方形和正方形的个数之和s宽为1的长方形和正方形有m个，宽为2的长方形和正方形有m-1个，宽为m的长方形和正方形有1个；长为1的长方形和正方形有n个，长为2的长方形和正方形有n-1个，长为n的长方形和正方形有1个；根据乘法原理s=(1+2+n)*(1+2+m)=3.长宽不等的长方形个数s2显然，s2=s-s1=-2.长方形和正方形的个数之和s3.长宽不等的长方形个数s29由此得出算法：#includeusingnamespacestd;intmain()intn,m;cinmn;intm1=m,n1=n,s1=m*n;/计算正方形的个数s1while(m1!=0&n1!=0)m1-;n1-;s1+=m1*n1;ints2=(m+1)*(n+1)*m*n)/4-s1;/计算长方形的个数s2couts1s2endl;由此得出算法：10【例例4】昆虫繁殖【问题描述问题描述】科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？0=X=20,1=Y=20,X=Z=50【输入格式输入格式】x,y,z的数值【输出格式输出格式】过Z个月以后，共有成虫对数【输入样例输入样例】128【输出样例输出样例】37【例4】昆虫繁殖11【参考程序参考程序】#includeusingnamespacestd;intmain()longlonga101=0,b101=0,i,j,x,y,z;cinxyz;for(i=1;i=x;i+)ai=1;bi=0;for(i=x+1;i=z+1;i+)/因为要统计到第z个月后，所以要for到z+1bi=y*ai-x;ai=ai-1+bi-2;coutaz+1endl;return0;【参考程序】12【例例5】位数问题【问题描述问题描述】在所有的N位数中，有多少个数中有偶数个数字3？由于结果可能很大，你只需要输出这个答案对12345取余的值。【输入格式输入格式】读入一个数N【输出格式输出格式】输出有多少个数中有偶数个数字3。【输入样例输入样例】2【输出样例输出样例】73【数据规模数据规模】1=N=1000【样例说明样例说明】在所有的2位数字，包含0个3的数有72个，包含2个3的数有1个，共73个【例5】位数问题13【算法分析算法分析】方法一：排列组合(但需要运用动态规划)。可以列出公式,在n个格子中放x个3(其中x为偶数,包括0).。c(n,x)*9(n-x)-c(n-1,x)*9(n-x-1)含义为在n个格子中取x个3,且不考虑第一位的特殊情况为c(n,x)*9(n-x)。而第一位为0的情况,为c(n-1,x)*9(n-x-1),两者减下,就为答案。方法二：递推考虑这种题目,一般来说都是从第i-1位推导第i位,且当前位是取偶数还是取奇数的。恍然大悟.可以用fi0表示前i位取偶数个3有几种情况,fi1表示前i位取奇数个3有几种情况。则状态转移方程可以表示为:fi0=fi-10*9+fi-11;fi1=fi-10+fi-11*9;边界条件:f11=1;f10=9;【算法分析】14【参考程序参考程序】#includeusingnamespacestd;intmain()intf10012,n,i,x;cinn;f11=1;f10=9;for(i=2;i=n;i+)x=f10;if(i=n)x-;fi0=(fi-10*x+fi-11)%12345;fi1=(fi-11*x+fi-10)%12345;cout0且j0且gij=0递推边界有4个：Fij=0/gij=1Fi0=Fi-10/i0且gi0=0F0j=F0j-1/j0且g0j=0F00=1考虑到最大情况下：n=20,m=20，路径条数可能会超过231-1,所以要用高精度。【算法分析】17【例例7】邮票问题邮票问题【问题描述问题描述】设有已知面额的邮票m种，每种有n张，用总数不超过n张的邮票，能从面额1开始，最多连续组成多少面额。（1m100，1n100，1邮票面额255）【输入格式输入格式】第一行：m,n的值，中间用一空格隔开。第二行：A1.m（面额），每个数中间用一空格隔开。【输出格式输出格式】连续面额数的最大值【输入样例输入样例】stamp.in34124【输出样例输出样例】stamp.out14【例7】邮票问题18【算法分析算法分析】一看到这个题目，给人的第一感觉是用回溯算法，从面额1开始，每种面额都用回溯进行判断，算法复杂度并不高，但是当m，n取到极限值100时，程序明显超时，因此，回溯算法在这里并不可取。能否用递推完成呢?我们有一个思路:从面额1开始，建立递推关系方程，就用范例来说吧，面额1，2，4只用1张邮票行了，面额3可以表示为面额1，2的邮票和1+1=2，面额5有两种表示方式min(面额1+面额4，面额2+面额3)，照此类推，递推关系方程不难建立，就拿邮票问题来说，以下是递推的一种方法:#includeusingnamespacestd;intn,m,i,j,k;intc256;/面额inta31001;/递推数组boolb1;voidreadfile()/读入数据cinmn;b1=true;for(i=1;ici;if(ci=1)b1=false;【算法分析】19voidwork()if(b1=true)coutMAX=0;/不存在面额1时输出无解elsei=1;ai=1;doi+;for(j=1;j=m;j+)if(i%cj=0)&(i/cj)ai)|(ai=0)ai=i/cj;/判断它能否被题目给定面额整除for(j=1;j=i/2;j+)if(aj+ai-jai)ai=aj+ai-j;/寻找(1=j=i),使aj+ai-j值最小while(ai=n)&(ai!=0);couti-1;/输出voidwork()20intmain()readfile();work();return0;这种递推方法虽然简单，由于1=邮票面额=255，1=n=100，因此MAX值最多可达到25500，25500次循环里必定还有嵌套循环，因此算法不加优化，很难在规定时间内得出最优值。这就需要递推的算法优化。一味递推不寻求算法优化，速度较之搜索提高不少，但一旦数据规模过大，很难在规定时间内得出最优值。这种递推方法原理是:对于某种要求得到的面额，判断它能否被题目给定面额整除，再寻找(1=j=i)，使Aj+Ai-j值最小，求出凑成某种面额最少邮票数，算法虽然简单，但还可以进一步优化。何不将用m种面额邮票作循环，建立递推关系式:Ai=MAX(AI-Cj+1)，于是当取到极限值时，程序减少了约1.6*108次循环，递推优化作用不言而喻。intmain()21下面是改进后的程序:#include#includeusingnamespacestd;intx256;intpieces30001;intm,n,i,j;intmain()cinmn;for(i=1;ixi;memset(pieces,0,sizeof(pieces);intmaxx=0;do/递推循环maxx+;下面是改进后的程序:22for(i=1;i=0)/循环,建立递推关系式PIECESi=MAX(PIECESI-Xj+1)if(piecesmaxx=0)piecesmaxx=piecesmaxx-xi+1;if(piecesmaxxpiecesmaxx-xi+1)piecesmaxx=piecesmaxx-xi+1;if(piecesmaxx=0)|(piecesmaxxn)coutmaxx-1;break;while(true);return0;for(i=1;i1,m1)边界条件可以由定义2推导出：S2(n,0)=0；S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(kn)。第二类Stirling数在竞赛中较少出现，但在竞赛中也有一些题目与其类似，甚至更为复杂。读者不妨自己来试着建立其中的递推关系。.第二类Stirling数31小结：通过上面对五种典型的递推关系建立过程的探讨，可知对待递推类的题目，要具体情况具体分析，通过找到某状态与其前面状态的联系，建立相应的递推关系。【例【例7】(1998合肥市竞赛复试第二题合肥市竞赛复试第二题)同一平面内的同一平面内的n(n500)条直线，已知有条直线，已知有p(p2)条直线相交于同一点，则这条直线相交于同一点，则这n条直线最多条直线最多能将平面分割成多少个不同的区域？能将平面分割成多少个不同的区域？解：这道题目与第一部分中的平面分割问题十分相似，不同之处就在于线条的曲直以及是否存在共点线条。由于共点直线的特殊性，我们决定先考虑p条相交于一点的直线，然后再考虑剩下的n-p条直线。首先可以直接求出p条相交于一点的直线将平面划分成的区域数为2p个，然后在平面上已经有k(kp)条直线的基础上，加上一条直线，最多可以与k条直线相交，而每次相交都会增加一个区域，与最后一条直线相交后，由于直线可以无限延伸，还会再增加一个区域。所以fm=fm-1+m(mp)，边界条件在前面已经计算过了，是fp=2p。虽然这题看上去有两个参数，但是在实际做题中会发现，本题还是属于带一个参数的递推关系。小结：通过上面对五种典型的递推关系建立过程的探讨，32【上机练习上机练习】1、走楼梯、走楼梯楼梯有N级台阶，上楼可以一步上一阶，也可以一步上二阶。编一递归程序，计算共有多少种不同走法？【输入样例输入样例】Stairs.in3【输出样例输出样例】Stairs.out32、兔子繁殖、兔子繁殖有一种兔子，出生后一个月就可以长大，然后再过一个月一对长大的兔子就可以生育一对小兔子且以后每个月都能生育一对。现在，我们有一对刚出生的这种兔子，那么，n个月过后，我们会有多少对兔子呢？假设所有的兔子都不会死亡。【输入格式输入格式】输入文件仅一行，包含一个自然数n。【输出格式输出格式】输出文件仅一行，包含一个自然数，即n个月后兔子的对数。【输入样例输入样例】Rabbit.in5【输出样例输出样例】Rabbit.out5【上机练习】1、走楼梯333、平面分割、平面分割同一平面内有n（n500）条直线，已知其中p（p2）条直线相交于同一点，则这n条直线最多能将平面分割成多少个不同的区域？【输入格式输入格式】两个整数n（n500）和p（2pn）。【输出格式输出格式】一个正整数，代表最多分割成的区域数目。【输入样例输入样例】Surface.in125【输出样例输出样例】Surface.out734、骨牌铺法、骨牌铺法有1n的一个长方形，用一个11、12和13的骨牌铺满方格。例如当n=3时为13的方格。此时用11、12和13的骨牌铺满方格，共有四种铺法。如下图：【输入样例输入样例】Domino.in3【输出样例输出样例】Domino.out43、平面分割【输入样例】Domino.in【输出样例】Dom345、蜜蜂路线、蜜蜂路线【问题描述问题描述】一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：蜜蜂从蜂房M开始爬到蜂房N，MN，有多少种爬行路线？【输入格式输入格式】输入M，N的值。【输出格式输出格式】爬行有多少种路线。【输入样例输入样例】bee.in114【输出样例输出样例】bee.out3775、蜜蜂路线【输入格式】356、数塔问题、数塔问题【问题描述问题描述】设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示：若要求从根结点开始，请找出一条路径，使路径之和最大，只要输出路径的和。【输入格式输入格式】第一行为n(n10)，表示数塔的层数从第2行至n+1行，每行有若干个数据，表示数塔中的数值。【输出格式输出格式】输出路径和最大的路径值。【输入样例输入样例】tower.in51311812726614158127132411【输出样例输出样例】tower.out866、数塔问题若要求从根结点开始，请找出一条路径367、过河卒（、过河卒（NOIP2002）【问题描述】【问题描述】棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点（如图中的C点和P1，P2，P8）。卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n,m)(n,m为不超过20的整数),同样马的位置坐标是需要给出的，CA且CB。现在输入B点坐标和C点的坐标，要你计算出卒从A点能够到达B点的路径的条数。【输入样例输入样例】knight.in4824【输出样例输出样例】knight.out07、过河卒（NOIP2002）【输入样例】knight.in379、极值问题、极值问题【问题描述问题描述】已知m、n为整数，且满足下列两个条件：m、n，k，即1m，nk（n2m*nm2）21你的任务是：编程输入正整数k（1k109），求一组满足上述两个条件的m、n，并且使m2n2的值最大。例如，从键盘输入k=1995，则输出：m=987n=1597。【输入样例输入样例】Acme.in1995【输出样例输出样例】Acme.outm=987n=15979、极值问题38