首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知由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
32
问题
已知由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://jikaoti.com/ti/unfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
欧洲第二战场的开辟过程及其意义。
兵家是专门研究军事理论和实践的学派,主要代表人物是战国中期齐国的(),他所著的兵书是一部杰出的古代兵书。
以下关于阿兹特克文化的叙述,不正确的是()。
下列选项中,不属于选官制度的是()
阅读以下史料,结合相关背景知识,分析古巴比伦社会的等级制度和奴隶制度。《汉谟拉比法典》(节录)第七条自由民从自由民之子或自由民之奴隶手中买得或为之保管银或金。或奴隶,或女奴,或牛,或羊,或驴,或不论任何物,而无证人及契约者,是为窃贼,
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
试述西欧城市兴起的原因、方式及其影响。
“钟鸣鼎食”往往用来形容贵族生活。考古发现的青铜乐器“钟”始见于周代遗址,可能存在于()
1940年毛泽东的《新民主主义论》:“而所谓民主主义,现在已不是旧范畴的民主主义,已不是日民主主义,而是新范畴的民主主义,而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
随机试题
铰孔时使用不同的协削液会影响铰孔后的孔径。()
正常人全血的比重主要取决于
与运动调节有关的黑质-纹状体通路的递质是
下列各项,能够增加企业当期营业外收入的有()。
某机动车制造股份公司为增值税一般纳税人,2019年7月有关业务如下:(1)内销自产货物包括:销售A型小轿车80辆(消费税税率为5%),不含税单价8万元/辆;销售客货两用车32辆,不含税单价3.4万元/辆;销售卫生通信车取得不含税销售额71.18万元。(
一、注意事项1.申论考试与传统的作文考试不同,是分析驾驭材料的能力与表达能力并重的考试。2.作答参考时限:阅读资料40分钟,作答110分钟。3.仔细阅读给定的资料,按照后面提出的“作答要求”依次作答在答题纸指定位置。
耶路撒冷旧城是______、伊斯兰教和基督教三大宗教发源地,三教都把耶路撒冷视为圣地。
下面关于TCP/IP参考模型与ISO/OSI参考模型关系的描述,正确的是______。
在关于报表数据源设置的叙述中,以下正确的是
EducationalValuesLifeisratherhecticforstudentsduringthefirstweekatNorthAmericanuniversities.However,students
最新回复
(
0
)