《算法分析与设计》实验一：递归与分治算法

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

实验报告书

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

班 级： 学 号： 姓 名：

评语： 成绩： 指导教师： 批阅时间： 年 月 日 《 算法分析与设计》实验报告 - 1 -

实验1 递归与分治算法

实验目的和要求

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

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

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

Turbo C 或VC++ 实验学时

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

蛮力法时是首先给定一组点对，然后对这些点对求最近点对，输出最近点对及其距离的平方，其时间复杂度为O（n2）；用分治法时依次输入要求点对的横坐标和纵坐标，然后求最近点对的距离并输出，在用此方法时，声明了一个point结构体类型，在此结构体中定义了点的横纵坐标。 核心源代码 蛮力法

#include #include using namespace std;

#define point 50

int ClosestPoints(int n,double x[point],double y[point]) {

double d,minDist=1999; int index1,index2,i,j;

《 算法分析与设计》实验报告 for(i=0;i

index1=i;

index2=j; minDist=d; }

}

cout<<\

点

(\

(\距离最近，且最近为:\ return 0;

}

void main() { double x[3]={22,33,44},y[3]={33,44,22};

cout<<\注意]该题所显示的是距离的平方!!!\ ClosestPoints(3,x,y);

} 分治法

#include #include using namespace std;

struct Point {

- 2 -

与

点

距离点 《 算法分析与设计》实验报告 - 3 -

};

double x; double y;

double max(Point s[],int n) { }

double ClosetPoints(Point s[],int n) {

double x;

x=(s[0].x+s[n-1].x)/2; return x;

int i,j,a=0,b=0,e=0,f=0,g=0;

double p=50000.0,sum=0,m,d1,d2,d,c[100],min; Point s1[100],s2[100],temp, p1[100],p2[100]; if(n<2)

return p;

for(i=0;i

m=max(s,n); for(i=0;i

for( j=n-1;j>=i;j--) { }

if(s[j].x

temp=s[j]; s[j]=s[j-1]; s[j-1]=temp;

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

{

if(s[i].x

s1[a++]=s[i];

else }

d1=ClosetPoints(s1,a); d2=ClosetPoints(s2,b);

s2[b++]=s[i];

if(d1

d=d1;

else

d=d2;

for(i=0;i

if(abs(s1[i].x-m)

p1[e++]=s1[i];

}

for(i=0;i

if(abs(s2[i].x-m)

p2[f++]=s2[i];

}

for(i=0;i

for(int j=e-1;j>=i;j--) {

if(p1[j].y

temp=p1[j]; p1[j]=p1[j-1]; p1[j-1]=temp;