2. 考研
  3. 在数组中，某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如，在数组{2，4，1，16，7，5，11，9}中，数对之差的最大值是11，是16减去5的结果。 (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C+

在数组中，某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如，在数组{2，4，1，16，7，5，11，9}中，数对之差的最大值是11，是16减去5的结果。 (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C+

admin2018-07-17  91
问题 在数组中，某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如，在数组{2，4，1，16，7，5，11，9}中，数对之差的最大值是11，是16减去5的结果。
    (1)给出算法的基本设计思想。
    (2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
    (3)说明你所设计算法的时间复杂度。
选项
答案分治法。 把数组分成两个子数组，其实没有必要拿左边子数组中较小的数字去和右边子数组中较大的数字作减法。可以想象，数对之差的最大值只可能是下面三种情况之一：①被减数和减数都在第一个子数组中，即第一个子数组中的数对之差的最大值；②被减数和减数都在第二个子数组中，即第二个子数组中数对之差的最大值；③被减数在第一个子数组中，是第一个子数组的最大值。减数在第二个子数组中，是第二个子数组的最小值。这三个差值的最大者就是整个数组中数对之差的最大值。 在前面提到的三种情况中，得到第一个子数组的最大值和第二子数组的最小值不是一件难事，但如何得到两个子数组中的数对之差的最大值?这其实是原始问题的子问题，可以递归地解决。下面是这种思路的参考代码： int MaxDiff_Solutionl(int numbers[]， unsigned length) { if(numbers==NULL｜｜lenath＜2) return 0； int max，min； return MaxDiffCore(numbers，numbers+length—1，&max，&min)； } int MaxDiffCore(int* start，int* end，int* max，int* min) { if(end==start) { *max=*min=*start； return 0； } int* middle=start+(end—start)／2； int maxLeft，minLeft； int leftDiff=MaxDiffCore(start，middle，&maxLeft，&minLeft)； int maxRight，minRight， int rightDiff=MaxDiffCore(middle+1，end，&maxRight，&minRight)； int crossDiff=maxLeft—minRight； *max=(maxLeft＞maxRight)?maxLeft：maxRight； *min=(minLeft＜minRight)?minLeft：minRight； int maxDiff=(leftDiff＞rightDiff)?leftDiff：rightDiff； maxDiff=(maxDiff＞crossDiff)?maxDiff：crossDiff； return maxDiff； }
解析
转载请注明原文地址:https://kaotiyun.com/show/F5Ri777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)