/******************************************************
該程序?qū)崿F(xiàn)對一維數(shù)據(jù)軸上的最臨近點(diǎn)的求解問題
采用方法：分治方法1（該方法在遞歸時(shí)由于使用數(shù)組的值，使得
          遞歸進(jìn)棧的數(shù)據(jù)很多，消耗系統(tǒng)空間很大，所以最多
		  處理的個(gè)數(shù)經(jīng)測試不超過70個(gè)，可見在設(shè)計(jì)程序時(shí)，考慮
		  空間的使用也是很必要的！）
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;//最多處理的點(diǎn)的個(gè)數(shù)

/***************************************************
求最小值函數(shù)
****************************************************/
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;
}

/*********************************************
求距離函數(shù)
********************************************/
int dmin1(int a[],int n)
{   
	int max,min,i,m,d1,d2,max1,min1,n1,n2;
	int a1[num],a2[num];
	/***************************************
	處理點(diǎn)少于2的情況
	****************************************/
    if (n<2)
      d=655359;
    /***************************************
	處理點(diǎn)多于等于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;//找出中位數(shù)
       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);
      //找分點(diǎn)兩側(cè)的點(diǎn)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];
	   }
	   /**************************************
	   求最近點(diǎn)的距離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;	//是否繼續(xù)進(jìn)行其他最近點(diǎn)對的求解
    char yn; 
	int SpendTime=0;	//花費(fèi)時(shí)間
	int TempTime;		
  	cout<<"****************************************************"<<endl;
	cout<<"該程序用分治法求解一維空間上的最小距離點(diǎn)對。\n若輸入點(diǎn)對中，有重復(fù)出現(xiàn)的點(diǎn)對，則按一個(gè)處理。"<<endl;
	while(!Again)
	{
		cout<<"\n****************************************************"<<endl;
		all=1;
		for (i=0;i<num;i++)
		{
			b[i]=0;
		}	
		
		cout << "\n請輸入要處理點(diǎn)的個(gè)數(shù)（最多 " << num << " 個(gè)）: ";
		cin >> k;	
		/**********************************************************
		 用srand函數(shù)生成隨機(jī)數(shù)(采用機(jī)器時(shí)間)
		***********************************************************/
		srand( (unsigned)time( NULL ) ); 
		for (i=0;i<k;i++)
			{
				repeat=FALSE;
				x=rand();
				for(j=0;j<all;j++)
				{
					//判斷是否存在重復(fù)輸入的點(diǎn)
					if(x==b[j])
					{
						repeat=TRUE;
						break;
					}
				
				}
				if(!repeat)
					{
					   b[all-1]=x;
					    all++;
					}
			}

		cout << endl;
		k=all-1;
		cout<<"\n無重復(fù)的點(diǎn)的個(gè)數(shù)為： "<<k<<endl;
		if(k==1)
		{
			cout<<"最近距離為 0"<<endl;
			cout<<"兩種算法的時(shí)間開銷相同！"<<endl;
		}
		else
		{   
			TempTime=(int)GetTickCount();//記錄算法開始時(shí)間
			d=dmin1(b,k);
			SpendTime=(int)GetTickCount()-TempTime;//算法花費(fèi)時(shí)間
		    cout << "其最近距離為： " << abs(d)<< endl;
			cout<<"一般方法的時(shí)間開銷為： "<<SpendTime<<"ms"<<endl;
			cout<<endl;
		}
		cout<<"\n繼續(xù)進(jìn)行其他最近點(diǎn)對的求解嗎?(Y/N)";
		cin>>yn;
		if(yn=='Y' ||yn=='y')
			Again=FALSE;
	    else
			if(yn=='N' ||yn=='n')
				Again=TRUE;
		
	}
}