离散数学101递推方程与生成函数

1、课件1第第1010章章 递推方程与生成函数递推方程与生成函数课件2第第10章章 递推方程与生成函数递推方程与生成函数 10.1 递推方程及其应用递推方程及其应用 10.2 生成函数及其应用生成函数及其应用 10.3 指数生成函数及其应用指数生成函数及其应用 10.4 catalan数与数与stirling数数课件310.1 递推方程及其应用递推方程及其应用 10.1.1 递推方程的定义及实例递推方程的定义及实例 10.1.2 常系数线性齐次递推方程的求解常系数线性齐次递推方程的求解 10.1.3 常系数线性非齐次递推方程的求解常系数线性非齐次递推方程的求解 10.1.4 递推方程的其他解法递推

2、方程的其他解法 10.1.5 递推方程与递归算法递推方程与递归算法课件4递推方程的定义递推方程的定义定义定义10.1 设序列设序列 a0, a1, , an, , 简记为简记为 an . 一个把一个把 an 与与某些个某些个ai (i0课件29实例实例解解 h(k) = 2 h(k1) + 2k1 h(1) = 1 令令 h*(k) = p1k2k + p2 , 解得解得 p1=p2=1 h*(k) = k2k + 1通解通解 h(k) = c 2k + k2k + 1 代入初值得代入初值得 c = 1 h(k) = 2k + k2k +1 w(n) = n log n n + 1 0 (1)

3、2 , 1 ) /2 (2 )(wnnnwnwk例例1414 归并排序归并排序课件30迭代归纳法迭代归纳法归并排序归并排序 0 (1)2 , 1 ) /2 (2 )(wnnnwnwk例例151log122)12.22(2(1)2.122222)2(2122212)2(221222)2(21212)2(2 2 12 )2 (2 )(2123323222121 nnnkkwwwwwwnwkkkkkkkkkkkkkkkkkkkkkk解解课件31迭代归纳法迭代归纳法错位排列错位排列例例16 dn = (n1)(dn1 + dn2) 0,)1()1(2)1(.)1(112122211 dndddddnd

4、nddnnnnnnnnn解：解：!1)1(.! 21! 111 !)1()1(.)1(4).1()1(3).1(2).1(.)1()1()1)(1()2)(1()1()1(13211232nnnnnnndnnnnndnnnndnndnnnnnnnnnn 课件32)log()()(log31.1112)1(31.1111)1(1)()()1()1()()()1(2)1()1()()1()(2)1()1()(2)(212211nnontnonnctnncncnntnntnontnnntnontntnnntncitntncnitnntnini 差消法差消法化简递推方程化简递推方程 0)1(2),()

5、(2)(11tnnoitnntni例例17课件33)(log2ln)1ln(ln131.1111212nonxdxxnnnn 积分近似积分近似课件34递归树递归树二分归并排序二分归并排序t(n)n-1t(n/2) t(n/2)n/2-1 n/2-1t(n/4) t(n/4) t(n/4) t(n/4)n/4-1 n/4-1 n/4-1 n/4-1 .1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 t(n) = nk (1+2+2k 1) = nk (2k 1) = n log n n + 1 n 1n 2n 4. n 2k 1k层层knnntnt2 , 1 ) /2 (2 )(

6、 课件35(1) t(n)=c, 左边左边=o(1)尝试法尝试法1)(2)(11 nitnntni)(1221)1(2nonnccnncn 右右边边1)1(1)1(12)1)(11(21211 cncnncnnnncncinni右边右边例例18 (2) t(n)=cn, 左边左边=cn, 课件36尝试法尝试法(续续)(321)(3212223112noncnnocnnncinni 右边右边)(log)2ln21(log1)log(2ln4log221log22211noncncnnnnonnnncniincni 右边右边(3) t(n)=cn2, 左边左边=cn2(4) t(n)=cnlogn

7、 , 左边左边=cnlogn 课件37)442ln24(2ln1)4ln2(2ln14ln22ln1ln2lnlog2222222 nnnxxxxdxxxdxxnnn积分近似积分近似)log(2ln4log2log2211nnonnniini 课件38ankbbnaaloglog 分治策略与递归算法分治策略与递归算法n为输入规模，为输入规模，n/b为子问题输入规模，为子问题输入规模，a为子问题个数，为子问题个数，d(n)为分解及综合的代价为分解及综合的代价)/()()/(.)/()/()/(.)()/()/()(1)1(),()/()(10221122ikiikkkkkkkkbndaandbn

8、adbnabndabntandbnadbntanttbnndbnatnt 课件39akikiikbnabndaantlog10),/()( 分治策略与递归算法分治策略与递归算法(续续)(1) d(n)=c 1)(log)(1)()(11)(loganokcokcaanoaoaacantkakkkb 实例：实例： 二分搜索二分搜索 w(n) = w(n/2) + 1 a = 1, b = 2, d(n) = c w(n) = o(logn) 课件40分治策略与递归算法分治策略与递归算法(续续) (2) d(n)=cn banobabacababacnabannocnknbanobabacnnba

9、cnabcnaantakkkkkkakiikikiikbb)(1/1/1)/()log()(1/1)/()()(loglog1111实例：归并排序实例：归并排序 w(n) = 2w(n/2) + n 1 a = 2, b = 2, d(n) = o(n), w(n)= o(nlogn) 课件41实例实例位乘问题位乘问题位乘问题：位乘问题：x,y 为为 n 位二进制数，位二进制数，n=2k, 求求 xy 一般方法：一般方法：w(n)= o(n2)分治法：令分治法：令x = a2n/2+b, y = c2n/2 +d, 则则 xy = ac 2n + (ad+bc)2n/2 + bd w(n)= 4 w(n/2) + cn w(1