离散完整课件103.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《离散完整课件103.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散 完整 课件 103
- 资源描述:
-
1、110.3 递推方程的求解与应用递推方程的求解与应用nHanoi 塔问题塔问题n递推方程的定义递推方程的定义n二分归并排序算法的分析二分归并排序算法的分析n快速排序算法的分析快速排序算法的分析n递归树递归树n分治算法分析的一般公式分治算法分析的一般公式2HanoiHanoi塔问题塔问题Hanoi塔问题:塔问题:从从A柱将这些圆盘移到柱将这些圆盘移到C柱上去柱上去.如果把一个圆盘从如果把一个圆盘从一个柱子移到另一个柱子称作一个柱子移到另一个柱子称作 1 次移动,在移动和放置次移动,在移动和放置时允许使用时允许使用B柱,但不允许大圆盘放到小圆盘的上面柱,但不允许大圆盘放到小圆盘的上面.问问把所有的
2、圆盘的从把所有的圆盘的从A移到移到C总计需要多少次移动?总计需要多少次移动?3算法设计与分析算法设计与分析算法算法 Hanoi(A,C,n)/*把把n个盘子从个盘子从A移到移到C1.Hanoi(A,B,n-1)2.move(A,C)/*把把1个盘子从个盘子从A移到移到C3.Hanoi(B,C,n-1)移动移动n个盘子的总次数为个盘子的总次数为T(n),得到递推方程,得到递推方程 T(n)=2T(n 1)+1.T(1)=1.可以求得可以求得 T(n)=2n 11秒钟移动秒钟移动1次,次,64个盘子大约需要个盘子大约需要5000亿年亿年4(等比级数求和)(等比级数求和)代入初值代入初值的项替换的项
3、替换被含被含的项替换的项替换被含被含12)(12.22212.22)1(2.122)3(2)3()2(12 1)3(2212)2(2)2()1(1 1)2(2 21)1(2)(3213212322 nnnnnnnTnTnTnTnTnTnTnTnTnTnT5递推方程的定义递推方程的定义定义定义10.5 设序列设序列a0,a1,an,简记为简记为an,一一个把个把an与某些个与某些个ai(in)联系起来的等式叫做关)联系起来的等式叫做关于序列于序列an的的递推方程递推方程.实例:实例:Fibonacci数列:数列:fn=fn-1+fn-2,初值初值 f0=1,f1=1 阶乘数列阶乘数列an,an=
4、n!:an=nan-1,a1=1 求解方法:迭代法求解方法:迭代法 0)1(2),()(2)(11TnnOiTnnTni6二分归并排序算法二分归并排序算法算法算法Mergesort(A,s,t)/*排序数组排序数组As.t1.m(t-s)/22.AMergesort(A,s,m)/*排序前半数组排序前半数组3.BMergesort(A,s+1,t)/*排序后半数组排序后半数组4.Merge(A,B)/*将排好序的将排好序的A,B归并归并假设假设n=2k,比较次数至多为,比较次数至多为W(n)W(n)=2W(n/2)+n 1归并两个归并两个n/2大小数组的比较次数为大小数组的比较次数为n 17实
5、例实例 输入输入:5,1,7,8,2,4,6,3 划分:划分:5,1,7,8,2,4,6,3 递归排序前半个数组递归排序前半个数组:5,1,7,8 1,5,7,8 递归排序后半个数组递归排序后半个数组:2,4,6,3 2,3,4,6 归并归并:1,5,7,8 和和 2,3,4,6 输出:输出:1,2,3,4,5,6,7,8 归并过程归并过程157823468求解递推方程求解递推方程1log122)12.22(2(1)2.122222)2(2122212)2(221222)2(21212)2(2 2 12 )2 (2 )(2123323222121 nnnkkWWWWWWnWkkkkkkkkkk
6、kkkkkkkkkkkk9归纳法验证解归纳法验证解nn=1代入上述公式得代入上述公式得 W(1)=1 log1 1+1=0,符合初始条件符合初始条件.n假设对于任何小于假设对于任何小于n的正整数的正整数t,W(t)都是正确的,都是正确的,将结果代入原递推方程的右边得将结果代入原递推方程的右边得 2W(n/2)+n 1 =2(2k 1 log2k 1 2k 1+1)+2k 1 =2k(k 1)2k+2+2k 1=k2k 2k+1 =nlogn n+1=W(n)10快速排序算法快速排序算法算法算法 Q Quicksort(A,p,r)/*排序数组排序数组Ap.r输入:输入:数组数组Ap.r输出:排
展开阅读全文