最接近点对问题VIP专享

一、最接近点对问题（一维） 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*0.01; } 返回最大、最小 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_maxs[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 #include using namespace std; const int M=50; s...