《递推关系的建立及其求解方法2》由会员分享，可在线阅读，更多相关《递推关系的建立及其求解方法2（42页珍藏版）》请在金锄头文库上搜索。
1、递推关系的建立及其求解方法王桐林 一、递推式的建立0 、 Fibonacci数列 1、Hanoi塔问题问题: 三柱问题问题：四柱问题问题：m柱问题2、平面分割问题问题：封闭曲线分割平面问题：Z分割平面问题：M分割平面3、Catalan数问题一：凸n边形的三角形剖分问题二：二叉树数目问题三：出栈序列4、第二类Stirling数 问题一：放置小球问题二：集合划分问题5、其他问题一：集合取数问题问题二：整数划分问题二、递推式的求解方法：1 递归函数用数组实现求递推式的通项表达式：31、迭加法32、待定系数法33、特征方程法34、生成函数法三、递推的形式 顺推法和倒推法lFibonacci数列的代表问
2、题是由意大利著名数 学家Fibonacci于1202年提出的“兔子繁殖问题 ”(又称“Fibonacci问题”)。l问题：一个数列的第0项为0，第1项为1，以后 每一项都是前两项的和，这个数列就是著名的 裴波那契数列，求裴波那契数列的第N项。 1、Fibonacci数列解答 由问题,可写出递推方程算法： F0 := 1; F1 := 2; FOR i := 2 TO N DO FI := FI 1 + FI 2;总结 从这个问题可以看出，在计算裴波那契数列的每一项目 时，都可以由前两项推出。这样，相邻两项之间的变化 有一定的规律性，我们可以将这种规律归纳成如下简捷 的递推关系式：Fn=g(Fn
3、1)，这就在数的序列中，建立 起后项和前项之间的关系。然后从初始条件（或是最终 结果）入手，按递推关系式递推，直至求出最终结果（ 或初始值）。很多问题就是这样逐步求解的。 对一个试题，我们要是能找到后一项与前一项的关系并 清楚其起始条件（或最终结果），问题就可以递推了， 接下来便是让计算机一步步了。让高速的计算机从事这 种重复运算，真正起到“物尽其用”的效果。递推概念l给定一个数的序列H0,H1,Hn,若存 在整数n0，使当n=n0时,可以用等号(或大 于号、小于号)将Hn与其前面的某些项 Hn(0i2)个盘子时，我们可以利用下列步骤： 第一步：先借助3柱把1柱上面的n1个盘子移动到2柱上，所
4、需的移 动次数为f(n1)。 第二步：然后再把1柱最下面的一个盘子移动到3柱上，只需要1次 盘子。 第三步：再借助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柱可以作为中间柱。移动次数为：fj。 第二步：再把原1柱上剩下的i-j个盘子在3根柱子（1、3、
5、4）之间移动，最后 移动到目标柱4上，因为此时2柱不能作为中间柱子使用，根据三柱问题可知， 移动次数为：2(i-j)-1。第三步：最后把非目标柱2柱上的j个盘子移动到目标柱上，次数为：fj。 通过以上步骤我们可以初步得出： fi = 2*fj+2(ij)1j可取的范围是11,m1)问题二：集合划分问题。设S是一个包含n个元素的集合，S=b1,b2,b3,bn,现需要将S集合 划分为m个满足如下条件的集合S1,S2, Sm。Si;SiSj=;S1S2Sm=S; (11,m1) 边界条件：S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(kn)。5 、其他： ）集合取数问题设f(n,k)
6、是从集合1，2，。，n中能够选择的没有两个连续 整数的k个元素子集的数目，求递归式f(n,k)。【问题分析】： N有两种情况： 当n在子集时，则n1一定不在子集中，即在1，2，。，n2中选k 1个元素，数目为f(n2,k1)。 当n不在子集中时，则在1，2，。，n1中选k个元素，数目为f(n 1,k)。 所以：f(n,k)= f(n2,k1) +f(n1,k) 边界条件：F(n,1)=n, f(n,k)=0 ( n=2，可以先那出j个1分到 每一份，然后再把剩下的I-j分成j份即可，分法有：f(I-j,j).第二类 : j份中至少有一份为1的分法，可以先那出一个1作为单独的1份， 剩下的I-1
7、再分成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， （I1,m1) 边界条件：S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(kn)。var s:array1100,1100 of longint;n,m,i,j:integer; beginread(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 dofor j:=i to n do
8、sj,i:=i*sj-1,i+sj-1,i-1;writeln(sn,m); end.3求递推式的通项表达式 31、迭加法 一般符合下列形式的递推式可以使用迭代法。F(n)=f(n-1)+g(n)其中：g(n)是关于n的线性表达式。F(2)=f(1)+9*2-8 F(3)=f(2)+9*3-8 F(4)=f(3)+9*4-8 F(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、待定系数法 适合下列格式的递推式： F
9、(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=1 2B6A=0 3+3B+2C=0 求出：A,B,C后，从而得出f(n)的通项 33、特
10、征方程法如果a1, ,ak是常数，且akk，则递推关系F(n)= a1f(n1)+a2f(n2)+akf(nk) 称为k阶常系数线性齐次递推关系。 它的特征方程是：Xk a1Xk1 a2Xk2ak=0 只要求出特征方程的根，再由初始条件表达式中的待定系数， 便可以得到原递推关系的解。 如果特征方程有k个互不相同的解X1,X2,Xk，则通解为： F(n)=c1X1n+c2X2n+.+ckXkn c1 ,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*X
11、2n又因为：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)
