最大子段和问题

最大子段和问题1.实验题目给定有n个整数（可能有负整数）组成的序列（a1,a2,…,an），求该序列从第i个数字到第j个数字的和（i=1，2，…,n;j=1，2，…,n）的最大值，当所有整数均为负整数时，其最大字段和为0.2.实验目的（1）深刻掌握动态规划法的设计思想并能熟练运用；（2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。3．实验要求（1）分别用蛮力法、分治法和动态规划法设计最大字段和问题的算法；（2）比较不同算法的时间性能；（3）给出测试数据，写出程序文档。4.程序实现（1...

1.实验题目给定有n个整数（可能有负整数）组成的序列（a1,a2,…,an），求该序列从第i个数字到第j个数字的和（i=1，2，…,n;j=1，2，…,n）的最大值，当所有整数均为负整数时，其最大字段和为0.2.实验目的（1）深刻掌握动态规划法的设计思想并能熟练运用；（2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。3．实验要求（1）分别用蛮力法、分治法和动态规划法设计最大字段和问题的算法；（2）比较不同算法的时间性能；（3）给出测试数据，写出程序文档。4.程序实现（1）蛮力法源程序如下：#include#defineN6voidML(inta[],ints[][N]){inti,j;for(i=0;ik){k=s[i][j];b=i1;c=j1;}if(k<0)k=0;printf("最大字段和为:%d,从数组的第%d个数开始,到第%d个数结束\n",k,b,c);}（2）分治法源程序如下：#include#defineN6intMaxSum(inta[],intleft,intright){intsum=0;intleftsum,rightsum,center;if(left==right){if(a[left]>0)sum=a[left];elsesum=0;}else{center=(leftright)/2;leftsum=MaxSum(a,left,center);rightsum=MaxSum(a,center1,right);ints1=0,lefts=0,i;for(i=center;i>=left;i--){lefts=a[i];if(lefts>s1)s1=lefts;}ints2=0,rights=0,j;for(j=center1;j<=right;j){rights=a[j];if(rights>s2)s2=rights;}sum=s1s2;if(sumintmax_sum(inta[],intn,int*best_i,int*best_j){inti,j;intthis_sum[100];intsum[100]; intmax=0;this_sum[0]=0;sum[0]=0;*best_i=0;*best_j=0;i=1;for(j=1;j<=n;j){if(this_sum[j-1]>=0)this_sum[j]=this_sum[j-1]a[j];else{this_sum[j]=a[j];i=j;}if(this_sum[j]<=sum[j-1])sum[j]=sum[j-1];else{sum[j]=this_sum[j];*best_i=i;*best_j=j;max=sum[j];}}returnmax;}voidmain(){ inti,j,n,a[100],t;printf("Inputnumberofdata(<99):\n");scanf("%d",&n);printf("inputthedata:\n");for(i=1;i<=n;i)scanf("%d",&a[i]);i=j=1;t=max_sum(a,n,&i,&j);printf("Themostsumofsectionis%d\n",t);printf("startingpointis%d\n",i);printf("endpointis%d\n",j);}5实验总结（1）出现的问题：在蛮力法中，调用函数ML(inta[],ints[][N])的声明刚开始写成下列形式voidML(inta[],ints[][])，编译通不过，这是因为多维数组名作为参数时，必须指明最高维的大小。（2）蛮力法的设计思路是用一个二维数组将从i到j的和都记录下来，再比较各元素的大小，时间复杂性为O（n2）,故效率低。分治法的设计思想是不断将问题为子问题，然后用递归算法求解子问题，最后对解进行合并。时间复杂性为O（n㏒2n），可见较蛮力法性能较好。动态规划法的设计思想是将问题划分为若干个子问题，但这些子问题不一定独立，用一个表格把每个子问题的解保存起来，当用到该子问题的解时查表即可，从而避免了大量的重复计算。所以从时间性能上看也比蛮力法好。

                    本文档为【最大子段和问题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

最大子段和问题

你可能还喜欢