首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在数组中,某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如,在数组{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
48
问题
在数组中,某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如,在数组{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年代,美国推行“中立”政策之所以对法西斯侵略起了绥靖作用,主要是因为它()。
近代中国各派军阀的共同点有()①始终打着维护共和制度的旗号②利用中央政权排斥异己③都试图夺取中央政权④以帝国主义列强为靠山
下列有关《布列斯特和约》的说法中,错误的一项是()。
明末清初,著名学者()抗清失败,前往日本讲学,传播中国文化。
下列对1918年德国十一月革命说法不正确的是()。
简述秦统一的历史必然性以及重要意义。
明末清初,著名学者()抗清失败,前往日本讲学,传播中国文化。
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
某计算机的Cache共有16块,采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节,按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(el,e2,…,em);i=1;while(所剩边数>=顶点数){从图中删去ei;若图不再连通。则恢复ei;i=
随机试题
在考生文件夹下的“samp1.accdb”数据库文件中建立表“tBook”,表结构如下:
经过多年改革,到1993年底,我国建立了______的税务制度。()
猫是弓形虫的人是疟原虫的
A.《黄帝内经·素问》B.《难经》C.《外台秘要》D.《临证指南医案》提出“三阳结,谓之膈”的是
对产褥中暑患者正确的处理是:
外国企业常驻代表机构能够准确反映经费支出但不能准确反映收入或成本费用的,可以按经费支出换算收入的方式来核定其应纳税所得额。下列有关代表机构经费支出的表述中,正确的有()。
直线制是一种最简单的集权式组织结构形式,其领导关系按()建立。
执行语句:intresult=100;cout<<(((result>=60)&&(result<=100))?"good":"general");结果是【】。
Everyprofessionortrade,everyart,andeverysciencehasitstechnicalvocabulary,thefunctionofwhichispartlytodesigna
Becauseoftheeconomiccrisis,industrialoutputintheregionremained________.
最新回复
(
0
)