蛮力法、分治法和动态规划法设计最大子段和问题的算法.doc_第1页
蛮力法、分治法和动态规划法设计最大子段和问题的算法.doc_第2页
蛮力法、分治法和动态规划法设计最大子段和问题的算法.doc_第3页
蛮力法、分治法和动态规划法设计最大子段和问题的算法.doc_第4页
全文预览已结束

下载本文档

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

文档简介

算法设计与分析实验报告实验题目给定由n个整数组成的序列(a1, a2, , an)，求该序列形如 的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。实验目的（1）深刻掌握动态规划法的设计思想并能熟练运用；（2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。实验要求 （1）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法；（2）比较不同算法的时间性能；（3）给出测试数据，写出程序文档。 实验内容（包括代码和对应的执行结果截图）#includeint x,y,z;int ml(int d)/蛮力法int a=0,i,j,f; for(j=0;j5;j+)f=0; for(i=j;i5;i+) f=f+di; if(a0) sum=aleft; else sum=0; y+; else center=(left+right)/2; /划分 leftsum=MaxSum(a, left, center); /对应情况，递归求解 rightsum=MaxSum(a, center+1, right); /对应情况，递归求解 s1=0; lefts=0; /以下对应情况，先求解s1 for (i=center; i=left; i-) lefts+=ai; if (leftss1) s1=lefts;y+; s2=0; rights=0; /再求解s2 for (j=center+1; js2) s2=rights;y+; sum=s1+s2; /计算情况的最大子段和 if (sumleftsum) sum=leftsum; /合并，在sum、leftsum和rightsum中取较大者 if (sumrightsum) sum=rightsum;y+; return sum;int max(int a,int n) int sum=0,b=0; for(int i=0;i0) b+=ai; else b=ai; if(bsum) sum=b; z+; return sum;void main()int c;int s5=1,9,-5,7,-1; c=ml(s); cout蛮力法计算最大子段和为：cendl; cout蛮力法时间性为：xendl;c=MaxSum(s, 0, 4); cout分治法计算最大子段和为：cendl; cout分治法时间性为：yendl;c=max(s, 4); cout动态规划法计算最大子段和为：cendl; cout动态规划法时间性为：zendl;程序运行结果：实验结果分析
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

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

最新文档

评论

0/150

提交评论