首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在数组中,某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如,在数组{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+
admin
2018-07-17
78
问题
在数组中,某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如,在数组{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
学硕统考专业
相关试题推荐
隋唐时期实行租庸调制,其中“庸”所起的作用是()
关于德意志宗教改革的说法不正确的是()
洋务派创办军事工业的方式是()。
鸦片战争中,林则徐被革职查办反映的问题是()。
不属于第三次科技革命新特点的选项是()。
对巴黎公社的评述,正确的有()。①是无产阶级建立政权的第一次伟大尝试②主要的经验是废除旧的国家机器,建立新的国家机器③其实践和经验,丰富了马克思主义理论④由于无产阶级的不成熟,其失败是不可避免的
17世纪英国资产阶级革命中,曾利用了古老文件同专制王权作斗争。这一古老文件是()
最早在中国传播马克思主义的是()。
1628年出版了《心血运动论》一书,论证了血液在全身的循环运动,使生理学发展为科学的是()。
已知某32位二进制机器数为11000000000000000000000000000000,试计算在下列各种编码方式下其代表的真值。(1)原码定点小数;(2)补码定点小数;(3)反码定点小数;(4)IEEE754标准短
随机试题
恶露
美国CPS考试的主要范围有
少尿是指
水平放置的渐扩管如图6-43所示,如忽略水头损失,断面形心点的压强有以下关系()。
井筒掘进施工采用抓岩机出渣时,不符合安全要求的内容是()。
下列关于期货公司首席风险官的说法,正确的有()。
下列关于成长型基金、收入型基金、平衡型基金的投资风险的说法中,正确的有()。
Doctorshavetreatedthefirstreportedcaseof"Internetaddictiondisorder"broughtonbyexcessiveuseofGoogleGlass.I
Moreurbancitizensnowprefertoliveincountryside. Writeanarticletoclarifyyourownpointsofviewtowardsthisissu
A、Therearenoneleft.B、Theyaretooexpensive.C、Theymightbeavailableattheconcert.D、Theyneedtobepurchasedinadvanc
最新回复
(
0
)