淮海工学院计算机工程学院
实验报告书
课程名： 《算法分析与设计》 题 目： 实验1 递归与分治算法
班 级： 学 号： 姓 名：
评语： 成绩： 指导教师： 批阅时间： 年 月 日
《 算法分析与设计》实验报告 - 1 -
实验1 递归与分治算法
实验目的和要求
（1）进一步掌握递归算法的设计思想以及递归程序的调试技术； （2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。 （3）分别用蛮力法和分治法求解最近对问题；
（4）分析算法的时间性能，设计实验程序验证分析结论。 实验内容
设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。 实验环境
Turbo C 或VC++ 实验学时
2学时，必做实验 数据结构与算法
核心源代码 蛮力法：
#include
int ClosestPoints(int x[ ], int y[ ], int n); int main() {
int x[3],y[3];
printf(\请输入各点的横坐标: \
for(int i=0;i<4;i++) { }
scanf(\
printf(\请输入各点的纵坐标: \
for(int j=0;j<4;j++)
《 算法分析与设计》实验报告 - 2 -
{ }
scanf(\
ClosestPoints(x,y,4); }
int ClosestPoints(int x[ ], int y[ ], int n) {
int index1, index2; //记载最近点对的下标 int d, minDist = 1000; //假设最大距离不超过1000 for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++) //只考虑i＜j的点对
{ return 0;
d =sqrt ((x[i]-x[j])* (x[i]-x[j]) + (y[i]-y[j])* (y[i]-y[j])); if (d < minDist) { minDist = d; index1 = i; index2 = j;
}
}
cout<<\最近的点对是：\ 和 \
return minDist; } 分治法：
#include
struct point //定义点的结构体 { };
int x, y;