- 論壇徽章:
- 0
|
/*
問題： 有兩個(gè)數(shù)組a,b，大小都為n,數(shù)組元素的值任意，無序。
要求： 通過交換a,b中的元素，使數(shù)組a元素的和與數(shù)組b元素的
和之間的差最小。
思路： 把a(bǔ), b的數(shù)據(jù)合并到臨時(shí)數(shù)組c，對(duì)c的數(shù)據(jù)按升序排序。
選擇c里的一對(duì)最小數(shù)據(jù)分別放入a、b，再選擇c里的一
對(duì)‘次’小數(shù)據(jù)。如果a的全部數(shù)據(jù)之和大于b的全部數(shù)
據(jù)之和，則：‘次’小兩數(shù)據(jù)中，小的數(shù)據(jù)歸入a，大的
歸入b，反之小的數(shù)據(jù)歸入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數(shù)組的最終結(jié)果 */
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數(shù)組的最終結(jié)果 */
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為待交換數(shù)據(jù)的數(shù)組，size_a為a的長(zhǎng)度，size_b為b的長(zhǎng)度*/
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為待排序臨時(shí)數(shù)組，size_c為c的長(zhǎng)度 */
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;
}
} |
|
免費(fèi)注冊(cè)
樓主: forrestgang
發(fā)表于 2006-11-16 17:24
