《算法分析最大字段和算法分析实验报告》由会员分享，可在线阅读，更多相关《算法分析最大字段和算法分析实验报告（6页珍藏版）》请在金锄头文库上搜索。
1、一、 实验目的：(1)能够熟悉最大字段和问题这个算法(2)分别使用三种不同算法：暴力算法、分治算法、动态规划算法，体会其算法思想并比较时间复杂度。二、 实验内容 给定由n个整数（可能为负整数）组成的序列a1、a2、an，求该序列形如ak的字段和的最大值。当所有整数均为负整数时定义其最大字段和为0。依次定义，所求的最优值为max0，。三、实验环境Window7、四、实验步骤与结果 （1）暴力算法：这是改进后的算法，使用两个for循环，该算法时间复杂性为O（）。 实验结果分析：（1）输入的数全是负整数时：（2）输入的数是n个整数的序列时（以n=20为例）：（2）分治算法：针对最大字段和本身的结构，
2、如果将所给的序列a1:n分为长度相等的两段a1:n/2和an/2+1:n,分别求出这两段的最大字段和，则a1:n的最大字段和有以下3种情况：（1）a1:n的最大字段和与a1:n/2的最大字段和相同；（2）a1:n的最大字段和与an/2+1:n的最大字段和相同；（3）a1:n的最大字段和为，且1=i=n/2,n/2+1=j=n。该算法的时间复杂性为 O(nlogn)。 实验结果分析：（1）输入的数全是负整数时：（2）输入的数是n个整数的序列时（以n=20为例）：（3）动态规划算法：在对上述分治算法的分析中注意到，若记bj= ,1=j0时，bj= bj-1+aj,否则bj=aj。由此可得计算bj的
3、动态规划递归式bj=maxbj-1+aj,aj,1=j=n该算法的时间复杂性为 O(n)。（1）输入的数全是负整数时：（2）输入的数是n个整数的序列时（以n=20为例）：五、心得体会 从本次实验中，我对暴力算法、分治算法和动态规划算法有了进一步的认识，从代码的一步步完成，更加深刻体会到了理论与实践的结合是多么不容易了。虽然整个算法思想看起来简单，可是真正动手实践，才发现了很多问题，实验结果与预期发生很大偏差，后来经过仔细研究，终于一一纠正了错误。“纸上得来终觉浅，绝知此事要躬行”，动手写的每一行代码，才能有获得正确结果的激动，才有了对知识的深度掌握。从这次实验中，通过分析三种算法的时间复杂度，
4、对其各自的适用范围以及优化思想有了很深的认识。六、实验源代码：1暴力算法#include main()int a100,i,n,besti,bestj;printf(请输入您将要输入的整数的个数n);scanf(%d,&n);printf(请输入整数，以空格隔开n);for(int g=0;gn;g+)scanf(%d,&ag);int sum=0;for(i=0;in;i+)for(int j=i;j=n;j+)int thissum=0;for(int k=i;ksum)sum=thissum;besti=i;bestj=j;printf(用暴力算法求出的最大字段和为%dn,sum);2
5、分治算法#includeint maxSubSum(int a,int left,int right)int sum=0;if(left=right)sum=aleft0?aleft:0;elseint center =(left+right)/2;int leftsum=maxSubSum(a,left,center);int rightsum=maxSubSum(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 right
6、s=0;for(int c=center+1;cs2)s2=rights;sum=s1+s2;if(sumleftsum)sum=leftsum;if(sumrightsum)sum=rightsum;return sum;printf(用分治算法求出的最大字段和为%dn,&sum);void main()int a100,i,n,besti,bestj;printf(请输入您将要输入的整数的个数n);scanf(%d,&n);printf(请输入整数，以空格隔开n);for(int g=0;gn;g+)scanf(%d,&ag);3 动态规划#include void main()int a100,i,n,besti,bestj;printf(请输入您将要输入的整数的个数n);scanf(%d,&n);printf(请输入整数，以空格隔开n);for(int g=0;gn;g+)scanf(%d,&ag);int sum=0,b=0;for(i=0;i0)b+=ai;else b=ai;if(bsum) sum=b;printf(用动态规划算法求出的最大字段和为%dn,sum);
