首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知由n(n≥2)个正整数构成的集合A={ak|0≤k<n),将其划分为两个不相交的子集A1和A2,元素个数分别是n1和n2,A1和A2中元素之和分别为S1和S2,设计一个尽可能高效的划分算法,满足|n1—n2|最小且|S1—S2|最大。 要求: 给出算
已知由n(n≥2)个正整数构成的集合A={ak|0≤k<n),将其划分为两个不相交的子集A1和A2,元素个数分别是n1和n2,A1和A2中元素之和分别为S1和S2,设计一个尽可能高效的划分算法,满足|n1—n2|最小且|S1—S2|最大。 要求: 给出算
admin
2017-08-16
70
问题
已知由n(n≥2)个正整数构成的集合A={a
k
|0≤k<n),将其划分为两个不相交的子集A
1
和A
2
,元素个数分别是n
1
和n
2
,A
1
和A
2
中元素之和分别为S
1
和S
2
,设计一个尽可能高效的划分算法,满足|n
1
—n
2
|最小且|S
1
—S
2
|最大。
要求:
给出算法的基本设计思想。
选项
答案
由题意知,将最小的[n/2]个元素放在A1中,其余的元素放在A
2
中,分组结果即可满足题目要求。仿照快速排序的思想,基于枢轴将n个整数划分为两个子集。 根据划分后枢轴所处的位置i分别处理: ①若i=4[n,2],则分组完成,算法结束; ②若i<[n,2],则枢轴及之前的所有元素均属于A
1
,继续对j之后的元素进行划分; ③若i>[n,2],则枢轴及之后的所有元素均属于A
2
,继续对i之前的元素进行划分; 基于该设计思想实现的算法,毋须对全部元素进行全排序,其平均时间复杂度是O(n),空间复杂度是O(1)。
解析
转载请注明原文地址:https://kaotiyun.com/show/eJRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
《关于建国以来党的若干历史问题的决议》
以下内容不属于中国共产党为解决中西部落后问题,巩固发展国防事业而采取的三线建设的是()。
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
1925年爆发的当时世界上罢工时间最长的一次斗争是()。
“改土归流”政策的根本目的是()。
下列选项中,不属于选官制度的是()
下列选项中,不属于列宁《四月提纲》内容的是()。
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
欧洲历史上第一部系统完备的法典是()。
随机试题
紫外光谱分析中所用比色皿是()。
计算机网络的发展经历了四个阶段,现阶段是
男性,60岁,货车司机,既往体健,有吸烟史30年,因“浮肿、尿少、肾功能进展1个月”就诊。患者1个月前因浮肿、尿量减少在当地医院测血压为160/95mmHg,查尿常规示PRO(+++),RBC15~20/HP,Cr168μmol/L,BUN9.5
根据《互联网药品信息服务管理办法》,关于互联网信息服务管理的说法,正确的是()。
公路建设市场信用信息包括公路建设从业单位的()。
有些学生虽然知道道德规范,也愿意遵守,但却受个人欲望的支配,不能抗拒诱惑因素,结果做出违反道德规范的事。其主要原因是这些学生()。
具有高科技含量、高文化附加值特征的各类创新型产业所形成的经济形态可以被称为()。
给定资料近年来,河北省平山县一直把消除贫困、改善民生作为不懈追求,到2015年年底全县脱贫5.4万人,贫困发生率由21%下降到9.1%。但受自然环境和历史欠账等因素影响,平山至今仍是国家级扶贫开发工作重点县,还有近l/10的群众生活在贫困线之下。
A、 B、 C、 D、 B
Whatwillfuturehistoriansrememberabouttheimpactofscience【C1】______thelastdecadeofthe20thcentury?Theywillnotb
最新回复
(
0
)