最接近点对问题.doc

一、最接近点对问题(一维)
1、最接近点对问题(一维)
最接近点对问题:给定平面上n个点,找其中的一对点,使得在n个点的所有点对中,该点对的距离最小。此时S中的n个点退化为x轴上的n个实数x1,x2,..,xn。最接近点对即为这n个实数中相差最小的2个实数。
2、分析
将所给的平面上n个点的集合S分成2个子集S1和S2,每个子集中约有n/2个点,·然后在每个子集中递归地求其最接近的点对。S1和S2的最接近点对未必就是S的最接近点对,如果组成S的最接近点对的2个点都在S1中或都在S2中,则问题很容易解决。但是,如果这2个点分别在S1和S2中,则对于S1中任一点p,S2中最多只有n/2个点与它构成最接近点对的候选者,仍需做n2/4次计算和比较才能确定S的最接近点对。
因此,依此思路,合并步骤耗时为O(n2)。
整个算法所需计算时间T(n)应满足:
T(n)=2T(n/2)+O(n2)
它的解为T
(n)=O(n2)
3、伪代码
随机Random
float Random()
{
float result=rand()%10000;
return result*;
}
返回最大、最小
float Max OR Min(float s[],int p,int q)//返回s[]中的最大值
{
float s_max(s_min)=s[p];
for(int i=p+1;i<=q;i++)
if(s_max<s[i])
s_max=s[i]; OR
if(s_min>s[i])
s_min=s[i];
return s_max(s_min)
}
主要函数
Cpair Cpair1(float s[],int n)
{
Cpair out_p_d={99999,0,0};
if(n<2) return out_p_d;
float m1=Max(s,0,n-1),m2=Min(s,0,n-1);
float m=(m1+m2)/2;//找出点集中的中位数
int j=0,k=0;
//将点集中的各元素按与m的大小关系分组
float s1[M],s2[M];
for(int i=0;i<n;i++)
{
if(s[i]<=m) {s1[j]=s[i];j++;}
else {s2[k]=s[i];k++;}
}
Cpair d1=Cpair1(s1,j),d2=Cpair1(s2,k);//递归
float p=Max(s1,0,j-1),q=Min(s2,0,k-1);
//返回s[]中的具有最近距离的点对及其距离
if(<)
{
if((q-p)<)
{
=(q-p);
=q;
=p;
return out_p_d;
}
else return d1;
}
else
{
if((q-p)<)
{
=(q-p);
=q;
=p;
return out_p_d;
}
else return d2;
}
}
4、程序实现
#include<>
#include <iostream>
using namespace std;
const int M=50;
struct Cpair
{
float d;
float d1,d2;
};
float Random();
int input(float s[],int number_used);
float Max(float s[],int p,int q);
float Min(float s[],int p,int q);
Cpair Cpair1(float s[],int n);
void main()
{
srand((unsigned)time(NULL));
int number_used,m;
float s[M];
Cpair d;
m=input(s,number_used);
d=Cpair1(s,m);
cout<<endl<<"the closest pair is ("<<<<","<<<<")";
cout<<endl<<"the min distance is "<<<<endl;
}
float Random()
{
float result=rand()%10000;