贪心算法-最优合并问题.doc_第1页
贪心算法-最优合并问题.doc_第2页
贪心算法-最优合并问题.doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

上机04 实验名称一、 问题11、 问题描述一、最优合并问题给定k个有序序列s1 , s2,. , sk , 用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m + n -1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少，编程实现该算法并证明算法的正确性。2、 算法设计思想贪心算法3、 算法过程描述原问题S=S1，S2，S3，S4.Sn，（合并顺序）设最优解为Ck(最少合并次数)设Si,Sj为最短的两个序列反证法证明贪心选择性质：设有另一个最优解Ck1（没有使用贪心选择性质，即没有先合并Si,Sj）构造一课二叉合并树Si Sk为任意序列，Sksi,sjSjSkSSk SiSj由图可知，Ck-Ck1=(Sk+Sj-1)+(Si+Sj+si-1)-(Si+sj-1)+(Si+Sj+Sk-1)=Sk-Si0因此Ck1不是最优解，因此具有贪心选择性质最优子结构证明：S=S1，S2，S3，S4.Sn记Si和Sj的合并为（Si,Sj）-Si+jS=S-S1,S2Si+jCk=Ck+(Si+Sj-1)4、 算法实现及运行结果 #include#includeusing namespace std;/计算最优值int minSum(int *a,int m) int bm; int sum=0; for(int i=0;i1) sort(b,b+m); b0=b1+b0; sum+=b0-1; for(int i=1;im-1;i+) bi=bi+1; m-; return sum;int main () int n; printf(请输入序列个数:n); scanf(%d,&n); int an+1; printf(请输入各个序列长度:n); for(int i=0;in;i+) scanf(%d,&ai); printf(最少比较次数为：%dn,minSum(a,n);return 0;5、 算法复杂度分析及算法改进时间复杂度：排序：O(nlogn)，合并(n-1)(2*O(1)+O(
人人文库> 全部分类> 教育资料 > 中学教育

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论