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

递推关系的建立及其求解方法 王桐林 一、递推式的建立 0 、 Fibonacci数列 1、Hanoi塔问题 问题: 三柱问题 问题：四柱问题 问题：m柱问题 2、平面分割问题 问题：封闭曲线分割平面 问题：Z分割平面 问题：M分割平面 3、Catalan数 问题一：凸n边形的三角形剖分 问题二：二叉树数目 问题三：出栈序列 4、第二类Stirling数 问题一：放置小球 问题二：集合划分问题 5、其他 问题一：集合取数问题 问题二：整数划分问题 二、递推式的求解方法： 1 递归函数 用数组实现 求递推式的通项表达式： 31、迭加法 32、待定系数法 33、特征方程法 34、生成函数法 三、递推的形式 顺推法和倒推法 lFibonacci数列的代表问题是由意大利著名数 学家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(Fn1)，这就在数的序列中，建立 起后项和前项之间的关系。然后从初始条件（或是最终 结果）入手，按递推关系式递推，直至求出最终结果（ 或初始值）。很多问题就是这样逐步求解的。 对一个试题，我们要是能找到后一项与前一项的关系并 清楚其起始条件（或最终结果），问题就可以递推了， 接下来便是让计算机一步步了。让高速的计算机从事这 种重复运算，真正起到“物尽其用”的效果。 递推概念 l给定一个数的序列H0,H1,Hn,若存 在整数n0，使当n=n0时,可以用等号(或大 于号、小于号)将Hn与其前面的某些项 Hn(0i2)个盘子时，我们可以利用下列步骤： 第一步：先借助3柱把1柱上面的n1个盘子移动到2柱上，所需的移 动次数为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、4）之间移动，最后 移动到目标柱4上，因为此时2柱不能作为中间柱子使用，根据三柱问题可知， 移动次数为：2(i-j)-1。 第三步：最后把非目标柱2柱上的j个盘子移动到目标柱上，次数为：fj。 通过以上步骤我们可以初步得出： fi = 2*fj+2(ij)1 j可取的范围是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)是从集合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再分成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; 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(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(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、特征方程法 如果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*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)(x