算法第五篇作业.docx

算法第五章作业张2013E80186611331．最大子段和问题：给定整数序列 ，求该序列形如的子段和的最大值： 已知一个简单算法如下：int Maxsum(int n,int a,int besti,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) 分治算法：将所给的序列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]的最大子段和为两部分的字段和组成，即；int MaxSubSum ( int *a, int left , int right){　int sum =0;　if( left==right)　　 sum = a[left] 0? a[ left]:0 ;else　 {int center = ( left + right) /2;int leftsum =MaxSubSum ( a, left , center) ;　　 int rightsum =MaxSubSum ( a, center +1, right) ;　　 int left_sum =0;　　 for ( int i = center ; i = left; i--){　　　 left_sum + = a [ i ];　　　 if( left_sum 0)　　　　 left_sum=0;　　 }　　 int right_sum =0;　　 for ( int i = center +1; i = right ; i++){　　　right_sum + = a[ i];　　　 if( right_sum 0)　　　　 right_sum=0;　　 }　　 sum = left_sum + right_sum;　　 if ( sum leftsum)　　　 sum = leftsum;　　 if ( sum rightsum)　　　 sum = rightsum;}　 return sum;}int MaxSum2 (int n){ int a[]；　 return MaxSubSum ( a, 1, n) ;}该算法所需的计算时间T(n)满足典型的分治算法递归分式T(n)=2T(n/2)+O(n)，分治算法的时间复杂度为O(nlogn)3)设,即那么问题的答案就在.而对于b(j)和b(j-1)，二者有如下关系所以有最优子结构性质，动态规划的公式为intMaxSum (int* a，int n ){int b[n]=0;int sum = 0;b[1]=a[1];for( int i=2;i=n;i++){if( b[i-1] 0)　　b[i] = b[i-1] + a [i];　else　　b [i]= a [i];　if( b [i] sum)　　sum = b[i];}return sum;}容易得到时间复杂度为O（n）2.（双机调度问题）用两台处理机A和B处理个作业。设第个作业交给机器A处理时所需要的时间是，若由机器B来处理，则所需要的时间是。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。以下面的例子说明你的算法：解：设为完成前i个作业，系统所需的最短处理时间，表示在完成前i个作业所需时间最少的策略下，分配到A机器上处理的作业的时间，表示在完成前i个作业所需时间最少的策略下，分配到B机器上处理的作业的时间得到的递推公式，其中。直接的关系式即是，　　　　　　，其中为了方便，，得到算法如下：　　　int minTime(int *a, int *b, int n)　　//a,b为A,B机器上处理作业所用时间数组 {int sa=0;