decfunction.cpp

算法实验:1 分治法在数值问题中的应用 ——最近点对问题 2 减治法在组合问题中的应用——8枚硬币问题 3 变治法在排序问题中的应用——堆排序 4 动态规划法在图问题中的应用——全源最短路径问题

#include "decConquer.h"
//Comparing the weight of two piles of coins 
//Input:	Two piles of coins A and B
// return 0 if the piles weith the same,
//-1 if A is lighter the B, 1 if A is not lighter than B
int Compare(Coin A[],Coin B[],int len){
	int i=0;
	int l=len;
	while( i<l && (A[i].weigth==B[i].weigth) )
		i++;
	if(i==l)
		return 0;
	else if( i<l && (A[i].weigth < B[i++].weigth))
		return -1;
	return 1;
}

//Detecting the fake coin from A
//Input:	an array A that record the weigth of each coin
//Output:	coin record fake coin in the array A of loacation and weight 
void FakeCoin(Coins A,int num,Coin *coin){
	assert(num>0);
	int div;
	int comp;
	Coin S1[MAX_COIN/2],S2[MAX_COIN/2];
	if(num>1){
		div=num/2;
		ArrayCopy(S1,A,0,div);
		if(num%2==0)
			ArrayCopy(S2,A,div,num);
		else 
			ArrayCopy(S2,A,div,num-1);
		if( (comp=Compare(S1,S2,div))==0)
			(*coin)=A[num-1];
		else if(comp==1)
			FakeCoin(S2,div,&(*coin));
		else FakeCoin(S1,div,&(*coin));		
	}
	else
		(*coin)=A[0];
}

//Atuo-generate weight
void AutoWeight(Coins *A,int *num){
	int i,number,weight,location;
	printf("请输入硬币的数量 (大于1小于%d)",MAX_COIN);
	scanf("%d",&number);
	assert(number>1);
	(*num)=number;
	(*A)=(Coin *)malloc(number*sizeof(Coin));
	srand( (unsigned int)time(0));
	weight=abs(rand()%10)+5;
	for(i=0;i<number;i++){
		(*A)[i].weigth=weight;
		(*A)[i].index=i;
	}
	location=abs( rand()%(number-1) );		//fake coin in the array of location
	(*A)[location].weigth=weight-3;
}

//
void Output(Coins A){
	int i=-1;
	while(A[++i].weigth>0)
		printf("index=%d weight=%d\n",A[i].index,A[i].weigth);
}

//Copy the Array A of the elements into array S
ArrayCopy(Coins S,const Coins A,int start,int end){
	int i,j=0;
	for(i=start;i<end;i++,j++)
		S[j]=A[i];
}

void DecStart(){
	Coins C;
	Coin coin;
	char c;
	int num;
start:
	system("cls");
	AutoWeight(&C,&num);
	Output(C);
	FakeCoin(C,num,&coin);
	printf("Fake coin: index=%d  weight=%d\n",coin.index,coin.weigth);
	printf("继续?(y/n)\n");
	while((c = getchar()) != '\n' && c != EOF);
	if(getchar()=='y')
		goto start;
}