欢迎来到天天文库
浏览记录
ID:22440242
大小:250.50 KB
页数:16页
时间:2018-10-20
《算法设计与分析-求解递归方程》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、递推方程求解递推方程定义给定数列f(0),f(1),…,f(n),一个把f(n)和某些f(i),0i2、n)+H(n-1)-3H(n-2)-5H(n-3)-2H(n-4)=0H(0)=1,H(1)=0,H(2)=1,H(3)=2特征方程x4+x3-3x2-5x-2=0,特征根-1,-1,-1,2,通解为解得解为常系数线性非齐次递推方程求解(公式法)标准形通解为对应的齐次通解加上特解特解的函数形式依赖于f(n)求解的关键是用待定系数法确定一个特解H*(n)f(n)为n的t次多项式,一般H*(n)也为n的t次多项式例8求an+5an-1+6an-2=3n2的通解设an*=P1n2+P2n+P3,代入得P1n2+P2n+P3+5[P1(n-1)2+P2(n-1)+P3]+6[P1(n-2)23、+P2(n-2)+P3]=3n2从而得到方程组12P1=3-34P1+12P2=029P1–17P2+12P3=0通解为例10Hanoi塔H(n)=2H(n-1)+1设H*(n)=PP=2P+1,P=-1H(n)=A2n–1代入初值H(1)=1得A=1解为H(n)=2n–1f(n)为指数函数n,特解也为指数形式若不是特征根,则特解为H*(n)=Pn若是e重特征根,则特解为Pnen例13H(n)+5H(n-1)+6H(n-2)=424n令H*(n)=P4n,代入得P4n+5P4n-1+6P4n-2=424n42P=4216,P=16通解为H(n)=C1(-2)n+C2(4、-3)n+4n+2H(n)–5H(n-1)+6H(n-2)=2n求特解2为1重根令H*(n)=Pn2n,代入得Pn2n–5P(n-1)2n-1+6P(n-2)2n-2=2n解得P=-2H*(n)=-n2n+12.转化成常系数线性递推方程求解---换元法例11令代入得bn=2bn-1+1,b0=4解得例12归并排序T(n)=2T(n/2)+n-1,n=2kT(2)=1H(k)=2H(k-1)+2k-1H(1)=1令H*(k)=P1k2k+P2,解得P1=P2=1,H*(k)=k2k+1通解H(k)=C2k+k2k+1,代入初值,得C=-1H(k)=-2k+k2k+1T(n)=nlogn5、–n+13.叠代归纳法例13H(n)=(4n-6)H(n-1)H(1)=1用归纳法验证4.差消法----化简递推方程例14求解递推方程相减并化简得由叠代得T(n)=O(nlogn)5.Master定理例20例21例22
2、n)+H(n-1)-3H(n-2)-5H(n-3)-2H(n-4)=0H(0)=1,H(1)=0,H(2)=1,H(3)=2特征方程x4+x3-3x2-5x-2=0,特征根-1,-1,-1,2,通解为解得解为常系数线性非齐次递推方程求解(公式法)标准形通解为对应的齐次通解加上特解特解的函数形式依赖于f(n)求解的关键是用待定系数法确定一个特解H*(n)f(n)为n的t次多项式,一般H*(n)也为n的t次多项式例8求an+5an-1+6an-2=3n2的通解设an*=P1n2+P2n+P3,代入得P1n2+P2n+P3+5[P1(n-1)2+P2(n-1)+P3]+6[P1(n-2)2
3、+P2(n-2)+P3]=3n2从而得到方程组12P1=3-34P1+12P2=029P1–17P2+12P3=0通解为例10Hanoi塔H(n)=2H(n-1)+1设H*(n)=PP=2P+1,P=-1H(n)=A2n–1代入初值H(1)=1得A=1解为H(n)=2n–1f(n)为指数函数n,特解也为指数形式若不是特征根,则特解为H*(n)=Pn若是e重特征根,则特解为Pnen例13H(n)+5H(n-1)+6H(n-2)=424n令H*(n)=P4n,代入得P4n+5P4n-1+6P4n-2=424n42P=4216,P=16通解为H(n)=C1(-2)n+C2(
4、-3)n+4n+2H(n)–5H(n-1)+6H(n-2)=2n求特解2为1重根令H*(n)=Pn2n,代入得Pn2n–5P(n-1)2n-1+6P(n-2)2n-2=2n解得P=-2H*(n)=-n2n+12.转化成常系数线性递推方程求解---换元法例11令代入得bn=2bn-1+1,b0=4解得例12归并排序T(n)=2T(n/2)+n-1,n=2kT(2)=1H(k)=2H(k-1)+2k-1H(1)=1令H*(k)=P1k2k+P2,解得P1=P2=1,H*(k)=k2k+1通解H(k)=C2k+k2k+1,代入初值,得C=-1H(k)=-2k+k2k+1T(n)=nlogn
5、–n+13.叠代归纳法例13H(n)=(4n-6)H(n-1)H(1)=1用归纳法验证4.差消法----化简递推方程例14求解递推方程相减并化简得由叠代得T(n)=O(nlogn)5.Master定理例20例21例22
此文档下载收益归作者所有