首页 / 算法 / 算法第二章上机实践报告
算法第二章上机实践报告
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法第二章上机实践报告,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2719字,纯文字阅读大概需要4分钟。
内容图文
题目:
最大子列和问题
问题描述:
给定K个整数组成的序列{ N?1??, N?2??, ..., N?K?? },“连续子列”被定义为{ N?i??, N?i+1??, ..., N?j?? },其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 },其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序,计算给定整数序列的最大子列和。
本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下:
- 数据1:与样例等价,测试基本正确性;
- 数据2:102个随机整数;
- 数据3:103个随机整数;
- 数据4:104个随机整数;
- 数据5:105个随机整数;
输入格式:
输入第1行给出正整数K (≤100000);第2行给出K个整数,其间以空格分隔。
输出格式:
在一行中输出最大子列和。如果序列中所有整数皆为负数,则输出0。
输入样例:
6
-2 11 -4 13 -5 -2
输出样例:
20
算法描述:
本题采用分治法的思想,将原问题一分为二,分别求取左子列和右子列的最大子列和,另外,还有一种比较特殊的情况,就是可能所求的子列横跨中间元素,这种情况要单独拿出来讨论。
最后比较三者的值,返回其最大值。
算法时间及空间复杂度分析:
1 #include <iostream> 2 using namespace std; 3 4 void input(int a[],int num) 5 { 6 for(int i=0;i<num;i++) 7 cin >> a[i]; 8 } 9 10 int compare(int lmax,int rmax,int mmax) 11 { 12 int max=0; 13 if(lmax>=rmax && lmax>=mmax) max=lmax; 14 else if(rmax>=lmax && rmax>=mmax) max=rmax; 15 else max=mmax; 16 return max; 17 } 18 19 int maxsum(int a[], int left, int right) 20 { 21 //if(left>right) return 0; 22 if(left==right) 23 { 24 if(a[left]>0) return a[left]; 25 else return 0; 26 } 27 int mid=(left+right)/2; 28 int lmax=maxsum(a,left,mid); 29 int rmax=maxsum(a,mid+1,right); 30 int lmmax=0; 31 int lsum=0; 32 for(int i=mid;i>=left;i--) 33 { 34 lsum+=a[i]; 35 if(lsum>lmmax) lmmax=lsum; 36 } 37 int rmmax=0; 38 int rsum=0; 39 for(int i=mid+1;i<=right;i++) 40 { 41 rsum+=a[i]; 42 if(rsum>rmmax) rmmax=rsum; 43 } 44 45 int mmax=lmmax+rmmax; 46 return compare(lmax,rmax,mmax); 47 } 48 49 int main() 50 { 51 int num; 52 cin >> num; 53 int *a=new int[num+1]; 54 input(a,num); 55 cout << maxsum(a,0,num-1); 56 delete []a; 57 return 0; 58 }
时间复杂度:该算法的时间分为分治求左右子列和与跨越中间元素的子列的和。其中,分治的问题规模为原问题的一半,则时间复杂度为2T(n/2),后者从中间元素出发,分别扫描左右两边的数,故时间复杂度为O(n).根据主定理T(n)=2T(n/2)+O(n)=O(n log n)。
空间复杂度:该算法只用到了辅助变量,故空间复杂度为O(1)。
心得体会:
我觉得分治法的难点在于找到问题规模最小到能求解的情况,并且在写递归函数的时候很容易绕晕。通过本题的练习,更加清晰地理解了分治法的思想。另外,与同伴的结对编程小笼包有所提高。
内容总结
以上是互联网集市为您收集整理的算法第二章上机实践报告全部内容,希望文章能够帮你解决算法第二章上机实践报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。