首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在数组中,某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如,在数组{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
42
问题
在数组中,某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如,在数组{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
学硕统考专业
相关试题推荐
下列内容是武则天独创的是()
一战期间,中国民族资本主义迅速发展的主要作用是()。
30年代,美国推行“中立”政策之所以对法西斯侵略起了绥靖作用,主要是因为它()。
夏王朝建立后,将其领土划分为九州,派九牧进行治理,在九州范围内根据土地的肥沃程度缴纳贡赋,称为()。
下列有关曲辕犁的表述正确的是()①曲辕犁早在中国汉代即已使用了②曲辕犁在中国出现至少比欧洲早一千多年③我国古代的农业工具和农耕技术曾长期居世界领先地位④处于“蒸汽时代”的欧洲农业技术革新,滞后于同时代工业的发展
冶铁技术中的“淬火法”在()已开始应用,大大提高了铁器的坚韧和锋利程度。
曾经来华留学,并在日本大化改新中发挥重要作用的是()。
一个客户机利用FTP协议从服务器上下载文件,如下图所示为整个过程中协议交换的过程,请回答如下问题:(1)该协议层图中第四层协议是什么?(2)如果FTP客户端采用了LIST命令来获得FTP服务器上的文件列表,该列表采用什么端口传输?
某计算机字长16位,采用16位定长指令字结构,部分数据通路结构如下图所示。图中所有控制信号为1时表示有效、为0时表示无效。例如控制信号MDRinE为1表示允许数据从DB打入MDR,MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状
在图B-1所示的平衡二叉树中,插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中,关键字37所在结点的左、右子结点中保存的关键字分别是____。
随机试题
A.螳螂科B.芫青科C.壁虎科D.乌贼科E.稚科斑蝥的原动物科属是()。
要式合同成立地点一般为()
实验室常用的补体灭活条件是
下列药物中可用于钙离子通道阻滞剂所导致严重水肿的是()。
患者,女性,65岁,患风湿性心脏病8年余,近日上呼吸道感染后出现乏力,稍事活动就心悸、气急,伴有乏力,食欲缺乏,肝区胀痛,双下肢轻度水肿。查体:双肺底湿哕音,肝大,肝颈静脉回流征阳性,心率128/分。以地高辛治疗后,病人出现头晕、头痛、恶心、呕吐、黄视
关于钢筋混凝土圆筒、框架结构水塔塔身质量验收主控项目的说法,错误的是()。
下列行为中,违反国家有关节能管理规定的有( )。
IthadbeensometimesinceJackhadseentheoldman.College,carrier,andlifeitselfgotintheway.Infact,Jackmovedcle
山水田园诗:这类诗以描写自然风光、农村景物以及安逸恬淡的隐居生活见长。诗境隽永优美,风格恬静淡雅,语言清丽洗练,多用白描手法。以下各项属于山水田园诗的是()。
毫无疑问,电视节目主持人是当今社会颇具影响力的人群之一。借助大众传媒的影响,主持人成为公众人物。他们的角色因此不同于普通人,而是集社会角色。媒介角色及个人角色于一体的特殊角色。选择了这一职业;不仅仅意味着选择了鲜花和掌声,财富和荣耀,更意味着选择了媒体和社
最新回复
(
0
)