- 1、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。。
- 2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 4、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 5、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 6、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 7、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
而相应齐次递推关系的通解为 ,由定理6.3.1知,非齐次递推关系的通解为 由初值 得 从而 故 例6.3.2 求解递推关系 解 由于2是特征方程的二重根,所以该递推关系的特解为 将它代入递推关系,并比较等号两边n的系数及常数项,得到 而相应齐次递推关系的通解为 从而非齐次递推关系的通解为 再由初值 求得 于是 根据前面的分析,可知该递推关系的通解为 解 相应的特征方程为x=2,故齐次解为2n。 设非齐次特解为b,代入原递推关系,得 例6.3.3 求Hanoi塔问题满足的递推关系 所以特解为 代入初值 得 所以 对于有些非线性递推关系,我们可以通 过变换化为常系数线性递推关系。 例6.3.6. 迭代法 给定n个实数a1,a2,…,an,可以用多少种不同的方法来构成它们的乘积?(与顺序有关) 例如 (a1*a2)*a3, a1*(a2*a3) H(1)=1; H(n)=(4(n-2)+2) H(n-1)=……. =(n-1)!C(2n-2,n-1) D(n)=(n-1)【D(n-1)+D(n-2)】 D(n)-nD(n-1)=-D(n-1)+ (n-1) D(n-2) =-( D(n-1)- (n-1) D(n-2)) =(-1)n-2 利用生成函数求解各类递推关系有广泛的适用性,其基本步骤是: (1)令 §6.4 用生成函数求解递推关系 (2)将关于 的递推关系式转化成关于 的方程式; ,将 展开成x的幂级数, 的系数即是 。 (3)解出 例6.4.1 求解递推关系 解: 令 则有 将 代入上式并整理,得 所以 求解h(n)=5h(n-1)-6h(n-2),h0=1,h1=-2 令g(x)=h0+h1x+ h2x2 …+hnxn+… -5xg(x)= -5h0x-5h1x2-…-5hn-1xn+… 6x2g(x)= 6h0x2+…+6hn-2xn+… (1-5x+6x2)g(x)=h0+(h1-5h0)x+(h2-5h1+6h0)x2+ g(x)=(1-7x)/ (1-5x+6x2) h(n)=5*2n-4*3n 其中 是给定常系数,那么, 定理6.4.1 具有初值条件的的k阶常系数线性递归关系为: 有生成函数 其中, 是不大于k-1次的多项式。当且仅当 关于递归关系的特征方程为 例6.4.2 已知序列 。 求 解法1 由定理6.4.1 的生成函数为 用 替代 ,知特征方程为 特征根为 故 利用整式除法 知 解得 从而 例6.4.3 求如下递归关系的生成函数: 解: 特征方程为 对 , , ,求得 例6.4.5 求解Hanoi塔问题 解 设 ,对等式 两边对应乘以 ,n≥2 并将等式组成左右两边相加。 左端为: 右端为: 从而 例6.4.6 求解递推关系: 解:先求它的生成函数: 所以 第六章、递推关系 主要内容 §6.1 递推关系的建立 §6.2 常系数线性齐次递推关系的求解 §6.3 常系数线性非齐次递推关系的求解 §6.4 用生成函数求解递推关系 §6.5 用迭代归纳法求解递推关系及其应用 构建求解递推关系是组合计数的重要方法; 在第四章讨论错位排列数Dn时,建立了关于 Dn的递推关系: Dn=(n-1)(Dn-1 + Dn-2) n≥3 D1=0,D2=1 并由此推出以下的递推关系: Dn=nDn-1 + (-1)n n≥2 D1=0 § 6.1 递推关系的建立 定义6.1.1 给定一个数的序列H(0),H(1),…, H(n),…若存在正整数n0,使得当n≥n0时,可以用等号(或小于,大于号)把H(n)和前面某些项H(i),0≤ i n,联系起来,这样的式子叫做递推关系。 递推关系也称递归关系,递归方程。从本质上讲,递推关系是研究整变量函数的或者说是研究数列的,与此对应的是连续论域中的微分方程。因此,我们可以类似的方法对它们进行研究。 利用递推关系和初值在某些情况下可以求出序列的通项表示式H(n),正如
您可能关注的文档
最近下载
- ZXR10 M6000电信级路由器硬件手册.docx VIP
- 《输液导管相关静脉血栓形成防治中国专家共识》解读PPT课件.pptx VIP
- 高中英语_Being funny without saying a word教学课件设计.ppt
- 2024版育婴师培训全套课件完整版.docx VIP
- 子网掩码相关教学 子网掩码快速算法.doc VIP
- 什么什么踏地四字成语.docx VIP
- 力士乐卷扬减速机制动器安装拆解图文.pdf VIP
- 新能源汽车充电系统检修:车载充电机的认知与检修PPT教学课件.pptx
- 2025年度食品安全风险日管控、周排查、月调度记录表.pdf VIP
- (新版)消防设施操作员(初级)消防设施操作-考试题库(含答案).docx VIP
文档评论(0)