已知由n(n≥2)个正整数构成的集合A={ak｜0≤k＜n)，将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2，设计一个尽可能高效的划分算法，满足｜n1—n2｜最小且｜S1—S2｜最大。要求：给出算

admin2017-08-16 53

问题已知由n(n≥2)个正整数构成的集合A={a_k｜0≤k＜n)，将其划分为两个不相交的子集A₁和A₂，元素个数分别是n₁和n₂，A₁和A₂中元素之和分别为S₁和S₂，设计一个尽可能高效的划分算法，满足｜n₁—n₂｜最小且｜S₁—S₂｜最大。
要求：
给出算法的基本设计思想。

选项

答案由题意知，将最小的[n/2]个元素放在A1中，其余的元素放在A₂中，分组结果即可满足题目要求。仿照快速排序的思想，基于枢轴将n个整数划分为两个子集。根据划分后枢轴所处的位置i分别处理： ①若i=4[n，2]，则分组完成，算法结束； ②若i＜[n，2]，则枢轴及之前的所有元素均属于A₁，继续对j之后的元素进行划分； ③若i＞[n，2]，则枢轴及之后的所有元素均属于A₂，继续对i之前的元素进行划分；基于该设计思想实现的算法，毋须对全部元素进行全排序，其平均时间复杂度是O(n)，空间复杂度是O(1)。

解析

转载请注明原文地址:https://kaotiyun.com/show/eJRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

已知由n(n≥2)个正整数构成的集合A={ak｜0≤k＜n)，将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2，设计一个尽可能高效的划分算法，满足｜n1—n2｜最小且｜S1—S2｜最大。要求：给出算

计算机408

学硕统考专业

1895年发现X射线，拉开物理学革命序幕的科学家是()。

以下内容不属于中国共产党为解决中西部落后问题，巩固发展国防事业而采取的三线建设的是()。

关于斯巴达的论述错误的是()。

德国发动二战以后，未进攻苏联先进攻英法的主要依据是()

使用天然火最早出现于人类发展过程的哪一阶段?()

世界古代历史上，对东西方文化交流、传播作出突出贡献的是()

文艺复兴运动兴起的时间是()。

欧洲历史上第一部系统完备的法典是（）。

下列著作被人们称为17世纪物理学、数学的百科全书，并标志着经典力学体系的完成的是()。

关于高压蒸汽灭菌法，不正确的描述是

医疗机构工作人员上岗工作，必须佩戴标牌。标牌除载明本人姓名外，还应载明

关于总成本费用的计算公式，下列正确的是()。[2010年真题]

根据系统安全理论，下列关于系统中危险源控制的观点，正确的是()。

开展各项调查研究是标价计算之前的一项重要准备工作，是成功投标报价的基础，下列选项属于应调查内容的是()。

根据《著作权法》的规定，不适用著作权法的作品包括()。

与上年相比，2006年我国铜材进口平均价格()根据上述，下列说法不正确的是()

技术转移，是指技术成果从一个企业、一个机构转移到其他企业、机构的活动。大范围的技术转移就形成技术扩散。根据以上的定义，下列不是技术转移的是()。

以下关于CMM的叙述中，不正确的是()。