算法分析习题参考答案第五章
1.最大子段和问题:给定整数序列 a1,a2, ,an,求该序列形如 ak的子段和
k i
j 的最大值: max 0,max ak 1 i j nk i j
1) 已知一个简单算法如下:
int Maxsum(int n,int a,int& best i,int& bestj){
int sum = 0;
for(int i=1;i<=n;i++){
int suma = 0;
for(int j=i;j<=n;j++){
suma + = a[j];
if(suma > sum){
sum = suma;
besti = i;
bestj = j;
}
}
}
return sum;
}试分析该算法的时间复杂性。
2) 试用分治算法解最大子段和问题,并分析算法的时间复杂性。
3) 试说明最大子段和问题具有最优子结构性质,并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。
(提示:令b(j) max1 i j n a,j 1,2, ,n) k
k ij
解:1)分析按照第一章,列出步数统计表,计算可得O(n) 2
2)分治算法:将所给的序列a[1:n]分为两段a [1:n/2]、a[n/2+1:n],分别求出这两段的最大子段和,则a[1:n]的最大子段和有三种可能:
①a[1:n]的最大子段和与a[1:n/2]的最大子段和相同;
②a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同;
③a[1:n]的最大子段和为两部分的字段和组成,即
j a
l ij ai a n a n aj;
2 2 1
算法分析习题参考答案第...1/2 相关文档推荐 算法分析与设计 第1章习... 3...5 , x2 = 2 2 则可设 n F (n) = c1 x1n + c 2 x 2 5 由 F...
第五章练习题参考答案及解析一.单项选择题 1. 【答案】B 【解析】向不特定...对要约条件进行分析,对股东是否接受要约提出建 议,并聘请独立财务顾问提出专业...
算法分析习题参考答案第八章算法分析习题参考答案第八章隐藏>> 1.二元可满足性...5. 独立集问题: 例:对于给定的无向图 G = (V , E ) 和正整数 k (≤...
数据结构与算法分析第五章课后题答案? ? ? ? 课后答案网,用心为你服务! ? ...最全最多的课后习题参考答案,尽在课后答案网(www.khdaw.com)! Khdaw团队一直...
第五章 习题参考答案 1.试编写一个绘制 Bezier .../*具体算法详见如下代码*/ for( i = 0; i < ...教育学第五章课后习题参... 2页 免费 电路分析课后...
数值最优化算法与理论第五章习题答案_工学_高等教育...2014年12月大学英语四级经典参考范文四季养生 中医养生...2014教师资格材料分析辅... 2014小学教师资格考试《...
数据结构与算法第5章课后答案_工学_高等教育_教育专区。数据结构与算法 课后答案...【解答】2h -1,2h-1 【分析】最小结点个数的情况是第1层有1个结点,其他...
数据结构与算法分析习题及... 44页 2财富值 数据结构与算法习题二参考... 4...计算机科学概论(刘艺著)第5章 数据结构与算法 习题与答案计算机科学概论(刘艺著...
第五章习题参考答案_理学_高等教育_教育专区。自动原理第五章课后习题第...证券从业资格考试投资分析考点识记89份文档 爆笑大撞脸 超爆笑笑话 有趣及爆笑...
第五章成本分析综合练习题参考答案 一、名词解释 1.机会成本:又称替换成本,是指生产者为了生产一定数量的产品所放弃的使用相同的生 产要素在其他生产用途中所能...
热门文档