divfuntion.cpp

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

#include "divCon.h"
//Sorts array A[0....n-1] by recursive mergesort
//Input:	An array A[0...n-1] of orderable elements
//Outpur:	An sorted Array A[0...n-1]

void Mergesort(Points *A,const int choice){
	assert((*A).num>0);
	int len;
	Points B,C;
	if((*A).num>1){
		len=(*A).num/2;
		ArrayCopy(&B,*A,0,len);//前半部分放到B中
		ArrayCopy(&C,*A,len,(*A).num);//put last half in C
		Mergesort(&B,choice);
		Mergesort(&C,choice);
		Merge(B,C,&(*A),choice);//&(*A) is a Parameter on each of level****////
	}

}

//Merges two sorted arrays into one sorted array
//Input:	Array B[0...p-1] and C[0..q-1] both sorted
//Output:	Sorted array A[0...p+q-1] of the elements of B and C
void Merge(Points B,Points C,Points *A,const int choice){
	int i=0,j=0,k=0;
	assert(choice==1||choice==2);
	if(choice==1){//按横坐标排序
		while(i<B.num&&j<C.num){
			if(B.p[i].x<C.p[j].x){//compare
				(*A).p[k]=B.p[i];
				i++;
			}else{
				(*A).p[k]=C.p[j];
				j++;
			}
			k++;
		}//while
		if(i==B.num)//把剩余部分连接到A中
			for(;j<C.num;j++,k++)
				(*A).p[k]=C.p[j];
		else{
			for(;i<B.num;i++,k++)
				(*A).p[k]=B.p[i];
		}
	}
	else{//按纵坐标排序
		while(i<B.num&&j<C.num){
			if(B.p[i].y<C.p[j].y){
				(*A).p[k]=B.p[i];
				i++;
			}else{
				(*A).p[k]=C.p[j];
				j++;
			}
			k++;
		}//while
		if(i==B.num)
			for(;j<C.num;j++,k++)
				(*A).p[k]=C.p[j];
		else{
			for(;i<B.num;i++,k++)
				(*A).p[k]=B.p[i];
		}
	}

}


//initialize array A
void InitPoints(Points *A){
	int i;
	(*A).num=0;
	printf("请输入点的数量( >1&&<%d )",MAX_POINT);
	scanf("%d",&(*A).num);
	assert((*A).num>1);
	printf("请依次输入点的横坐标和纵坐标的值\n");
	for(i=0;i<(*A).num;i++){
		printf("坐标%d:\n",i);
		printf("x=");
		scanf("%d",&(*A).p[i].x);
		printf("y=");
		scanf("%d",&(*A).p[i].y);
	}//
}

//Copy the array src[start......end-1] of the elements to array des[0....end-start]
// which from start to end
//复制不包含src[end]
void ArrayCopy(Points *des,Points src,int start,int end){
	assert(src.num>0);
	int i,j;
	for(j=0,i=start;i<end;i++,j++)//复制不包含src[end]
		(*des).p[j]=src.p[i];
	(*des).num=j;
}

//Output array A[0....n-1] of the elements
void Output(Points A){
	assert(A.num>0);//不满足这各条件才执行
	int i;
	for(i=0;i<A.num;i++){
		printf("坐标%d:",i);
		printf("(%d,%d)\n",A.p[i].x,A.p[i].y);
	}
}

//initialize array A[0....n] by auto-generated data
void AutoPoints(Points *A){
	int i;
	(*A).num=0;
	printf("请输入点的数量( >1&&<%d )",MAX_POINT);
	scanf("%d",&(*A).num);
	assert((*A).num>1);
	//function srand() always in combination with rand() function 
	srand((unsigned int)time(NULL));
	for(i=0;i<(*A).num;i++){
		(*A).p[i].x=rand()%50-25;	//Abscissa横坐标
		(*A).p[i].y=rand()%30-15;	//Ordinate纵坐标
	}//
}

//Find two closest points from array A[0....n-1]
//Input:	An  sorted array A[0...n-1]
//Output:	the value of two-point and the two points 
void ClosestPoints(Points A,Distance *D){
	assert( A.num>1 );
	int divide;//divide array A into two subsets B and C
	Points B,C;
	Distance temp;
	if(A.num>6){//divide array A into two subsets B and C
		divide=A.num/2;
		ArrayCopy(&B,A,0,divide);
		ArrayCopy(&C,A,divide,A.num);//let A into two subsets
		ClosestPoints(B,&(*D));//在B中找最近对
		ClosestPoints(C,&(*D));//在C中找最近对
		Closest(B,C,&(*D));//在分界两边找最近对
	}else{
		temp=SmallestDis(A);
		if((*D)->distance<0)//第一次
			(*D)=temp;
		else if( temp->distance < (*D)->distance  )
			(*D)=temp;	
	}//else
}

//Find the smallest distance between two-point in subset A
//return the smallest distance
Distance SmallestDis(Points A){//蛮力法求最近对
	assert(A.num>1);
	int i,j,dis=0;
	int min=INT_MAX;
	int x,y;
	Distance D;
	if( (D=(Distance)malloc(sizeof(Dis)))==NULL )
		exit(1);
	for(i=0;i<A.num-1;i++){
		for(j=i+1;j<A.num;j++){
			dis=POWER(A.p[i].x,A.p[j].x)+POWER(A.p[i].y,A.p[j].y);
			if(dis<min){
				min=dis;
				x=i;
				y=j;
			}
		}
	}//for(i=0)
	D->p1=A.p[x];
	D->p2=A.p[y];
	D->distance=min;
	return D;
}


//在B和C的距离为d的范围内找最近对
void Closest(Points B,Points C,Distance *D){
	assert((*D)->distance>=0);
	int i,j,dis,min;
	int x=INT_MAX,y=INT_MAX;//x、y分别记录找到的点
	int distance=(*D)->distance;
	Points S1,S2;
	S1.p[0]=B.p[B.num-1];
	i=B.num-2;
	j=1;
	while( POWER(S1.p[0].x,B.p[i].x) <= distance &&i>=0){//B中范围在d内的点
		S1.p[j++]=B.p[i--];
	}//
	S1.num=j;
	i=0;
	//C中范围在d内的点
	while( POWER(C.p[i].x,S1.p[0].x) <= distance &&i<C.num )
		S2.p[i]=C.p[i++];
	S2.num=i;
	if(S2.num==0)
		return;
	else{//找最近对
		Mergesort(&S1,2);
#if 0
		puts("====================================\n");
		Output(S1);
		puts("====================================\n");
#endif
		for(i=0;i<S1.num;i++){
			for(j=0;j<S2.num;j++){
				if( POWER(S2.p[j].y,S1.p[i].y) <= distance  
					&& POWER(S2.p[j].x,S1.p[i].x) <= distance ){
					dis=POWER(S2.p[j].x,S1.p[i].x)+POWER(S2.p[j].y,S1.p[i].y);
					if(dis<distance){
						min=dis;
						x=i;
						y=j;
					}
				}//if
			}//for(j=0)
		}//for(i=0)
		if(x!=INT_MAX && y!=INT_MAX){//找到这样的两个点
			(*D)->p1=S1.p[x];
			(*D)->p2=S2.p[y];
			(*D)->distance=min;
		}
		
	}//else
}

void DivStart(){
	char c;
	Points A;
	Distance D;
start:
	system("cls");
	AutoPoints(&A);
	//InitPoints(&A);
	Mergesort(&A,1);
	Output(A);
	if( (D=(Distance)malloc(sizeof(Dis)))==NULL )
		exit(1);
	ClosestPoints(A,&D);
	printf("分治法最近对为:");
	printf("p1(%d,%d)──p2(%d,%d) =%d\n",
		D->p1.x,D->p1.y,D->p2.x,D->p2.y,D->distance);
//#if 0
	printf("蛮力法最近对为:");
	D=SmallestDis(A);
	printf("p1(%d,%d)──p2(%d,%d) =%d\n",
		D->p1.x,D->p1.y,D->p2.x,D->p2.y,D->distance);
	free(D);
	D=NULL;
	printf("继续?(y/n)\n");
	while((c = getchar()) != '\n' && c != EOF);
	if(getchar()=='y')
		goto start;
//#endif
}