首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在数组中,某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如,在数组{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
76
问题
在数组中,某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如,在数组{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
学硕统考专业
相关试题推荐
下列关于清朝军机处的叙述,不正确的是()。
下列有关曲辕犁的表述正确的是()①曲辕犁早在中国汉代即已使用了②曲辕犁在中国出现至少比欧洲早一千多年③我国古代的农业工具和农耕技术曾长期居世界领先地位④处于“蒸汽时代”的欧洲农业技术革新,滞后于同时代工业的发展
在苏俄新经济政策的内容中,最能体现多种所有制成分的是()。
新石器时代的房屋建筑根据环境的不同形成了不同的类型,()地区多为干栏式建筑。
杜鲁门总统执政时期,针对美国国内问题提出的计划是()。
试论科举制的历史作用。
()是宋代为支付军政费用而筹措的一宗款项。同时又是各地为筹措这项经费而加征的苛捐杂税的总名称
北约和华约两个组织对峙近半个世纪,这()。
某系统中n个相互独立的生产者进程为一个消费者进程提供数据,假设每个生产者提供的数据写入各不相同的缓冲区,且生产者写缓冲区的速度比消费者读缓冲区的速度快,则缓冲区个数的最优值应为()。
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
随机试题
能导致企业的经营利润和资本不能自由汇出或抽回的政治风险是________。
下列关于视杆细胞的叙述,错误的是
正常心电图在以下哪一个导联P波是倒置的
用于小儿外感风热,内郁化火,发热头痛的是
桥梁球型支座水平承载力试验,受试验设备能力限制时,经与用户协商可选用小型支座进行试验。()
视频通道传输参数色度/亮度时延差标准值为≤70ns()。
会计资料所反映的内容和结果,应当同单位实际发生的经济业务的内容及其结果相一致,这是会计资料的()。
个人及家庭收支流量大多以()来计算,对照期初与期末的现金,看记账时有无漏记之处。
“坚定地同亚、非、拉美以及其他地区的发展中国家站在一起,坚决支持他们捍卫国家主权、发展民族经济的正义斗争;支持欧洲、日本等国家反对超级大国控制、威胁的斗争。”上述内容反映了我国20世纪()以来的外交策略。
我国行政系统的一般监督不包括()。
最新回复
(
0
)