第五章 递归关系及解法

1、第五章第五章 递推关系及其解法递推关系及其解法5.1 递归关系的建立递归关系的建立-在计算机科学特别是算法分析中有广泛的应用定义定义5.1.15.1.1 设a0,a1,a2,an,为一序列,把该序列中an与它前面的几个ai关(0in-1)联起来的方程称为一个递归关系. 例例1 1(“Hanoi塔”问题)：这是一个组合数学中的著名问题。n个大小不一的圆盘依其半径大小，从下而上套在A柱上，如下图示。现要求将所有的圆盘从A柱上全部转移到C柱上,每次只允许从一个柱子上转移一个盘子到另一柱子上，且在转移过程中不允许出现大盘放在小盘上方。试问要转移多少次才能将柱A上的n个盘移到C柱上。A B C 例例2

2、2 “Fibonacci兔子问题”：从某年某月(设为第0月)开始,把雌雄各一的一对小兔放入养殖场,假定两个月后长成成年兔,并同时(即第二个月)开始每月产雌雄各一的一对小兔,新增的小兔也按此规律繁殖,问第n个月末养殖场共有多少对兔子? 第n月的兔子包括两部分:上月留下的和当月新生的,而新生的小兔数即为前月末的兔子数,所以 Fn=Fn-1+Fn-2nFibonacci序列的性质:5.2 常系数线性齐次递归关系的解法常系数线性齐次递归关系的解法 定义定义5.2.1 序列a0,a1,a2,an,中相邻的k+1项之间的关系为 则称之为序列的k阶常系数线性齐次递归关系,其中系数bi为常数,i=1,2,k,

3、且bk0。n定义定义5.2.2 与(5.2.1)相联系的方程 称之为递归关系(5.2.1)的特征方程，其根称为递归关系式的特征根。) 1 . 2 . 5()(, 02211knabababaknknnn)2 . 2 . 5()(, 02211knbxbxbxkkkk特征方程的根与递归关系的解之间的关系：特征方程的根与递归关系的解之间的关系： 1.特征根无重根特征根无重根 定理定理5.2.1 若q 0, an=qn为递归关系(5.2.1)的解当且仅当q为特征方程(5.2.2)的根。 定义定义5.2.3 称式 为递归关系(5.2.1)的初值条件。) 1 . 2 . 5(,111100kkhahah

4、an定理定理5.2.2 若q1,q2,qk为递归关系式(5.2.1)的特征根，c1,c2,ck为任意常数，则 为递归关系(5.2.1)的解。n定义定义5.2.4 若对递归关系(5.2.1)的任意一个解an，都存在一组常数c1,c2,ck使得 则称该式为递归关系式(5.2.1)的通解。n定理定理5.2.3 若q1,q2,qk为递归关系式(5.2.1)的k个互不相同的特征根，则式(5.2.4)为(5.2.1)的通解。,2211nkknnnqcqcqca)4 . 2 . 5(,2211nkknnnqcqcqca 例例1 求Fibonacci序列的通项。 例例2 求解递归关系. 0, 2, 1)3(,

5、22210321aaanaaaannnn 注：若特征根有复根，复根成对出现，故设 则通解可表示为 其中 ,21ixix,sincos)()(212211ncncxAxAannnnn. )( i,arctan,21221122AAcAAc 例例3 求解递归关系. 0, 1)2(,2121aanaaannnn2.特征根有重根特征根有重根 定理定理5.2.4 若递归关系(5.2.1)的特征方程(5.2.2)有一个m重根q，则qn,nqn,nm-1qn均为(5.2.1)的解。 定理定理5.2.5 设q1,q2,qt分别为特征方程(5.2.2)的相异的m1,m2,mt重根,且 则递归关系(5.2.1)的

6、通解为,1kmtiitimjnijijniqnca111. 例例4 求解递归关系 例例5 求解递归关系. 3, 2)3(,22121aanaaannn. 2, 1, 0, 1)4(,25332104321aaaanaaaaannnnn5.3 常系数线性非齐次递归关系的解法常系数线性非齐次递归关系的解法 定义定义5.3.1 序列a0,a1,a2,an,中相邻的k+1项之间的关系为 则称之为序列的k阶常系数线性非齐次递归关系,其中系数bi为常数,i=1,2,k,bk0,f(n) 0,nk 。 定义定义5.3.2 在式(5.3.1)中,若f(n)=0, 则称 为由式(5.3.1)导出的常系数线性齐次

7、递归关系。) 1 . 3 . 5()(),(2211knnfabababaknknnn)2 . 3 . 5()(, 02211knabababaknknnn 定理定理5.3.1 若 为(5.3.1)的一个特解,而 ( )是由(5.3.1)导出的线性齐次递归关系(5.3.2)的通解,则 为(5.3.1)的通解。n注：由定理5.3.1知, 要求(5.3.1)的通解,只要求它的一个特解及导出的齐次递归关系的通解即可。对非齐线性递归关系的特解, 针对f(n)的特殊形式有以下情形:nakiniinqca1*timjnijijniqnca111*nnnaaa 1.f(n)是n的t次多项式n 1不是齐次递归

8、关系(5.3.2)的特征根 这时,(5.3.1)的特解形式为 其中 为待定常数。n例1 求解“Hanoi塔”问题的递归关系n例2 求解递归关系,1110ttttnAnAnAnAattAAAA,110. 1)2(1211anaann. 3) 1(3201annaannn1是齐次递归关系(5.3.2)的m重特征根(m1) 这时,(5.3.1)的特解形式为 其中 为待定常数。n例3 求解递归关系,)(1110mttttnnAnAnAnAattAAAA,110. 2)2() 1(211annaann 2 f(n)是n的形式 不是导出的齐次线性递归关系的特征根 这时,(5.3.1)的特解形式为 其中 A

9、为待定常数。例例4 求解递归关系 .nnAa. 1, 0)2(31071021aanaaannnnn是导出的齐次线性递归关系的m重特征根(m1) 这时,(5.3.1)的特解形式为 其中 A为待定常数。 例例5 求解递归关系.nmnnAa.24421的通解nnnnaaanf(n)= n g(n),其中g(n)为n的t次多项式, 是导 出的齐次线性递归关系的m重特征根(m0) 这时,(5.3.1)的特解形式为 其中 为待定常数。n例例6 求解递归关系.)(1110nmttttnnAnAnAnAattAAAA,110. 1, 0)2()5(21031021aannaaannnn5.4 递归关系的其他

10、解法递归关系的其他解法 前面方法当k较大时，面临求解高阶方程及k个未知数k个方程的方程组, 求解困难问题。本节再介绍一些方法。 一、迭代法一、迭代法 例1 求解递归关系 二、归纳法二、归纳法 例2 求解递归关系. 1) 1(01annaann. 2)2() 1(211annaann三、母函数法三、母函数法 主要思想:n用f(x)表示序列a0,a1,a2,an,的普通母函数,即n利用递归关系an的表达式与(5.4.1)间的关系将(5.4.1)化为关于f(x)的方程，即有 g(f(x)=0;n解出f(x)；n将f(x)的表达式展开成幂级数的形式，即得an的初等表达式.) 1 . 4 . 5(,)(

11、02210nnnnnxaxaxaxaaxf 例例3 求解递归关系 例例4 求解递归关系. 1, 1)2(,1021FFnFFFnnn. 1,0)2(,2)2() 1(1021aanaanannnnn四、代换法四、代换法 将序列a0,a1,a2,an,的递归关系转换为关于新序列b0,b1,b2,bn,的递归序列。 例例5 求解递归关系n五、将常系数线性非齐次递归关系转化为常系数齐次递归五、将常系数线性非齐次递归关系转化为常系数齐次递归关系关系 例例6 求an-2an-1=3的通解。 例例7 求. 2) 1(,2) 1(11anannannn. ?1nkk5.5 Stirling数数 一、第一、第

12、1类类Stirling数数 令 ，若 则称S1(n,k)为第1类Stirling数，即为多项式xn中xk的系数。 约定：约定：当nk时， S1(n,k)=0。定理定理5.5.1 第1类Stirling数S1(n,k)满足 ) 1()2)(1(nxxxxxn ,),(01nkknxknSx. 0,0)0 ,(, 0)0 , 0()0, 0(, ),() 1,(), 1(11111nnSSknknnSknSknS 由定理5.4.1得第1类Stirling数S1(n,k)的数值：n k1234567112-1132-314-611-61524-5035-1016-120274-22585-15177

13、20-17641624-735175-211 二、第二、第2类类Stirling数数 若 则称S2(n,k)为第二类Stirling数。显然，当nk时， S2(n,k)=0。n定理定理5.5.2 第2类Stirling数S2(n,k)满足 ,),(02nkknxknSx. 0,0)0 ,(, 1)0 , 0()0, 0(, ),() 1,(), 1(22222nnSSknknkSknSknSS2(n,k)的组合意义涉及集合的划分。定理定理5.5.3 S2(n,k)为n个元素的集合划分成k个不相交的非空子集的方式数。 证明证明 设A(n,k)为n个元素的集合划分成k个不相交的非空子集的方式数，只

14、要证明A(n,k)满足定理5.5.2即可。 给定一个n+1个元素的集合a1,a2,an+1,将它划分为k个不相交的非空子集,分以下两种情况: (1) an+1为k个子集中的一个子集，则将a1,a2,an划分为k-1个子集的方式数为A(n,k-1)。 (2) an+1不为k个子集中的一个子集，则an+1必为某个子集中的元素。这时，先将a1,a2,an划分为k个子集共有A(n,k)种方式，然后将an+1加到k个子集中的某一个，共有k种方式，从而得总的划分数为kA(n,k)。 由加法原理， a1,a2,an+1划分为k个子集的方式数为 A(n,k-1)+ kA(n,k)。 所以有 A(n+1,k)=

15、A(n,k-1)+ kA(n,k)。 又将0 个元素的集合划分为0个不相交子集的方式数为1，所以A(0,0)=1。 另一方面，不可能将n个元素的集合中的元素不放进任何一个集合中去，所以A(n,0)=0。 这样， A(n,k)满足定理5.5.3，所以 A(n,k) =S2(n,k)。 说明：说明： (1)把n个不同的球放入k 个相同的盒子而无一空盒，等价于将n个元素的集合划分为k个不相交的非空子集，所以把n个不同的球放入k个相同盒子而无一空盒的放法共有S2(n,k)种。 (2) S2(n,k)具有以下性质： S2(n,n)=1, S2(n,k)=0 (nk, 或 k=0n)； S2(n,2)=2n-1-1; S2(n,n-1)=C(n,2)。 例例2 设m,n均为正整数，mn。用组合分析的方法证明证明证明 设有n只不同的球，m个盒子，它们的编号依次为1,2,m。把这n个球放入盒子中，允许有空盒且不限制放入盒子内