递推关系的建立及其求解方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三讲,递推式的建立及其求解方法,一、递推式的建立,1,、,Hanoi,塔问题,问题,:,三柱问题,问题,：四柱问题,问题,：,m,柱问题,2,、平面分割问题,问题,：封闭曲线分割平面,问题,：,Z,分割平面,问题,：,M,分割平面,3,、,Catalan,数,问题一：凸,n,边形的三角形剖分,问题二：二叉树数目,问题三：出栈序列,4,、第二类,Stirling,数,问题一：放置小球,问题二：集合划分问题,5,、其他,问题一：集合取数问题,问题二：整数划分问题,二、递推式的求解方法：,1,递归函数,用数组实现,求递推式的通项表达式：,3,1,、迭加法,3,2,、待定系数法,3,3,、特征方程法,3,4,、生成函数法,一、递推式的建立,1,、,Hanoi,塔问题,问题的提出：,Hanoi,塔由,n,个大小不同的圆盘和,m,根木柱,1,2,3.,m,组成。开始时，这,n,个圆盘由大到小依次套在,1,柱上，如图所示。,现在要求把,1,柱上,n,个圆盘按下述规则移到,m,柱上：,(1),一次只能移一个圆盘；,(2),圆盘只能在,m,个柱上存放；,(3),在移动过程中，不允许大盘压小盘。,求将这,n,个盘子从,1,柱移动到,m,柱上所需要移动盘子的最少次数,。,问题,:,三柱问题,设,f(n,),为,n,个盘子从,1,柱移到,3,柱所需移动的最少盘次。当,n=1,时，,f(1)=1,。,当,n=2,时，,f(2)=3,。,以此类推，当,1,柱上有,n(n,2),个盘子时，我们可以利用下列步骤：,第一步：先借助,3,柱把,1,柱上面的,n-1,个盘子移动到,2,柱上，所需的移 动次数为,f(n-1),。,第二步：然后再把,1,柱最下面的一个盘子移动到,3,柱上，只需要,1,次 盘子。,第三步：再借助,1,柱把,2,柱上的,n-1,个盘子移动到,3,上，所需的移动次 数为,f(n-1),。,由以上,3,步得出总共移动盘子的次数为：,f(n-1)+1+f(n-1),。,所以：,f(n,)=2 f(n1)+1,f(n,)=2,n,-1,问题,：四柱问题,【,问题分析,】,：,令,fi,表示四个柱子时，把,i,个盘子从原柱移动到目标柱所需的最少移动次数。,j,第一步：先把,1,柱上的前,j,个盘子移动到另外其中一个非目标柱（,2,或,3,柱均可，假设移到,2,柱）上，此时,3,和,4,柱可以作为中间柱。移动次数为：,fj,。,第二步：再把原,1,柱上剩下的,i-j,个盘子在,3,根柱子（,1,、,3,、,4,）之间移动，最后移动到目标柱,4,上，因为此时,2,柱不能作为中间柱子使用，根据三柱问题可知，移动次数为：,2(,i-j)-1,。,第三步：最后把非目标柱,2,柱上的,j,个盘子移动到目标柱上，次数为：,fj,。,i,通过以上步骤我们可以初步得出：,fi,=2*fj+2(i-j)-1,j,可取的范围是,1=,jI,，,所以对于不同的,j,，,得到的,fi,可能是不同的，本题要求最少的移动次数,fi,=min2*fj+2(i-j)-1,，,其中,1=,jI,const,MaxNum,=1000;,var,n:integer;,F3,F4:array1.MaxNum of double;,procedure Init;,var,i:integer;,begin,fillChar(F3,sizeOf(F3),0);,fillChar(F4,sizeOf(F4),0);,readln(n,);,F31:=1;,F41:=1;,*F3n,为,Hanoi,塔中,3,根柱子，,n,个盘子的最少移动次数,F3n=2n-1;,F4n,为,Hanoi,塔中,4,根柱子，,n,个盘子的最少移动次数*,for i:=2 to n do F3i:=2*F3i-1+1;,end;,procedure Run;,var,i,j:integer;,minF4i,temp:double;,begin,for i:=2 to n do,begin,minF4i:=1e+100;,for j:=1 to i-1 do,begin,temp:=2*F4j+F3i-j;,if(temp minF4i)then minF4i:=temp;,end;,*F4i=min(2*F4j+F3i-j);(1=j=i-1)*,F4i:=minF4i;,end;,writeln(F4n:0:0);,end;,begin,Init;,Run;,end.,问题,：,m,柱问题,【,问题分析,】,：,设,F(m,n,),为,m,根柱子,n,个盘子时移动的最少次数：,1,、先把,1,柱上的前,j,个盘子移动到另外其中一个除,m,柱以外的非目标柱上，移动次数为：,fm,j,；,2,、再把原,1,柱上剩下的,n-j,个盘子在,m-1,根柱子之间移动，最后移动到目标柱,m,上，移动次数为：,fm-1,n-j,；,3,、最后把非目标柱上的,j,个盘子移动到目标柱没柱上，移动次数为：,fm,j,。,F(m,n,)=min2*,F(m,j)+F(m-1,n-j)(1=j n),j,2,、,平面分割问题,问题,问题的提出：设有,n,条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，求这些封闭曲线把平面分割成的区域个数。,【,问题分析,】,：,设,f(n,),为,n,条封闭曲线把平面分割成的区域个数。,由图,4,很容易得出：,f(1)=2,；,f(2)=4,。,2,假设当前平面上已有的,n-1,条曲线将平面分割成,f(n-1),个区域，现在加入第,n,条封闭曲线。第,n,条曲线每与已有的,n-1,条曲线相交共有,2(,n-1),个交点，也就是说第,n,条曲线被前,n-1,条曲线分割成,2(,n-1),段弧线，而每一条弧线就会把原来的区域一分为二，即增加一个区域，所以共增加,2(,n-1),个区域,F,（,n,）,=f,（,n-1,）,+2(n-1),问题,问题的提出：一个,z,形曲线可以把一个平面分割成,2,部分。如图所示。求,n,个,z,形曲线最多能把平面分割成多少部分。写出递推式,f(n,),。,【,问题分析,】,：,根据上图容易得出：,f,（,1,）,=2,；,f,（,2,）,=12,。,假设平面上已有,n-1,个,z,图形把平面分成了,f,（,n-1,）,个区域。加入第,n,个,z,后，因为前面的,n-1,个,z,共有,3,（,n-1,）,条边，第,n,个,z,和他们共有,3*(3*(,n-1),个交点,即第,n,个,z,被分成,3*(3*(,n-1)+1,部分，所以增加,3*(3*(,n-1)+1,个区域,由以上得出：,f,（,n,）,=f,（,n-1,）,+3*(3*(n-1)+1,即：,f,（,n,）,=f,（,n-1,）,+9n-8,初始条件：,f,（,1,）,=2,问题,：,M,分割平面,问题二的扩展：在问题二的基础上进一步考虑：如果,z,图形扩展为,m,边的下列图形：看一下问题的解。,通过上面的分析我们很容易知道：,n,个上述图形可以将平面划分的区域的递推关系：,f,（,n,）,=f,（,n-1,）,+m,（,m,（,n-1,）,+1=f(n-1)+m,2,(n-1)+1,初始条件：,f,（,1,）,=2,3,、,Catalan,数,问题一：凸,n,边形的三角形剖分,在一个凸,n,边形中，通过不相交于,n,边形内部的对角线，把,n,边形拆分成若干三角形，不同的拆分数目用,f(n,),表之，,f(n,),即为,Catalan,数。例如五边形有如下五种拆分方案，故,f(5)=5,。,求对于一个任意的凸,n,边形相应的,f(n,),。,区域是一个凸,k,边形，区域是一个凸,n-k+1,边形，区域的拆分方案总数是,f(k,),区域的拆分方案数为,f(n-k+1),，,故包含,P1PkPn,的,n,边形的拆分方案数为,f(k,)*f(n-k+1),种,F(n,)=,问题二：二叉树数目,问题描述：求,n,个结点能构成不同二叉数的数目。,【,问题分析,】,：,设,F(n,),为,n,个结点组成二叉树的数目。,容易知道：,f(1)=1;f(2)=2,f(3)=5,选定,1,个结点为根，左子树结点的个数为,i,，,二叉树数目,f,（,i,）,种；右子树结点数目为,n-i-1,，,二叉树数目,f,（,n-i-1,）,种，,I,的可取范围,0,，,n-1,。,所以有：,F(n,)=,为了计算的方便：约定,f,（,0,）,=1,问题三：出栈序列,问题描述：,N,个不同元素按一定的顺序入栈，求不同的出栈序列数目。,【,问题分析,】,：,设,f,（,n,）,为,n,个元素的不同出栈序列数目。,容易得出：,f,（,1,）,=1,；,f,（,2,）,=2,。,第,n,个元素可以第,i,（,1=i=n,）,个出栈，前面已出栈有,i-1,个元素，出栈方法：,f,（,i-1,）；,后面出栈,n-I,个元素，出栈方法为：,f,（,n-i,）。,所以有：,F(n,)=,约定：,F(0)=1,F(n,)=,4,、第二类,Stirling,数,问题一：放置小球,n,个有不同的球放到,m,个相同的盒子中，要求无一空盒，其不同的方案数用,S(n,m,),表示，称为第二类,Stirling,数,，求,S(n,m,),。,设有,n,个不同的球，分别用,b1,b2,bn,表示。从中取出一个球,bn,，,bn,的放法有以下两种：,1,）,bn,独自占一个盒子；那么剩下的球只能放在,m-1,个盒子中，方案数为,S(n-1,m-1),2,）,bn,与别的球共占一个盒子；那么可以事先将,b1,b2,bn-1,这,n-1,个球放入,m,个盒子中，然后再将球,bn,可以放入其中一个盒子中，方案数为,mS(n-1,m),S(n,m,)=mS(n-1,m)+S(n-1,m-1),问题二：,集合划分问题。,设,S,是一个包含,n,个元素的集合，,S=b1,b2,b3,bn,现需要将,S,集合划分为,m,个满足如下条件的集合,S1,S2,Sm,。,Si,;,SiSj,=;,S1S2Sm=S;(1=I,j1,m1),边界条件：,S2(n,1)=1,；,S2(n,n)=1,；,S2(n,k)=0(kn),。,5,、其他：,）集合取数问题,设,f(n,k,),是从集合,1,，,2,，。，,n,中能够选择的没有两个连续整数的,k,个元素子集的数目，求递归式,f(n,k,),。,【,问题分析,】,：,N,有两种情况：,当,n,在子集时，则,n-1,一定不在子集中，即在,1,，,2,，。，,n-2,中选,k-1,个元素，数目为,f(n-2,k-1),。,当,n,不在子集中时，则在,1,，,2,，。，,n-1,中选,k,个元素，数目为,f(n-1,k),。,所以：,f(n,k,)=f(n-2,k-1)+f(n-1,k),边界条件：,F(n,1)=n,f(n,k,)=0 (n=k),）整数划分问题,将整数,n,分成,k,份，且每份不能为空，任意两种分法不能相同,(,不考虑顺序,),。例如：,n=7,，,k=3,，,下面三种分法被认为是相同的。,1,，,1,，,5;1,，,5,，,1;5,，,1,，,1;,问有多少种不同的分法。输入：,n,，,k(6n=200,，,2=k=2,，可以先那出,j,个,1,分到每一份，然后再把剩下的,I-j,分成,j,份即可，分法有：,f(I-j,j,).,第二类,:,j,份中至少有一份为,1,的分法，可以先那出一个,1,作为单独的,1,份，剩下的,I-1,再分成,j-1,份即可，分法有：,f(I-1,j-1).,所以,：,f(I,j)=f(I-j,j)+f(I-1,j-1),边界条件：,f,（,i,，,1,）,=1,，,f,（,i,，,j,）,=0,，（,Ij,）,