最大子段和问题.doc

《最大子段和问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、昆明理工大学信息工程与自动化学院学生实验报告（2012—2013学年第1学期）课程名称：算法分析与设计开课实验室：4452012年12月20日年级、专业、班计科101学号6姓名李力成绩实验项目名称最大子段和问题指导教师张晶教师评语该同学是否了解实验原理：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符号进行时间复杂性分析；（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；

3、（4）通过分析对比，得出自己的结论。三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUALC++6.0软件四、实验方法、步骤（或：程序代码或操作过程）1.分治法求解程序代码：//分治法求解最大子段和问题#include#defineM6intmain(){intmaxsum(inta[],intleft,intright);inta[M],left,right;printf("请输入%d个数:",M);//scanf("%d",&M);printf("");for(inti=0;i<=M-1;i++){scanf("%d

4、",&a[i]);}left=0;right=M-1;printf("最大子段和为：%d",maxsum(a,left,right));return0;}intmaxsum(inta[],intleft,intright){intsum,center,lefts,rights,s1,s2,leftsum,rightsum;sum=0;if(left==right){if(a[left]>0)sum=a[left];elsesum=0;}else{center=(left+right)/2;leftsum=maxsum(a,left,center);righ

5、tsum=maxsum(a,center+1,right);s1=0;lefts=0;for(inti=center;i>=left;i--){lefts=lefts+a[i];if(lefts>s1)s1=lefts;}s2=0;rights=0;for(intj=center+1;j<=right;j++){rights=rights+a[j];if(rights>s2)s2=rights;}sum=s1+s2;if(sum

6、}returnsum;}2.蛮力法求解程序代码：#include#defineM6//序列长度intmain(void){inti,a[M];intmaxSums(inta[]);printf("请输入%d个整数序列",M);for(i=0;i

7、temp=0;for(k=0;kmaxnum){maxnum=temp;}temp=0;}returnmaxnum;}3.动态规划法求解程序代码：#include#defineM6//数组的长度intdt(intarray[],intn);intmain(){inti,n=M;intarray[n];printf("请输入%d个数:",M);printf("");for(i=0;i

8、d",&a