《(精品)递推关系的建立及其求解方法2.ppt》由会员分享，可在线阅读，更多相关《(精品)递推关系的建立及其求解方法2.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、递推关系的建立及其求解方法递推关系的建立及其求解方法王桐林王桐林一、递推式的建立一、递推式的建立 0、Fibonacci数列数列 1、Hanoi塔问题塔问题问题问题:三柱问题三柱问题问题问题：四柱问题：四柱问题问题问题：m柱问题柱问题2、平面分割问题、平面分割问题问题问题：封闭曲线分割平面：封闭曲线分割平面问题问题：Z分割平面分割平面问题问题：M分割平面分割平面3、Catalan数数问题一：凸问题一：凸n边形的三角形剖分边形的三角形剖分问题二：二叉树数目问题二：二叉树数目问题三：出栈序列问题三：出栈序列4、第二类、第二类Stirling数数 问题一：放置小球问题一：放置小球问题二：集合划分问题
2、问题二：集合划分问题5、其他、其他问题一：集合取数问题问题一：集合取数问题问题二：整数划分问题问题二：整数划分问题二、递推式的求解方法：二、递推式的求解方法：1 递归函数递归函数用数组实现用数组实现求递推式的通项表达式：求递推式的通项表达式：31、迭加法、迭加法 32、待定系数法、待定系数法 33、特征方程法、特征方程法 34、生成函数法、生成函数法三、递推的形式顺推法和倒推法顺推法和倒推法lFibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。l问题：一个数列的第0项为0，第1项为1，以后每一项都是前两项的
3、和，这个数列就是著名的裴波那契数列，求裴波那契数列的第N项。1、Fibonacci数列数列解答由问题,可写出递推方程算法：算法：F0:=1;F1:=2;FOR i:=2 TO N DO FI:=FI 1+FI 2;总结从这个问题可以看出，在计算裴波那契数列的每一项目从这个问题可以看出，在计算裴波那契数列的每一项目时，都可以由前两项推出。这样，相邻两项之间的变化时，都可以由前两项推出。这样，相邻两项之间的变化有一定的规律性，我们可以将这种规律归纳成如下简捷有一定的规律性，我们可以将这种规律归纳成如下简捷的递推关系式：的递推关系式：Fn=g(Fn1)，这就在数的序列中，建立，这就在数的序列中，建立
4、起后项和前项之间的关系。然后从初始条件（或是最终起后项和前项之间的关系。然后从初始条件（或是最终结果）入手，按递推关系式递推，直至求出最终结果结果）入手，按递推关系式递推，直至求出最终结果（或初始值）。很多问题就是这样逐步求解的。（或初始值）。很多问题就是这样逐步求解的。对一个试题，我们要是能找到后一项与前一项的关系并对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件（或最终结果），问题就可以递推了，清楚其起始条件（或最终结果），问题就可以递推了，接下来便是让计算机一步步了。让高速的计算机从事这接下来便是让计算机一步步了。让高速的计算机从事这种重复运算，真正起到种重复运算，真正起到
5、“物尽其用物尽其用”的效果。的效果。递推概念递推概念l给定一个数的序列给定一个数的序列H0,H1,Hn,若存若存在整数在整数n0，使当，使当n=n0时时,可以用等号可以用等号(或或大于号、小于号大于号、小于号)将将Hn与其前面的某些项与其前面的某些项Hn(0i2)个盘子时，我们可以利用下列步骤：个盘子时，我们可以利用下列步骤：第一步：先借助第一步：先借助3柱把柱把1柱上面的柱上面的n1个盘子移动到个盘子移动到2柱上，所需的移柱上，所需的移 动次数为动次数为f(n1)。第二步：然后再把第二步：然后再把1柱最下面的一个盘子移动到柱最下面的一个盘子移动到3柱上，只需要柱上，只需要1次次 盘子。盘子。
6、第三步：再借助第三步：再借助1柱把柱把2柱上的柱上的n1个盘子移动到个盘子移动到3上，所需的移动次上，所需的移动次 数为数为f(n1)。由以上由以上3步得出总共移动盘子的次数为：步得出总共移动盘子的次数为：f(n1)+1+f(n1)。所以：所以：f(n)=2 f(n1)+1 f(n)=2n-1问题问题：四柱问题：四柱问题【问题分析问题分析】：令令fi表示四个柱子时，把表示四个柱子时，把i个盘子从原柱移动到目标柱所需的最少移动次数。个盘子从原柱移动到目标柱所需的最少移动次数。j第一步：先把1柱上的前j个盘子移动到另外其中一个非目标柱（2或3柱均可，假设移到2柱）上，此时3和4柱可以作为中间柱。移
7、动次数为：fj。第二步：再把原1柱上剩下的i-j个盘子在3根柱子（1、3、4）之间移动，最后移动到目标柱4上，因为此时2柱不能作为中间柱子使用，根据三柱问题可知，移动次数为：2(i-j)-1。第三步：最后把非目标柱2柱上的j个盘子移动到目标柱上，次数为：fj。通过以上步骤我们可以初步得出：通过以上步骤我们可以初步得出：fi=2*fj+2(ij)1j可取的范围是可取的范围是1=jI，所以对于不同的所以对于不同的j，得到的得到的fi可能是可能是不同的，本题要求最少的移动次数不同的，本题要求最少的移动次数 fi=min2*fj+2(i-j)-1，其中1=jI const MaxNum=1000;va
8、r 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*F3i1+1;end;procedure
9、Run;var i,j:integer;minF4i,temp:double;begin for i:=2 to n do begin minF4i:=1e+100;for j:=1 to i1 do begin temp:=2*F4j+F3ij;if(temp minF4i)then minF4i:=temp;end;*F4i=min(2*F4j+F3ij);(1=j=i1)*F4i:=minF4i;end;writeln(F4n:0:0);end;begin Init;Run;end.问题问题：m柱问题柱问题【问题分析】：设F(m,n)为m根柱子,n个盘子时移动的最少次数：1、先把1柱上的
10、前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)2、平面分割问题平面分割问题问题问题问题的提出：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，求这些封闭曲线把平面分割成的区域个数。【问题分析】：设f(n)为n条封闭曲线把平面分割成的区域个数。由图4很容易得出：f(1)=
11、2；f(2)=4。假设当前平面上已有的假设当前平面上已有的n1条曲线将平面分割成条曲线将平面分割成f(n1)个区域，现在加个区域，现在加入第入第n条封闭曲线。第条封闭曲线。第n条曲线每与已有的条曲线每与已有的n1条曲线相交共有条曲线相交共有2(n1)个个交点，也就是说第交点，也就是说第n条曲线被前条曲线被前n1条曲线分割成条曲线分割成2(n1)段弧线，而每段弧线，而每一条弧线就会把原来的区域一分为二，即增加一个区域，所以共增加一条弧线就会把原来的区域一分为二，即增加一个区域，所以共增加2(n1)个区域个区域 F（n）=f（n1）+2(n1)问题问题问题的提出：一个z形曲线可以把一个平面分割成2
12、部分。如图所示。求n个z形曲线最多能把平面分割成多少部分。写出递推式f(n)。【问题分析】：根据上图容易得出：f（1）=2；f（2）=12。假设平面上已有n-1个z图形把平面分成了f（n-1）个区域。加入第n个z后，单独考虑第n个z的3条边，每一条边和前面的n-1个z共有3（n-1）个交点，即这条边被分成3（n-1）+1部分，所以增加3（n-1）+1个区域，3条边共增加3（3（n-1）+1）个区域。但是第n个z本身有2个交点，故少了2个区域，所以实际增加了3（3（n-1）+1）-2个区域。由以上得出：f（n）=f（n-1）+3（3（n-1）+1）-2 即：f（n）=f（n-1）+9n-8 初始
13、条件：f（1）=2问题问题：M分割平面分割平面问题二的扩展：在问题二的基础上进一步考虑：如果z图形扩展为m边的下列图形：看一下问题的解。通过上面的分析我们很容易知道：n个上述图形可以将平面划分的区域的递推关系：f（n）=f（n-1）+m（m（n-1）+1）-（m-1）初始条件：f（1）=23、Catalan数数问题一：凸问题一：凸n边形的三角形剖分边形的三角形剖分在一个凸在一个凸n边形中，通过不相交于边形中，通过不相交于n边形内部的对角线，把边形内部的对角线，把n边形拆分成若边形拆分成若干三角形，不同的拆分数目用干三角形，不同的拆分数目用f(n)表之，表之，f(n)即为即为Catalan数。例
14、如五边形数。例如五边形有如下五种拆分方案，故有如下五种拆分方案，故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个结点为根，左子树结点的个数
15、为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=i1,m1)问题二：问题二：集合划分问题。集合划分问题。设S是一个包含n个元素的集合，S=b1,b2,b3,bn,现需要将S集合划分为m个满足如下条件的集合S1,S2,S
16、m。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在子集时，则在子集时，则n1一定不在子集中，即在一定不在子集中，即在1，2，。，。，n2中选中选k1个元素，数目为个元素，数目为f(n2,k1)。当当n不在子集中时，则在不在子集中时，则在1，2，。，。，n1中选中选k个元素，数目为个元素，数目为f(n1,k)。所以：所以：
17、f(n,k)=f(n2,k1)+f(n1,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(
18、I-j,j)+f(I-1,j-1)边界条件：f（i，1）=1，f（i，j）=0，（Ij）二、递推式的求解方法：二、递推式的求解方法：1 递归函数递归函数用数组实现用数组实现求递推式的通项表达式：求递推式的通项表达式：31、迭加法、迭加法 32、待定系数法、待定系数法 33、特征方程法、特征方程法 34、生成函数法、生成函数法1、递归函数、递归函数 用递归函数来实现递推式是初学选手们采用最多的求解方法，只要设置正确的边界条件，相对来说比较容易实现。如：集合取数问题f(n,k)=f(n-2,k-1)+f(n-1,k)边界条件：F(n,1)=n,f(n,k)=0 (n=k)function f(n,
19、k:integer):integer;begin if k=1 then f:=n else if n1,m1)边界条件：S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(kn)。var s:array1.100,1.100 of longint;n,m,i,j:integer;begin read(n,m);fillchar(s,sizeof(s),0);for i:=1 to n do si,1:=1;for i:=1 to m do si,i:=1;for i:=2 to m do for j:=i to n do sj,i:=i*sj-1,i+sj-1,i-1;writeln
20、(sn,m);end.3求递推式的通项表达式求递推式的通项表达式 31、迭加法一般符合下列形式的递推式可以使用迭代法。F(n)=f(n-1)+g(n)其中：g(n)是关于n的线性表达式。F(2)=f(1)+9*2-8F(3)=f(2)+9*3-8F(4)=f(3)+9*4-8F(n)=f(n-1)+9*n-8以上以上n1个等式相加得到：个等式相加得到：f(n)=f(1)+9*(2+3+4+n)8*n即：即：f(n)=9*n*n/27*n/2+1如：平面分割问题二如：平面分割问题二:f（n）=f（n1）+9n8初始条件：初始条件：f（1）=2 32、待定系数法、待定系数法 适合下列格式的递推式：
21、F(n)=a*f(n-1)+g(n)a1例1：Hanoi塔塔三柱问题：f(n)=2 f(n-1)+1，边界条件：f(1)=1令：f(n)+A=2(f(n-1)+A)A为待定系数求得A=1,即：f(n)+1=2(f(n-1)+1)由等比数列性质得出：f(n)+12n-1(f(1)+1)=2n所以：f(n)2n1例例2：求求F(n)=3f(n1)+n2+n+2的通项。的通项。令令:f(n)+An2+Bn+c=3(f(n1)+A(n1)2+B(n1)+c)A，B，C为待定系数。为待定系数。由于上述恒等成立，得：由于上述恒等成立，得：2A=12B6A=03+3B+2C=0求出：求出：A,B,C后，从而
22、得出后，从而得出f(n)的通项的通项 33、特征方程法、特征方程法 如果如果a1,ak是常数，且是常数，且ak=0,nk，则递推关系则递推关系 F(n)=a1f(n1)+a2f(n2)+akf(nk)称为称为k阶常系数线性齐次递推关系。阶常系数线性齐次递推关系。它的特征方程是：它的特征方程是：Xk a1Xk1 a2Xk2ak=0只要求出特征方程的根，再由初始条件表达式中的待定系数，只要求出特征方程的根，再由初始条件表达式中的待定系数，便可以得到原递推关系的解。便可以得到原递推关系的解。如果特征方程有如果特征方程有k个互不相同的解个互不相同的解X1,X2,.Xk，则通解为：则通解为：F(n)=c
23、1X1n+c2X2n+.+ckXknc1,c2ck待定。待定。例：Fibonacci数列数列F(n)=f(n-2)+f(n-1);f(1)=1;f(2)=1解：特征方程：X2-X-1=0解得：x1=x2=则：f(n)=C1*X1n+C2*X2n又因为：f(1)=1 f(2)=1所以：C1*X1+C2*X21 C1*X12+C2*X221得出：C1=C2=-34、生成函数法、生成函数法这种方法的基本思想原理：已知数列：a0,a1,a2an构造函数：g（x）=a0+a1x+a2x2+aixi+anxn.g(x)称为数列a0,a1,a2an的生成函数。因此，我们要想求系数an，只要求出g(x)，然后把g(x)展开成幂级数。f(x)=f(x0)+f1(x0)(x-x0)+f2(x0)(x-x0)2/2!+f(n)(x0)(x-x0)n/n!+展开式中xn的系数就是an的表达式。：anf(n)(x0)/n!如：g(x)=(1+x)n=a0+a1x+a2x2+aixi+anxn.展开成幂级数：(1+x)n=Cn0+Cn1X+Cn2X2+CniXi+.+CnnXn比较系数得：ai=Cni现在的问题是现在的问题是1、由已有的递推关系怎样构造求出、由已有的递推关系怎样构造求出g(x)。2、把把g(x)展开成幂级数展开成幂级数例：二叉树数目二叉树数目F(n)=f（0）=1；f(1)=1求f(n)