- 论坛徽章:
- 0
|
/*
问题: 有两个数组a,b,大小都为n,数组元素的值任意,无序。
要求: 通过交换a,b中的元素,使数组a元素的和与数组b元素的
和之间的差最小。
思路: 把a, b的数据合并到临时数组c,对c的数据按升序排序。
选择c里的一对最小数据分别放入a、b,再选择c里的一
对‘次’小数据。如果a的全部数据之和大于b的全部数
据之和,则:‘次’小两数据中,小的数据归入a,大的
归入b,反之小的数据归入b,大的归入a。依次类推。。。
*/
#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#define MAX_SIZE 30
void sort(void * C, int size_c);
void split(int A[], int B[], int size_a, int size_b);
int main(int argc, char* argv[])
{
int i;
int A[MAX_SIZE], B[MAX_SIZE];
printf("\n\na[%d]=\n\n", MAX_SIZE);
for(i=0; i<=MAX_SIZE-1; i++)
{
A[i] = rand() % 100;
printf("\t%d", A[i]);
}
printf("\n\nb[%d]=\n\n", MAX_SIZE);
for(i=0; i<=MAX_SIZE-1; i++)
{
B[i] = rand() % 100;
printf("\t%d", B[i]);
}
split(A, B, sizeof(A)/sizeof(int), sizeof(B)/sizeof(int));
/* 打印a数组的最终结果 */
printf("\n\n\n\n\n\na[%d]=\n\n", MAX_SIZE);
for(i=0; i<=MAX_SIZE-1; i++)
printf("\t%d", A[i]);
/* 打印b数组的最终结果 */
printf("\n\nb[%d]=\n\n", MAX_SIZE);
for(i=0; i<=MAX_SIZE-1; i++)
printf("\t%d", B[i]);
getch();
return 0;
}
/*a, b为待交换数据的数组,size_a为a的长度,size_b为b的长度*/
void split(int A[], int B[], int size_a, int size_b){
int i;
int sum_a = 0, sum_b = 0;
int *C = (int*)malloc( (size_a+size_b)*sizeof(int) );
for(i = 0; i <= size_a; i++)
*(C+i) = A[i];
for(i = 0; i <= size_b; i++)
*(C+size_a+i) = B[i];
sort(C, size_a+size_b);
for(i = 0; i < (size_a+size_b)/2; i++)
{
A[i] = sum_a > sum_b?C[i*2]:C[i*2+1];
B[i] = sum_a > sum_b?C[i*2+1]:C[i*2];
sum_a+=A[i];
sum_b+=B[i];
}
}
/*冒泡法升序排序,c为待排序临时数组,size_c为c的长度 */
void sort(void * C, int size_c){
int i, j, t;
for(i=size_c; i>0; i--)
for(j=0; j<i-1; j++)
if( *((int*)C+j) > *((int*)C+j+1) )
{
t = *((int*)C+j+1);
*((int*)C+j+1) = *((int*)C+j);
*((int*)C+j) = t;
}
} |
|