最大子段和问题算法实验报告_昆明理工大学.doc

《最大子段和问题算法实验报告_昆明理工大学.doc》由会员分享，可在线阅读，更多相关《最大子段和问题算法实验报告_昆明理工大学.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、昆明理工大学信息工程与自动化学院学生实验报告（ 2012 2013 学年 第 1 学期 ）课程名称：算法分析与设计 开课实验室：信自444 2012 年12月 20 日年级、专业、班计科101班学号姓名成绩实验项目名称最大子段和问题指导教师 吴霖教师评语该同学是否了解实验原理：A.了解B.基本了解C.不了解该同学的实验能力：A.强 B.中等 C.差 该同学的实验是否达到要求：A.达到B.基本达到C.未达到实验报告是否规范：A.规范B.基本规范C.不规范实验过程是否详细记录：A.详细B.一般 C.没有 教师签名： 年 月 日一、上机目的及内容1.上机内容给定有n个整数（可能有负整数）组成的序列（

2、a1,a2,an），求改序列形如的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。2.上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）分别用穷举法、分治法和动态规划法设计最大子段和问题的算法；（2）对所设计的算法采用大O符号进行时间复杂性分析；蛮力法：T(n)=O(n2)分治法：T(n)=O(nlog(n)动态规划法：T(n)=O(n)。（3）上机实现算法，

3、并用计数法和计时法分别测算算法的运行时间；（4）通过分析对比，得出自己的结论。三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUAL C+6.0软件四、实验方法、步骤（或：程序代码或操作过程）一、蛮力法#includeint MaxSum(int a,int n,int &besti,int &bestj) int sum=0; int i,j,k; for(i=1;i=n;i+) int asum=0; for(j=i;jsum) sum=asum; besti=i; bestj=j; return sum;void main() int n,a100,m,i,j,ma

4、xsum; cout输入元素个数n:n; cout输入各元素的值(一共n个):endl; for(m=1;mam; maxsum=MaxSum(a,n,i,j); cout最大子段和是：maxsumendl;二、 分治法#includeint MaxSum(int a,int left,int right) int sum=0; if (left=right) if (aleft0) sum=aleft; else sum=0; else int center=(left+right)/2; int leftsum=MaxSum(a,left,center); int rightsum=Max

5、Sum(a,center+1,right); int s1=0; int lefts=0; for(int i=center;i=left;i-) lefts+=ai; if(leftss1) s1=lefts; int s2=0; int rights=0; for(int j=center+1;js2) s2=rights; sum=s1+s2; if(sumleftsum)sum=leftsum; if(sumrightsum)sum=rightsum; return sum;void main() int n,a100,m,maxsum;cout分治法求解endl; cout请输入待求

6、的元素数目n; cout请输入各元素endl; for(m=1;mam; maxsum=MaxSum(a,1,n); cout当前序列最大子段和为：maxsumendl;三、 动态规划法#includevoid MaxSum(int n,int a) int sum=0; int b=0; for(int i=1;i0)b+=ai; else b=ai; if(bsum)sum=b; cout最大子段和是：sumendl; void main() int n,a100,m,maxsum;cout动态规划法求解endl; cout请输入待求的元素数目n; cout请输入各元素endl; for(

7、m=1;mam;MaxSum(n,a);五、实验过程原始记录( 测试数据、图表、计算等)请给出各个操作步骤的截图和说明；六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）蛮力法，分治法，动态规划法的求解问题效率不同。动态规划法效率最高，算法最优，和其他两者相比理解起来不那么容易，只有人把问题想得透彻，设计出复杂度更低的算法，机器的求解速度才能更快，最终获益的是我们自己。所以程序员不应只会用前人设计好得算法编写代码，也应发挥主管能动性，优化算法，设计出适合当前需求的优良算法。注：教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。