计算机算法分析与设计【常用的数学工具】非常实用哦.doc

Design and Analysis of Algorithm Common Math Tool 第2章 常用的数学工具Common Math Tool第1章 算法引论（6学时）第2章 常用数学工具（3学时）第3章 NP完全性理论（4.5学时）第4章 蛮力法（3学时）第5章递归与分治策略（4.5学时）第6章 减冶法（3学时）第7章 动态规划（3学时）第8章贪心算法（4.5学时）第9章 回溯法（4.5学时）第10章 分支限界法（4.5学时）第11章 概率算法（4.5学时）第12章 近似算法（3学时）总复习 （3学时）本章要点：u 2.1 生成函数及其性质u 2.2用生成函数求解递归方程u 2.3用特征方程求解递归方程u 2.4 用递推方法求解递归方程2.1 生成函数及其性质一、生成函数的定义生成函数（也叫“母函数”， generating function）？构造这么一个多项式函数g(x)，使得x的n次方系数为f(n)。于是，如果有系数f(1)=7,f(2)=4,f(3)=16,f(4)=0,f(5)=1,等等， 则f函数的生成函数g(x)=7x+4x2+16x3+x5+.这就是生成函数。关键点：其作用是什么呢？生成函数可以将某些生成函数可以化简为一个很简单的函数。也就是说，不一定每个生成函数都是用一长串多项式来表示的。比如，这个函数f(n)=1 （n当然是属于自然数的），它的生成函数就应该是：g(x)=1+x+x2+x3+x4+.（每一项都是一，所以有常数项）这就是一个有无穷多项的等比数列求和的问题。如果-1x1，那么g(x)=1/(1-x)无穷级数是研究有次序的可数无穷个数或者函数的和的收敛性及和的数值的方法，理论以数项级数为基础，数项级数有发散性和收敛性的区别。只有无穷级数收敛时有一个和；发散的无穷级数没有和。算术的加法可以对有限个数求和，但无法对无限个数求和，有些数列可以用无穷级数方法求和。 包括数项级数、函数项级数（又包括幂级数、Fourier级数）。在研究生成函数时，我们都假设级数收敛，因为生成函数的x没有实际意义，我们可以任意取值。于是，我们就说，f(n)=1的生成函数是g(x)=1/(1-x)。另外，1. 一些具有实际意义的组合问题也可以用像这样简单的一个函数全部表示出来。2. 可以把一些诸如递归变化的函数通过生成函数求出其通项公式，如汉诺塔问题及菲波那契序列问题等。組合數學中的生成函數: 例 a.1考慮恆等式 (1+ax)(1+bx)(1+cx)=1+(a+b+c)x+(ab+bc+ac)x2+abcx3 如將 a,b,c 看作代表三物件，它的右邊是一多項式，其係數恰代表了將 a,b,c 作組合的各種可能。常數項 1 表示在三物件中一個都不取；x 的係數 a+b+c 表示在 a,b,c 中取一個的各種組合，即或取 a，或取 b，或取 c；x2 的係數 ab+bc+ac 表取二個的各種組合；x3 之係數表示了三個皆取的唯一方法。在這裏可能產生各種情形是用 + 號連接，同時發生之事件則用乘法表示。例 a.2設有 5 個球 a,a,a,b,c，其中三個球 a 完全一樣，則恆等式 其中 xr 之係數表示了選取 r 個的各種可能組合 ()。 在排列組合問題中，加法原則與乘法原則是大家熟知的兩個法則。加法原則是講如一事件可能發生情況有 m 種，另一種事件可能發生情況有 n 種，則這兩種事件其一發生情況有 m+n 種。乘法原則是講如一事件可能發生情況有 n 種，另一事件可能發生情況有 m 種，則這兩事件同時發生情況有 nm 種。我們在上面兩例用到的是一種符號運算，它遵從這兩法則。在 例 a.2，因子 1+ax+a2x2+a3x3 表示了或不取 a，或取一個 a，或取 2 個 a，或取三個 a 的各種情況；而在 例 a.1 中，(1+ax)(1+bx) 表示了如果 a,b 被允許同時選取時可能產生之各種情況。 在很多場合中，我們只對事件發生可能之個數有興趣，而不在乎事件發生的具體形式。這時我們可以取代表不同物件的符號 a,b,c 等均為 1，例如在 例 a.1 中，令 a=b=c=1，則 (1+x)(1+x)(1+x)=1+3x+3x2+x3 其中 xr 之係數為在三個物件中取 r 個的組合數。 定义2.1 令是一个实数序列，构造如下的函数：（2.1.1）则函数称为序列的生成函数。例：函数则函数便是序列的生成函数。二、生成函数的性质1. 加法 设是序列的生成函数，是序列的生成函数，则（2.1.2）是序列的生成函数。2移位 设是序列的生成函数，则（2.1.3）是序列的生成函数。3乘法 设是序列的生成函数，是序列的生成函数，则 （2.1.4）是序列的生成函数，其中，4. z变换 设是序列的生成函数，则（2.1.5）是序列的生成函数。特别地，有：（2.1.6）所以，是序列的生成函数。当时，有：（2.1.7）则是序列1,1,1,的生成函数。利用：（2.1.8）可以去掉级数中的奇数项；同样，利用（2.1.9）可以去掉级数中的偶数项。5微分和积分 设是序列的生成函数，对求导数（2.1.10）显然，是序列的生成函数。同样，对求积分（2.1.11）则积分是的生成函数。如果对（2.1.7）式求导数，可得：（2.1.12）则是算术级数1,2,3的生成函数。如果对（2.1.7）式求积分，可得：（2.1.13）则是调和级数的生成函数。2.2 用生成函数求解递归方程例2.1 汉诺塔（Hanoi）问题。宝石针的编号为、，针串着64片金盘。希望把它们移到针或针。是金盘的数量，是移动个金盘的移动次数(参考第5章 递归与分治策略法，Page.29)1 当时， =1。2 当时， 。3 当时， 。递归关系式：（2.2.1）用作为系数，构造一个生成函数：令由（2.2.1）及（2.1.7）式得：所以，令：有：求得。所以： ，它是式中第项的系数。当时，移动次数为。例2.2 菲波那契序列（Fibonacci）问题。菲波那契数列指的是这样一个数列： 1，1，2，3，5，8，13，21 这个数列从第三项开始，每一项都等于前两项之和。设：、表示第个月小兔子、大兔子的数目，及第个月兔子的总数目。则：（2.2.2）（2.2.3）（2.2.4）第一式：第个月大兔子的数量，为前一个月大兔子的数量加上前一个月小兔子的数量；第二式：第个月小兔子的数量，为前一个月大兔子的数量；第三式：表示第个月兔子的总量为该月大兔子的数量及小兔子的数量之和。递归方程：（2.2.5）用作为系数，构造生成函数：令：所以，有：有：解得：把、代入，得到：令，则有：所以，第项系数为：2.3 用特征方程求解递归方程2.3.1 k阶常系数线性齐次递归方程二阶常系数线性微分方程的一般形式是 y+py+qy=f(x) （1） 其中p，q是常数；f(x)是x的已知函数.如果f(x)=0,则方程（1）变为 y+py+qy=0 f(x)=0, （2）称（2）为二阶常系数齐次线性微分方程如果f(x)0，则称方程（1）为二阶常系数非齐次线性微分方程.一、k阶常系数线性齐次递归方程1、递归方程的形式：（2.3.1）2、递归方程的特征方程取代：两边分别除以，可得：把上式写成：（2.3.2）则式（2.3.2）称为递归方程（2.3.1）的特征方程。二、k阶常系数线性齐次递归方程的求解1、是特征方程的个互不相同的根。则递归方程（2.3.1）的通解为：（2.3.3）2、特征方程的个根中有个重根，递归方程（2.3.1）的通解形式为：（2.3.4）在（2.3.3）及（2.3.4）中，为待定系数。3、求解过程：把递归方程的初始条件代入（2.3.3）或（2.3.4）中，建立联立方程，确定系数，从而可求出通解。例2.3 三阶常系数线性齐次递归方程如下：解 特征方程为：把方程改写成：对特征方程进行因式分解，得：则有特征根：所以，递归方程的通解为：由初始条件得：解此联立方程，得：则递归方程的解为：例2.4 三阶常系数线性齐次递归方程如下：解： 特征方程为：把特征方程改写成：进行因式分解：最后得：求得特征方程的根为：所以，递归方程的通解为：代入初始条件：解此联立方程，得：则递归方程的解为：2.3.2 k阶常系数线性非齐次递归方程一、k阶常系数线性非齐次递归方程1、递归方程的形式：（2.3.5）2、通解形式：其中，是对应齐次递归方程的通解，是原非齐次递归方程的特解。3、特解的求取1）是的次多项式，即（2.3.6）其中，是常数。特解也是的次多项式：（2.3.7）其中，为待定系数。2）是如下形式的指数函数：（2.3.8）其中，、为常数。a) 不是特征方程的重根，特解为：（2.3.9）其中，为待定系数。b) 是特征方程的重特征根，特解的形式为：（2.3.10）其中，是待定系数。例2.5 二阶常系数线性非齐次递归方程如下：解 对应的齐次递归方程的特征方程为：把此方程转换为：得到特征根为：所以，对应的齐次递归方程的通解为：令非齐次递归方程的特解为：代入原递归方程，得：化简后得到：由此，得到联立方程：解此联立方程，可得：所以，非齐次递归方程的通解为：把初始条件代入，有：解此联立方程，得：最后，非齐次递归方程的通解为：例2.6 二阶常系数线性非齐次递归方程如下：解 对应齐次递归方程的特征方程为：此方程可改写成：所以，方程的解为：齐次递归方程的通解为：令非齐次递归方程的特解为：把特解代入原非齐次递归方程，得：整理得：可得联立方程：解此联立方程得：所以，非齐次递归方程的通解为：用初始条件代入：解此联立方程得：最后，非齐次递归方程的解为：2.4 用递推方法求解递归方程2.4.1 递推非齐次递归方程：（2.4.1）其中，、是常数，是的某一个函数。直接把公式应用于式中的，得到： （2.4.2）例2.7 汉诺塔问题。由（2.2.1），汉诺塔的递归方程为：直接利用（2.4.2）式于汉诺塔的递归方程。此时，从递推到1，有：2.4.2 用递推法求解变系数递归方程一、变系数齐次递归方程：（2.4.3）利用递推方法，容易得到：（2.4.4）例2.8 解如下递归函数：由（2.4.4）式，容易得到：二、变系数非齐次递归方程：（2.4.5）其中，是常数，和是的函数。利用（2.4.5）式对进行递推，有： （2.4.6）例2.9 解如下的递归函数：对方程进行递推，有： 如果直接使用公式（2.4.6），此时，有：得到同样结果。例2.10 解如下