首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在数组中,某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如,在数组{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
52
问题
在数组中,某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如,在数组{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
学硕统考专业
相关试题推荐
《道威斯计划》的实施所产生的直接结果是()。
阅读下列材料,回答问题:材料一:列宁说:“我们在夺取政权时便知道,不存在将资本主义制度具体改造成社会主义制度的现存方法……我不知道哪位社会主义者处理过这类问题……我们必须根据实践作出判断。”——摘自《苏联
典型的西欧封建庄园对农民采用的剥削方式是()。
第一次国共合作采取了共产党员以个人身份加入国民党的党内合作方式,最早提出这种方式的是()。
1940年毛泽东的《新民主主义论》:“而所谓民主主义,现在已不是旧范畴的民主主义,已不是日民主主义,而是新范畴的民主主义,而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是
分页存储管理中,页表的功能是什么?当系统中的地址空间变得非常大时(如32位地址空间),会给页表的设计带来什么样的新问题?请给出一种解决方法,分析它的优点和缺点。
由元素序列(27,16,75,38,51)构造平衡二叉树,则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。
在图B-1所示的平衡二叉树中,插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中,关键字37所在结点的左、右子结点中保存的关键字分别是____。
已知AOE网中顶点v1,v2,v3,……v7分别表示7个时间,有向线段a1,a2,a3,……a10。分别表示10个活动,线段旁的数值表示每个活动花费的天数,如下图所示。请填写下面两个表格,并用顶点序列表示出关键路径,给出关键活动。
随机试题
说明Windows2000/XP采用什么高速缓存,它的作用是什么?
试评析唐代差遣任职法。
测得血糖20天室内质量控制数据,计算出其均值为5.0mmol/L,标准差为0.25mmol/L,其变异系数应为
儿童类风湿病的护理措施()
普通商业企业优先批准销售乙类非处方药的条件是()。
肝硬化患者进食时应细嚼慢咽,必要时药物应研成粉末服用,其目的是
偏心轮质量为m,半径为R,圆心(形心)为O,偏心距OC=e,对质心C的回转半径为P,轮子沿水平面作纯滚动,轮子的角速度为ω,则图示位置时,相对质心C的动量矩LC(大小、方向)为()。
在可行性研究阶段下面内容不必要的是()。
某电器专卖店为一般纳税人,2015年8月发生下列购销业务:(1)销售空调30台,每台零售价格3000元,商场派人负责安装,每台收取安装费510元。(2)采取有奖销售方式销售电冰箱100台,每台零售价格2340元;将外购的50只石英手表对外投资,市场零售
斯巴达和雅典教育体系出现于欧洲的()
最新回复
(
0
)