算法分析习题参考答案第五章.doc

《算法分析习题参考答案第五章.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1．最大子段和问题：给定整数序列，求该序列形如的子段和的最大值：1)已知一个简单算法如下：intMaxsum(intn,inta,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++){intsuma=0;for(intj=i;j<=n;j++){suma+=a[j];if(suma>sum){sum=suma;besti=i;bestj=j;}}}returnsum;}试分析该算法的时间复杂性。2)试用分治算法解最大子段和问题，并分析算法的时间复杂性。3)试说明最大

2、子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。（提示：令）解：1）分析按照第一章，列出步数统计表，计算可得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]的最大子段和为两部分的字段和组成，即；intMaxSubSum(int*

3、a,intleft,intright){　intsum=0;　if(left==right)　　sum=a[left]>0?a[left]:0;else　{intcenter=(left+right)/2;intleftsum=MaxSubSum(a,left,center);　　intrightsum=MaxSubSum(a,center+1,right);　　ints_1=0;　　intleft_sum=0;　　for(inti=center;i>=left;i--){　　　left_sum+=a[i];　　

4、　if(left_sum>s1)　　　　s1=left_sum;　　}　　ints2=0;　　intright_sum=0;　　for(inti=center+1;i<=right;i++){　　　right_sum+=a[i];　　　if(right_sum>s2)　　　　s2=right_sum;　　}　　sum=s1+s2;　　if(sum

5、n){inta；　returnMaxSubSum(a,1,n);}该算法所需的计算时间T(n)满足典型的分治算法递归分式T(n)=2T(n/2)+O(n)，分治算法的时间复杂度为O(nlogn)3）设,则最大子段和为最大子段和实际就是.要说明最大子段和具有最优子结构性质，只要找到其前后步骤的迭代关系即可。若,；若，。因此，计算的动态规划的公式为：intMaxSum(int*a，intn){intsum=0,b=0，j=0;for(inti=1;i<=n;i++){if(b>0)　　b=b+a[i];　else　　

6、b=a[i];end{if}　if(b>sum)　　sum=b;j=i；end{if}}returnsum;}自行推导，答案：时间复杂度为O（n）。1.动态规划算法的时间复杂度为O（n）（双机调度问题）用两台处理机A和B处理个作业。设第个作业交给机器A处理时所需要的时间是，若由机器B来处理，则所需要的时间是。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。以下面的例子说明你的算法：解

7、：（思路一）删除（思路二）在完成前k个作业时，设机器A工作了x时间，则机器B最小的工作时间是x的一个函数。设F[k][x]表示完成前k个作业时，机器B最小的工作时间，则其中对应第k个作业由机器B来处理（完成k-1个作业时机器A工作时间仍是x，则B在k-1阶段用时为）；而对应第k个作业由机器A处理（完成k-1个作业，机器A工作时间是x-a[k]，而B完成k阶段与完成k-1阶段用时相同为）。则完成前k个作业所需的时间为1）当处理第一个作业时，a[1]=2,b[1]=3;机器A所花费时间的所有可能值范围：0£x£a[0

8、].x<0时，设F[0][x]=∞，则max(x,∞)=∞；0£x<2时，F[1][x]=3，则Max(0,3)=3，x³2时，F[1][x]=0，则Max(2,0)=2；2）处理第二个作业时：x的取值范围是：0<=x<=(a[0]+a[1])，当x<0时，记F[2][x]=∞；以此类推下去（思路三）假定个作业的集合为。设为的子集，若安排中的作业在机器A上处理，其余作业在