全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
上机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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- (完整版)2026年节后复工安全教育培训试题及答案
- (2025)员额法官遴选面试试题(附答案)
- 《建设工程法规及相关知识》测试题(附答案)
- 《3-6岁儿童学习与发展指南》测试卷及答案
- “依法治校”普法试题(含答案)
- 2024年大学生安全知识竞赛试题库和答案
- 19期间核查的实施习题与参考答案
- (2025年)危重孕产妇救治试题及答案
- 《饲料质量安全管理规范》考核试题及答案
- (2025)保密教育测试题库完整参考答案
- 2026年注册安全工程师考试金属非金属矿山安全生产实务(初级)试题与参考答案
- 2027年高考地理复习:综合题 答题方向+答题模版汇编
- 2026年监理工程师继续教育人防工程监理测试题含答案
- 2025年控告申诉检察业务竞赛真题及答案解析
- 2026年慢性病防控岗位考试题库及答案
- 化工运行制冷过程工程分析培训课件
- GB/T 2423.68-2026环境试验第2部分:试验方法试验:覆冰融冰循环试验
- 数据资产价值评估指南及实践案例集
- 2025年ISO体外诊断试剂使用规范检测答案及解析
- 精神科护理实践中的人文关怀
- 苏州市住宅工程建安成本参考指标(2021年)
评论
0/150
提交评论