2016年計算機聯考真題——尋求最大子集和的差

概述

已知由n（n>=2）個正整數構成的集合A ，将其劃分成兩個不相交的子集A1和A2，元素個數分别為n1和n2，A1和A2中元素之和分别為S1和S2。設計一個盡可能高效的劃分算法，滿足|n1-n2|最小且|S1-S2|最大。要求：

1）給出算法的基本設計思想。

2）根據設計思想，采用C或C++語言描述算法，關鍵之處給出注釋。

3）說明你所設計算法的平均時間複雜度和空間複雜度。

算法思想

根據快速排序的思想，把找到最佳的劃分，把最小的[n/2]個數放到A1，其餘的數放到A2。分組結果即為題意所求。

算法步驟：

1）若i=[n/2]，則劃分結束。

2）若i<[n/2]，則樞軸及之前的所有元素均屬于A1，繼續對i之後的元素進行劃分。

3）若i>[n/2]，則樞軸及之後的所有元素均屬于A2，繼續對i之前的元素進行劃分。

基于該設計思想，毋須堆全部元素進行排序，其平均時間複雜度為O(n),空間複雜度為O(1)。

全部代碼

#include <iostream>
#include <cstdlib>
using namespace std;

//初始化數組 
void SetArray(int* data,int size)
{
    //srand(time(0));
    cout<<"随機初始化"<<size<<"個數"<<endl;
    for(int i = 0 ; i < size ; i++){
        data[i] =rand()%100+1;
    }
}

void Print(int* data ,int size)
{
    for(int i = 0 ; i < size ; i++){
        cout<<data[i]<<" "; 
    }
    cout<<endl;
}

//交換函數 
void Swap(int* a ,int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int FindMax(int* data,int size)
{
    int low = 0,high = size-1;
    int low0 = 0,high0 = size-1;
    int k = size/2;
    bool flag = true;
    while(flag){
        int pivot = data[low];      //确定樞紐 
        while(low < high){
            //找到右邊第一個比樞紐小的數 
            while(low < high && data[high] > pivot){
                high--;
            }
            if(low != high){//如果還劃分沒有結束 
                data[low] = data[high];
            }
            //找到左邊第一個比樞紐大的數 
            while(low < high && data[low] < pivot){
                low++;
            }
            if(low != high){//如果還劃分沒有結束 
                data[high] = data[low];
            }
            data[low] = pivot;//把樞紐放到合适的位置
            if(low == k-1){//如果low剛好是中間位置 
                flag = false;
            }else if(low < k-1){//現在樞紐位置小于中間位置 
                low0 = low++;//說明前low個數是已經是最小的了 
                high = high0;
            }else{
                high0 = high--;//說明後high個數是已經是最大的了
                low = low0;
            } 
        }
    }
    int s1 = 0,s2 = 0;
    for(int i = 0 ; i < k ; i++){
        s1 += data[i];
    }
    for(int i = k ; i < size ; i++){
        s2 += data[i];
    }
    return s2-s1;
 } 

int main()
{
    cout<<"請輸入數組長度:"<<endl;
    int size,*data;
    cin>>size; 
    data = new int[size];

    SetArray(data,size);
    int max = FindMax(data,size);
    cout<<"數組為："<<endl;
    Print(data,size); 
    cout<<"劃分樞紐為："<<endl;
    cout<<data[size/2];
    cout<<"劃分結果為："<<endl;
    Print(data,size/2);
    Print(data+size/2,size-size/2); 
    cout<<"最大子集和的差為：";
    cout<<max;

    return 0;
 }            

複制

截圖為：