首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知由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
39
问题
已知由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
学硕统考专业
相关试题推荐
简述联合国的成立过程、宗旨及组成机构。
评述两税法实行的原因、内容及意义。
1934年9月苏联加入国联,对此说法错误的一项是()。
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
文艺复兴运动兴起的时间是()。
1962年1、2月间,中共中央召开的统一思想、总结经验教训、明确工作方向的会议是()。
下列事件:①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订,按照时间顺序排列正确的是()。
全国高校院系调整的具体时间是()。
近代思想家如何传播西方思想革新中国政治的?
全国高校院系调整的具体时间是()。
随机试题
试分析《苏武传》中苏武的形象。
(2010年10月)我国《土地管理法》规定的保护耕地的主要措施包括______、_______、_______、_______、_______。
为了有效地达到组织目标,促成组织发展,而采取与满足工作者个人需要有关的工作内容、工作职能和工作关系的设计是
炎症反应最重要的功能是
小儿指纹色鲜红的主病为
对于报关企业,海关要求其在设立时具备()条件。
对基金投资进行限制的主要目的有()。I.降低风险Ⅱ.避免基金操纵市场Ⅲ.发挥基金引导市场的积极作用Ⅳ.增加基金资产的收益水平
父权制确立的标志是()。
Marriagetherapiststeachaskillcalledactivelistening.Eachpartnertakesaturnlistening,thenparaphraseswhathe’sheard
Oneofthehobbiesweknowthecavemenhadwas______.
最新回复
(
0
)