xx.txt

该程序实现对一维数据轴上的最临近点的求解问题 采用方法：分治方法1（该方法在递归时由于使用数组的值

/******************************************************
该程序实现对一维数据轴上的最临近点的求解问题
采用方法：分治方法1（该方法在递归时由于使用数组的值，使得
          递归进栈的数据很多，消耗系统空间很大，所以最多
		  处理的个数经测试不超过70个，可见在设计程序时，考虑
		  空间的使用也是很必要的！）
name:Yangchen
class:20#
num:s0307392
time:2004/11/22
*******************************************************/
#include <iostream.h>
#include <math.h>
#include <string.h>
#include "time.h"
#include "windows.h"
#include <stdlib.h>
#include <stdio.h>
int d;
const int num=70;//最多处理的点的个数

/***************************************************
求最小值函数
****************************************************/
int MIN(int a,int b,int c)
{
	if((a<=b)&&(a<=c))
	   return a;
    if((b<=a)&&(b<=c))
       return b;
    if((c<=a)&&(c<=b))
       return c;
}

/*********************************************
求距离函数
********************************************/
int dmin1(int a[],int n)
{   
	int max,min,i,m,d1,d2,max1,min1,n1,n2;
	int a1[num],a2[num];
	/***************************************
	处理点少于2的情况
	****************************************/
    if (n<2)
      d=655359;
    /***************************************
	处理点多于等于2的情况
	****************************************/
     else 
	 {
       max=min=a[0];
	   for(i=0;i<n-1;i++)
	   {
		   if(a[i+1]>a[i])
	          max=a[i+1];
	       else 
		      min=a[i+1];
	   }
	   m=(min+max)/2;//找出中位数
       n1=n2=0;
	   for(i=0;i<n;i++)
	   {if(a[i]<m)
	     a1[n1++]=a[i];
	    else
		 a2[n2++]=a[i];
	   }
       d1=dmin1(a1,n1);
	   d2=dmin1(a2,n2);
      //找分点两侧的点max1和min1
	   max1=a1[0];
	   for(i=0;i<n1-1;i++)
	   {if(a1[i+1]>a1[i])
	    max1=a1[i+1];
	   }
	   min1=a2[0];
	   for(i=0;i<n2-1;i++)
	   {if(a2[i+1]<a2[i])
	   min1=a2[i+1];
	   }
	   /**************************************
	   求最近点的距离d
	   ***************************************/
	   d=MIN(d1,d2,min1-max1);
   	 }
  return(d);
}

void main()
{
    int b[num]; 
    int  k,i,j,all,x;     
   	bool repeat=FALSE;
	bool Again=FALSE;	//是否继续进行其他最近点对的求解
    char yn; 
	int SpendTime=0;	//花费时间
	int TempTime;		
  	cout<<"****************************************************"<<endl;
	cout<<"该程序用分治法求解一维空间上的最小距离点对。\n若输入点对中，有重复出现的点对，则按一个处理。"<<endl;
	while(!Again)
	{
		cout<<"\n****************************************************"<<endl;
		all=1;
		for (i=0;i<num;i++)
		{
			b[i]=0;
		}	
		
		cout << "\n请输入要处理点的个数（最多 " << num << " 个）: ";
		cin >> k;	
		/**********************************************************
		 用srand函数生成随机数(采用机器时间)
		***********************************************************/
		srand( (unsigned)time( NULL ) ); 
		for (i=0;i<k;i++)
			{
				repeat=FALSE;
				x=rand();
				for(j=0;j<all;j++)
				{
					//判断是否存在重复输入的点
					if(x==b[j])
					{
						repeat=TRUE;
						break;
					}
				
				}
				if(!repeat)
					{
					   b[all-1]=x;
					    all++;
					}
			}

		cout << endl;
		k=all-1;
		cout<<"\n无重复的点的个数为： "<<k<<endl;
		if(k==1)
		{
			cout<<"最近距离为 0"<<endl;
			cout<<"两种算法的时间开销相同！"<<endl;
		}
		else
		{   
			TempTime=(int)GetTickCount();//记录算法开始时间
			d=dmin1(b,k);
			SpendTime=(int)GetTickCount()-TempTime;//算法花费时间
		    cout << "其最近距离为： " << abs(d)<< endl;
			cout<<"一般方法的时间开销为： "<<SpendTime<<"ms"<<endl;
			cout<<endl;
		}
		cout<<"\n继续进行其他最近点对的求解吗?(Y/N)";
		cin>>yn;
		if(yn=='Y' ||yn=='y')
			Again=FALSE;
	    else
			if(yn=='N' ||yn=='n')
				Again=TRUE;
		
	}
}