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

《算法分析与设计》实验报告-2-
实验1递归与分治算法
一，实验目的和要求
（1）进一步掌握递归算法的设计思想以及递归程序的调试技术；
（2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。
（3）分别用蛮力法和分治法ace)//在满足条件的区域内依次判断
《算法分析与设计》实验报告-4-
《算法分析与设计》实验报告-3-
}
}
{
=[i];
=[j];
=space;
《算法分析与设计》实验报告-8-
《算法分析与设计》实验报告-5-
}
}
--i;
}
}//分治法求最近对
voidDivideConquer(constList&L,CloseNode&closenode,intbegin,intend){
if(begin!=end)
{
intmid=(begin+end)/2;//排列后的中间的那个点
doublemidX=[mid].x;
//继续在左半边用分治法求最近对
//继续在右半边用分治法求最近对
//判断左右各距中线d的区域，是否有最
DivideConquer(L,closenode,begin,mid);
DivideConquer(L,closenode,mid+1,end);middle(L,closenode,mid,midX);
近对
}voidmain()
{
//初始化
Listlist;
CloseNodeclosenode;
=10000;//最近点的距离
create(list);//输入各点到NList中
cout〈〈"各点坐标为："〈〈endl;
for(inti=0;i<;++i)
cout〈〈"X="〈〈[i].x〈〈"Y="〈〈[i].y〈〈"\n";
BruteForce(list,closenode,0,-1);
cout〈〈"用蛮力法求最近对:"<<endl;
cout〈〈"最近对为点("〈〈〈〈","〈〈〈〈")和点("〈〈〈〈","〈〈〈〈")\n"〈〈"最近距离为:"〈〈sqrt()〈〈endl;
cout〈〈endl〈〈endl;
cout〈〈"用分治法求最近对："〈〈endl;
paixu(list);
cout〈〈"经过排序后的各点："〈〈endl;
for(intj=0;j〈;++j)
cout〈〈"X="〈〈[j].x〈〈"Y="〈〈[j].y〈〈"\n";
DivideConquer(list,closenode,0,-1);
cout〈〈"最近对为点("〈〈〈〈","〈〈〈〈")和点("〈〈〈〈","〈〈〈〈")\n"〈〈"