数组瓜分

www.MyException.Cn  网友分享于：2014-06-19  浏览：0次

数组分割

```// 数组分割
void Array::Divided_Array(int * data,const unsigned int length)
{
// 异常输入
if(data == NULL || length == 0 || length %2 != 0)
{
cout<<"异常输入 Divided_Array"<<endl;
}

// 正常输入
else
{
// 开辟空间，选择算法辅助工具
stack<unsigned int> S ;
int sum_stack = 0 ;
int min;
unsigned int now ;
unsigned int * result = new unsigned int[length/2];

// 求出数组的和
int sum_array = Sum_Array(data,length) ;
cout<<"sum_array = "<<sum_array<<endl;
// 核心算法
S.push(0) ;
sum_stack = data[0] ;
min = sum_array/2 - sum_stack;
now = 0;
while( true )
{

// 进栈原则
// 和不够大
if(sum_stack < sum_array/2)
{

// 元素个数不够
if(S.size() < length/2)
{
// 栈顶没有走到数组尾部
if(now < length-1)
{
now++;
S.push(now);
sum_stack += data[now];
}

// 栈顶已经走到数组尾部
else{
if(S.empty() == false)
{
now = S.top();
sum_stack -= data[S.top()];
S.pop();

}
else break;
}
}

// 元素个数已经够了,
// 检查是否比当前组合更符合大案要求，
// 如果是则保存一下
else if(S.size() == length/2)
{
if(sum_array/2 - sum_stack < min)
{
min = sum_array/2 - sum_stack;
Stack_To_Array(S,result);
}
// 出栈，更新栈，继续寻找
now = S.top();
sum_stack -= data[now];
S.pop();

}
}

// 出栈原则
else if(sum_stack > sum_array/2)
{
// 出栈，更新栈，继续寻找
now = S.top();
sum_stack -= data[now];
S.pop();

}

// 如果当前栈的和等于数组和的一半
else
{
if(S.size() == length/2)
{
min = sum_array/2-sum_stack;
Stack_To_Array(S,result);
break;
}
else
{
// 出栈，更新栈，继续寻找
if(S.empty() == false)
{
now = S.top();
sum_stack -= data[S.top()];
S.pop();
}
else break;
}
}
}

cout<<"min = "<<min<<endl;
cout<<"sum_stack = "<<sum_stack<<endl;
for(unsigned int i=0;i<length/2;i++)
{
cout<<data[result[i]]<<" ";
}
cout<<endl;

}
}

// 数组求和
int Array::Sum_Array(int * data,const unsigned int length)
{
// 异常输入
if(data == NULL || length == 0 || length %2 != 0)
{
cout<<"异常输入 Divided_Array"<<endl;
return -1;
}

// 正常输入
else
{
int sum = 0;
for(unsigned int i =0;i<length;i++)
sum += data[i];
return sum;
}
}

// 栈复制到数组
void Array::Stack_To_Array(stack<unsigned int> S,unsigned int * &data)
{
unsigned int length = S.size();
if(length == 0)
{
return void(0);
}
data = new unsigned int[length];
for(unsigned int i = length-1;i < length;i--)
{
data[i] = S.top();
S.pop();
}
return void(0);
}```