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

1、5 / 6文档可自由编辑打印一、 实验目的：(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<

3、=j<=n,则所求的最大字段和为=bj由bj的定义易知，当bj-1>0时，bj= bj-1+aj,否则bj=aj。由此可得计算bj的动态规划递归式bj=maxbj-1+aj,aj,1<=j<=n该算法的时间复杂性为 O(n)。（1）输入的数全是负整数时：（2）输入的数是n个整数的序列时（以n=20为例）：五、心得体会 从本次实验中，我对暴力算法、分治算法和动态规划算法有了进一步的认识，从代码的一步步完成，更加深刻体会到了理论与实践的结合是多么不容易了。虽然整个算法思想看起来简单，可是真正动手实践，才发现了很多问题，实验结果与预期发生很大偏差，后来经过仔细研究，终于一一纠

4、正了错误。“纸上得来终觉浅，绝知此事要躬行”，动手写的每一行代码，才能有获得正确结果的激动，才有了对知识的深度掌握。从这次实验中，通过分析三种算法的时间复杂度，对其各自的适用范围以及优化思想有了很深的认识。六、实验源代码：1暴力算法#include <stdio.h> main()int a100,i,n,besti,bestj;printf("请输入您将要输入的整数的个数n");scanf("%d",&n);printf("请输入整数，以空格隔开n");for(int g=0;g<n;g+)scanf(&q

5、uot;%d",&ag);int sum=0;for(i=0;i<n;i+)for(int j=i;j<=n;j+)int thissum=0;for(int k=i;k<=j;k+) thissum+=ak;if(thissum>sum)sum=thissum;besti=i;bestj=j;printf("用暴力算法求出的最大字段和为%dn",sum);2 分治算法#include<stdio.h>int maxSubSum(int a,int left,int right)int sum=0;if(left=rig

6、ht)sum=aleft>0?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(lefts>s1) s1=lefts;int s2=0;int rights=0;for(int c=center+1;c<=rights;c+)rights+=ac;if(right&g

7、t;s2)s2=rights;sum=s1+s2;if(sum<leftsum)sum=leftsum;if(sum<rightsum)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;g<n;g+)scanf("%d",&ag);3 动态规划#include <stdio.h> void main()int a100,i,n,besti,bestj;printf("请输入您将要输入的整数的个数n");scanf("%d",&n);printf("请输入整数，以空格隔开n");for(int g=0;g<n;g+)scanf("%d",&ag