算法分析最大字段和算法分析实验报告

《算法分析最大字段和算法分析实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一、实验目的：(1)能够熟悉最大字段和问题这个算法(2)分别使用三种不同算法：暴力算法、分治算法、动态规划算法，体会其算法思想并比较时间复杂度。二、实验内容给定由n个整数（可能为负整数）组成的序列a1、a2、……an，求该序列形如ak的字段和的最大值。当所有整数均为负整数时定义其最大字段和为0。依次定义，所求的最优值为max{0，}。三、实验环境Window7、四、实验步骤与结果（1）暴力算法：这是改进后的算法，使用两个for循环，该算法时间复杂性为O（）。实验结果分析：（1）输入的数全是负整数

2、时：（2）输入的数是n个整数的序列时（以n=20为例）：（2）分治算法：针对最大字段和本身的结构，如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n],分别求出这两段的最大字段和，则a[1:n]的最大字段和有以下3种情况：（1）a[1:n]的最大字段和与a[1:n/2]的最大字段和相同；（2）a[1:n]的最大字段和与a[n/2+1:n]的最大字段和相同；（3）a[1:n]的最大字段和为，且1<=i<=n/2,n/2+1<=j<=n。该算法的时间复杂性为O(nlo

3、gn)。实验结果分析：（1）输入的数全是负整数时：（2）输入的数是n个整数的序列时（以n=20为例）：（3）动态规划算法：在对上述分治算法的分析中注意到，若记b[j]={},1<=j<=n,则所求的最大字段和为={}=b[j]由b[j]的定义易知，当b[j-1]>0时，b[j]=b[j-1]+a[j],否则b[j]=a[j]。由此可得计算b[j]的动态规划递归式b[j]=max{b[j-1]+a[j],a[j]},1<=j<=n该算法的时间复杂性为O(n)。（1）输入的数全是负整数时：（2）输入

4、的数是n个整数的序列时（以n=20为例）：五、心得体会从本次实验中，我对暴力算法、分治算法和动态规划算法有了进一步的认识，从代码的一步步完成，更加深刻体会到了理论与实践的结合是多么不容易了。虽然整个算法思想看起来简单，可是真正动手实践，才发现了很多问题，实验结果与预期发生很大偏差，后来经过仔细研究，终于一一纠正了错误。“纸上得来终觉浅，绝知此事要躬行”，动手写的每一行代码，才能有获得正确结果的激动，才有了对知识的深度掌握。从这次实验中，通过分析三种算法的时间复杂度，对其各自的适用范围以及优化思想

5、有了很深的认识。六、实验源代码：1暴力算法#includemain(){inta[100],i,n,besti,bestj;printf("请输入您将要输入的整数的个数");scanf("%d",&n);printf("请输入整数，以空格隔开");for(intg=0;g

6、k++)thissum+=a[k];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}}printf("用暴力算法求出的最大字段和为%d",sum);}2分治算法#includeintmaxSubSum(inta[],intleft,intright){intsum=0;if(left==right)sum=a[left]>0?a[left]:0;else{intcenter=(left+right)/2;intleftsum=ma

7、xSubSum(a,left,center);intrightsum=maxSubSum(a,center+1,right);ints1=0;intlefts=0;for(inti=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}ints2=0;intrights=0;for(intc=center+1;c<=rights;c++){rights+=a[c];if(right>s2)s2=rights;}sum=s1+s2;if(sum

8、