最近对问题-递归与分治算法.doc

最近对问题-递归与分治算法
《 算法分析与设计》实验报告 - 1 -
《 算法分析f(>space) //在满足条件的区域内依次判断
《 算法分析与设计》实验报告 - 5 -
{
=[i];
=[j];
=space;
}
}
--i;
}
}
//分治法求最近对
void DivideConquer(const List &L,CloseNode &closenode,int begin,int end)
{
if(begin!=end)
{
int mid = (begin+end)/2; //排列后的中间的那个点
double midX = [mid].x;
DivideConquer(L,closenode,begin,mid); //继续在左半边用分治法求最近对
DivideConquer(L,closenode,mid+1,end); //继续在右半边用分治法求最近对
《 算法分析与设计》实验报告 - 5 -
middle(L,closenode,mid,midX); //判断左右各距中线d的区域，是否有最近对
}
}
void main()
{
//初始化
List list;
CloseNode closenode;
= 10000; //最近点的距离
create(list); //输入各点到NList中
cout<<"各点坐标为:"<<endl;
for(int i=0;i<;++i)
cout<<"X="<<[i].x<<" Y="<<[i].y<<"\n";
BruteForce(list,closenode,0,-1);
cout<<"用蛮力法求最近对:"<<endl;
cout<<"最近对为点 ("<<<<","<<<<")和点("<<<<","<<<<")\n"<<"最近距离为: "<<sqrt()<<endl;
《 算法分析与设计》实验报告 - 7 -
cout<<endl<<endl;
cout<<"用分治法求最近对:"<<endl;
paixu(list);
cout<<"经过排序后的各点:"<<endl;
for(int j=0;j<;++j)
cout<<"X="<<[j].x<<" Y="<<[j].y<<"\n";
DivideConquer(list,closenode,0,-1);
cout<<"最近对为点 ("<<<<","<<<<")和点("<<<<","<<<<")\n"<<"最近距离为: "<<sqrt()<<endl;
}
六，核心源代码
//左右各距中线d的区域的最近对算法
void middle(const List & L,CloseNode &cnode,int mid,double midX)
《 算法分析与设计》实验报告 - 7 -
{
int i,j; //分别表示中线左边，右边的点
dou