首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知由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
34
问题
已知由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
学硕统考专业
相关试题推荐
简述两税法产生的背景、内容及其评价。
在印度独立和巴勒斯坦建国问题上,英国扮演了什么角色?有什么影响?
()是一部上起传说中的黄帝,下迄汉武帝时期的中国通史,是中国历史上第一部内容完整、结构周密的历史著作。
下列关于湘军的叙述中不正确的是()。
1891年标志着电机发展新阶段开始的是在电能实际应用中首次采用()。
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
关于希腊早期宗教的叙述不正确的是()。
中华人民共和国恢复在联合国合法席位的时间是()。
欧洲历史上第一部系统完备的法典是()。
德国发动二战以后,未进攻苏联先进攻英法的主要依据是()
随机试题
A.间歇性跛行B.静息痛C.肢体寒冷D.肢端坏疽E.皮色苍白、紫疳、潮红
任脉腧穴的主治病证不包括
背景材料: 某工程签约合同总价为2000万元,开工预付款为合同总价的10%在第1月全额支付。下表是承包人每个月实际支付完成的工程进度款(实际完成量可能超过或少于签约合同价,本题实际完成进度款总额1950万元)。根据《公路工程标准施工招标文件》(2009
下列属于商业银行客户风险内生变量中盈利能力指标的是()。
教师可以通过哪些方面实现对幼儿游戏的指导?
阅读以下函数说明和C语言函数,将应填入(n)处的字句写在对应栏内。【说明】编写程序,利用带参数的主函数main(),实现二进制文件的复制。比如,若该程序已生成可执行文件filebin.exe,在DOS操作系统命令状态下键入如下命令行:
具有多媒体功能的微型计算机系统中,常用的CD-ROM是
Mostpublishingisnow"electronic"inthesensethatbooks,magazines,andnewspapersarepreparedoncomputers,andexistasc
Morethan2,300universitiesinover100countrieshaveintroducedChinesecoursestotheircurricula,andyoungoverseasnation
Aschoolisbeingaskedtoapologizetothefamilyofaboyitprosecutedfortruancy.Theboywas【C1】______ashaving"schoolp
最新回复
(
0
)