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

第10章 递推方程与生成函数 第10章 递推方程与生成函数 10.1 递推方程及其应用 10.2 生成函数及其应用 10.3 指数生成函数及其应用 10.4 Catalan数与Stirling数 10.1 递推方程及其应用 10.1.1 递推方程的定义及实例 10.1.2 常系数线性齐次递推方程的求解 10.1.3 常系数线性非齐次递推方程的求解 10.1.4 递推方程的其他解法 10.1.5 递推方程与递归算法 递推方程的定义 递推方程的实例——计数编码 递推方程的实例——Hanoi塔 递推方程的实例——算法分析 常系数线性齐次递推方程的公式解法 特征方程、特征根 递推方程的解与特征根的关系 解的线性性质 无重根下通解的结构 求解实例 有重根下通解的结构 求解实例 特征方程与特征根 递推方程解与特征根的关系 解的线性性质 无重根下通解的结构 定理的证明 求解实例 有重根下求解中的问题 有重根下的通解结构 求解实例 常系数线性非齐次递推方程求解 递推方程的标准型 通解结构 特解的求法 多项式函数 指数函数 组合形式 递推方程的标准型及通解 特解的形式——多项式 实例 实例(续) 特解的形式——指数 特解的形式——指数(续) 特解的组合形式 递推方程的其他解法 换元法 迭代归纳法——递归树 差消法 尝试法 应用实例 换元法 实例 迭代归纳法——归并排序 迭代归纳法——错位排列 差消法——化简递推方程 积分近似 递归树——二分归并排序 尝试法 尝试法(续) 积分近似 分治策略与递归算法 分治策略与递归算法(续) 分治策略与递归算法(续) 实例——位乘问题 例17 T(n) n-1 T(n/2) T(n/2) n/2-1 n/2-1 T(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?1 n?2 n?4 . . . n?2k?1 k 层 (1) T(n)=C, 左边=O(1) 例18 (2) T(n)=cn, 左边=cn, (3) T(n)=cn2, 左边=cn2 (4) T(n)=cnlogn , 左边=cnlogn n为输入规模，n/b为子问题输入规模， a为子问题个数，d(n)为分解及综合的代价 (1) d(n)=c 实例： 二分有哪些信誉好的足球投注网站 W(n) = W(n/2) + 1 a = 1, b = 2, d(n) = c W(n) = O(logn) * 定义10.1 设序列 a0, a1, …, an, …, 简记为{ an }. 一个把 an 与 某些个ai (in) 联系起来的等式叫做关于序列 { an } 的递推方 程. 当给定递推方程和适当的初值就唯一确定了序列. 例如， Fibonacci数列：1，1，2，3，5，8，… ，记作{ fn }. 递推方程 fn = fn?1 + fn?2 初值 f0 = 1，f1 = 1 阶乘计算数列： 1，2，6，24，5！，…, 记作{ F(n)} 递推方程 F(n) = nF(n?1) 初值 F(1) = 1 化简得 an = 6an?1 + 8n?1, 可以解得 an=(6n+8n)/2 例1 一个编码系统用八进制数字对信息编码，一个码是 有效的当且仅当含有偶数个7, 求 n 位长的有效码字有多 少个？ 解 设所求有效码字为 an个. 分类处理、分步处理得到递 推方程和初值如下： an=7an?1+ 8n?1 ? an?1 a1=7 例2 从A柱将这些圆盘移到C柱上去. 如果把一个圆盘从 一个柱子移到另一个柱子称作一次移动，在移动和放置 时允许使用B柱，但不允许大圆盘放到小圆盘的上面. 问 把所有的圆盘的从A移到C总计需要多少次移动？ 初值是 T(1)=1 可证明解是 T(n)=2n?1 移动n个盘子的总次数为T(n). 因此得到递推方程 T(n) = 2T(n?1) +1