2016年408算法大题

举报
野猪佩奇996 发表于 2022/01/22 23:53:14 2022/01/22
【摘要】 已知由n(n>=2)个正整数构成的集合A ,将其划分成两个不相交的子集A1和A2,元素个数分别为n1和n2,A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法,满足|n1-n2|最小且|S1-S2|最大。要求: 1)给出算法的基本设计思想。 2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。 3...

已知由n(n>=2)个正整数构成的集合A ,将其划分成两个不相交的子集A1和A2,元素个数分别为n1和n2,A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法,满足|n1-n2|最小且|S1-S2|最大。要求:

1)给出算法的基本设计思想。

2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。

3)说明你所设计算法的平均时间复杂度和空间复杂度。

解析

1根据快速排序的思想,把找到最佳的划分,把最小的[n/2]个数放到A1,其余的数放到A2。分组结果即为题意所求。

算法步骤:

1)若i=[n/2],则划分结束。

2)若i<[n/2],则枢轴及之前的所有元素均属于A1,继续对i之后的元素进行划分。

3)若i>[n/2],则枢轴及之后的所有元素均属于A2,继续对i之前的元素进行划分。


      int setPartition(int a[],int n){
         int pivotkey,low=0,low0=0,high=n-1,high0=n-1,flag=1,k=n/2,i;
         int s1=0,s2=0;
         while(flag){
              pivotkey=a[low]; //选择枢轴
             while(low<high){  //基于枢轴对数据记性划分
                 while(low<high && a[high]>=pivotkey) --high;
                 if(low!=high) a[low]=a[high];
                 while(low<high && a[low]<=pivotkey) ++low;
                 if(low!=high) a[high]=a[low];
              }
              a[low]=pivotkey;
             if(low==k-1) //若枢轴是第n/2个元素,划分成功
              flag=0else if(low<k-1){
                  low0=++low;
                  high=high0;
              }else{
                  high0=--high;
                  low=low0;
              }
          }
         for(i=0;i<k;i++) s1+=a[i];
         for(i=k;i<n;i++) s2+=a[i];
         return s2-s1;
      }
  
 

(3)算法的平均时间复杂度为O(n),空间复杂度为O(1).

【注意】时间复杂度不要误以为是O(logn)

附:快速排序模板(牢记)


      void Quiksort(ElemType A[],int low,int high){
         if(low<high){
             //Partition()是划分操作,将原表划分成2表
             int pivot=Partition(A,low,high);//划分
             QuickSort(A,low,pivot-1);
             QuickSort(A,pivot,high);
          }
      }
      int Partition(ElemType A[],int low,int high){
          ElemType pivot=A[low];//将当前表中第一个元素设为枢轴,对表进行划分
         while(low<high){  //循环跳出条件
             while(low<high&&A[high]>=pivot) --high;
              A[low]=A[high];//将比枢轴小的元素移动到左端
             while(low<high&&A[low]<=pivot)  ++low;
              A[high]=A[low];//将比数轴大的元素移动到左端
          }
          A[low]=pivot;//枢轴元素存放到最终位置
         return low;//返回存放枢轴的最终位置
      }
  
 

 

文章来源: andyguo.blog.csdn.net,作者:山顶夕景,版权归原作者所有,如需转载,请联系作者。

原文链接:andyguo.blog.csdn.net/article/details/106035854

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。