《母函数与递推关系》PPT课件

《《母函数与递推关系》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ProjectI全排列生成算法的研究和实现5分选作C/C++orJava11月20日前网络学堂提交目标ResearchandNovelty（非命题作文，以下内容任选）在实现和研究4种全排列生成算法基础上进行创新算法效率和复杂度分析新的算法任何相关内容的创新点3-6页评分标准Paper(80%)代码以及可执行文件(20%)选题分析完善2内容回顾组合的生成和组合意义模型转换一一对应定义：对于序列a0,a1,a2…,构造一函数：G(x)=a0+a1x+a2x2+……,称函数G(x)是序列a0,a1,a2…,的母函数(生成函数ge

2、neratingfunction)。(1+x)n是序列C(n,0),C(n,1),…C(n,n)的母函数g(x)=1+x+x2+x3+x4+...=1/(1-x)是f(n)=1的母函数设级数收敛，-1

3、子可用。设计算法;估计它的复杂性，即估计工作量.5§2.2递推关系算法：N=2时第一步先把最上面的一个圆盘套在B上第二步把下面的一个圆盘移到C上最后把B上的圆盘移到C上到此转移完毕ABC6§2.2递推关系假定n-1个盘子的转移算法已经确定。对于一般n个圆盘的问题,先把上面的n-1个圆盘经过C转移到B;第二步把A下面一个圆盘移到C上最后再把B上的n-1个圆盘经过A转移到C上n=2时，算法是对的，因此，n=3是算法是对的。以此类推。ABC7§2.2递推关系令h(n)表示n个圆盘所需要的转移盘次。对于一般n个圆盘的问题,先把上面

4、的n-1个圆盘经过C转移到B:h(n-1)次第二步把A下面一个圆盘移到C上:1次最后再把B上的n-1个圆盘经过A转移到C上：h(n-1)次算法复杂度为：构造母函数为：求得了母函数，对应的序列也就求得h(n)ABC8§2.2递推关系所谓形式算法说的是假定这些幂级数在作四则运算时，一如有限项的代数式一样。9如何从母函数得到序列？化为部分分数的算法。由上式可得：g(x)=1+x+x2+x3+x4+...=即：10§2.2递推关系或利用递推关系(2-2-1)有上式左端为：右端第一项为：右端第二项为：11§2.2递推关系例2.求n位

5、十进制数中出现偶数个5的数的个数。先从分析n位十进制数出现偶数个5的数的结构入手设p1p2…pn-1是n-1位十进制数，若含有偶数个5，则pn取5以外的0，1，2，3，4，6，7，8，9九个数中的一个，若p1p2…pn-1只有奇数个5，则pn取5，使p1p2…pn-1pn成为出现偶数个5的十进制数。解法1：令an为n位十进制数中出现偶数个5的数的个数，bn为n位十进制数中出现奇数个5的数的个数。设序列{an}的母函数为A(x)，序列{bn}的母函数为B(x)。12a1=8,b1=113§2.2递推关系故得关于母函数A(x)

6、和B(x)得连立方程组：14§2.2递推关系解法二：n-1位的十进制数的全体共9×10n-1个(最高位不为0)，设所求数为an,设A(x)=a1x+a2x2+…,按照尾数是否为5分类：尾数不是为5的：9an-1尾数为5的，前n-1位有奇数个5：15§2.2递推关系验证：a1=8,a2=73161）不出现某特定元素设为a1，其组合数为，相当于排除a1后从a2,….an中取r个做允许重复的组合。§2.2递推关系例三：从n个元素a1,a2,….an中取r个进行允许重复的组合。假定允许重复的组合数用表示，其结果可能有以下两种情况。

7、2）至少出现一个a1，取组合数为相当于从a1,a2,….an中取r-1个做允许重复的组合，然后再加上一个a1得从n个元素中取r个允许重复的组合。17§2.2递推关系因，故令系数(1-x)不是常数。但18由二项式定理可得母函数递推关系递推运算初始值代数运算：化为部分分数的算法§2.3母函数的性质一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。为了求满足某种递推关系的序列，可把它转换为求对应的母函数G(x)，G(x)可能满足一代数方程，或代数方程组，甚至于是微分方程。最后求逆变换，即从已

8、求得的母函数G(x)得到序列{an}。关键在于要搭起从序列到母函数，从母函数到序列这两座桥。21§2.3母函数的性质对应的母函数分别为、不特别说明,下面假设、两个序列22性质1：若则例.已知则23例.已知则mmm-1性质2：则若证：例.24性质3：证：若则)::::12102102210100LLLL