首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知由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
36
问题
已知由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
学硕统考专业
相关试题推荐
战后列强围绕中国问题产生的矛盾及其表现。
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
兵家是专门研究军事理论和实践的学派,主要代表人物是战国中期齐国的(),他所著的兵书是一部杰出的古代兵书。
汉章帝会群儒于白虎观,讨论经义,由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书,这部书系统地吸收了阴阳五行和谶纬之学,形成今文经学派的主要观点。
以下关于阿兹特克文化的叙述,不正确的是()。
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
1942年太平洋战争爆发后,日本先后夺取了焦作、开滦等煤矿,华北沦陷区每年向日本输送的原煤达800万吨。这说明日本在沦陷区进行经济掠夺的直接目的是()。
“二战”后,联合国的成立反映了世界人民和平的愿望,下列叙述正确的是()。
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
五四运动后,马克思主义在中国广泛传播。1920年在上海出版了最早的《共产党宣言》中文全译本,译者是()
随机试题
氯气泄漏后,处理空气中氯的最好方法是向空气中( )。
尿浓缩的主要部位是【】
()是确定工程造价(计划价格)的经济文件。
背景资料:某堤防工程项目业主与承包商签订了工程施工承包合同。合同中估算工程量为5300m3,单价为180元/m3,合同工期为6个月。有关付款条款如下:(1)开工前业主应向承包商支付估算合同总价20%的工程预付款。(2)业主自第一个月起
部门预算中的一般预算支出包括()。
难度是指项目的难易程度,用P代表。P值越(),难度越低。
一般情况下,使用鼠标双击计算机桌面上的应用程序快捷图标即可()。
[*]
在关系模型的数据库管理系统中,三种基本关系运算是______。
WhendidthewomangototheSummerPalace?
最新回复
(
0
)