内容发布更新时间 : 2024/11/2 15:15:32星期一 下面是文章的全部内容请认真阅读。

淮海工学院计算机工程学院

实验报告书

课程名： 《算法分析与设计》 题 目： 实验1 递归与分治算法

班 级： 学 号： 姓 名：

评语： 成绩： 指导教师： 批阅时间： 年 月 日

《 算法分析与设计》实验报告 - 1 -

实验1 递归与分治算法

实验目的和要求

（1）进一步掌握递归算法的设计思想以及递归程序的调试技术； （2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。 （3）分别用蛮力法和分治法求解最近对问题；

（4）分析算法的时间性能，设计实验程序验证分析结论。 实验内容

设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。 实验环境

Turbo C 或VC++ 实验学时

2学时，必做实验 数据结构与算法

核心源代码 蛮力法：

#include #include #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 #include const int n = 4;

struct point //定义点的结构体 { };

int x, y;