2. 考研
  3. 已知由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｜最大。 要求： 给出算

admin2017-08-16  76
问题 已知由n(n≥2)个正整数构成的集合A={ak｜0≤k＜n)，将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2，设计一个尽可能高效的划分算法，满足｜n1—n2｜最小且｜S1—S2｜最大。
要求：
给出算法的基本设计思想。
选项
答案由题意知，将最小的[n/2]个元素放在A1中，其余的元素放在A2中，分组结果即可满足题目要求。仿照快速排序的思想，基于枢轴将n个整数划分为两个子集。 根据划分后枢轴所处的位置i分别处理： ①若i=4[n，2]，则分组完成，算法结束； ②若i＜[n，2]，则枢轴及之前的所有元素均属于A1，继续对j之后的元素进行划分； ③若i＞[n，2]，则枢轴及之后的所有元素均属于A2，继续对i之前的元素进行划分； 基于该设计思想实现的算法，毋须对全部元素进行全排序，其平均时间复杂度是O(n)，空间复杂度是O(1)。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/eJRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)