文档介绍：淮海工学院计算机工程学院实验报告书课程名: 《算法分析与设计》题目: 实验 1 递归与分治算法班级: 学号: 姓名: 评语: 成绩: 指导教师: 批阅时间:年月日《算法分析与设计》实验报告- 1- 实验 1 递归与分治算法实验目的和要求(1)进一步掌握递归算法的设计思想以及递归程序的调试技术; ( 2)理解这样一个观点:分治与递归经常同时应用在算法设计之中。(3)分别用蛮力法和分治法求解最近对问题; (4)分析算法的时间性能,设计实验程序验证分析结论。实验内容设 p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn) 是平面上 n 个点构成的集合 S, 设计算法找出集合 S中距离最近的点对。实验环境 Turbo C或 VC++ 实验学时 2学时,必做实验数据结构与算法#include<iostream> #include<Cmath> #include<algorithm> #define N 100 using namespace std; struct point { int x,y; }; bool cmpx(point a,point b) { return <; } bool cmpy(point a,point b) { return >; 《算法分析与设计》实验报告- 2- } int Sqrt(point a,point b)// 两点间的距离的平方{ int k; k=(-)*(-)+(-)*(-); return k; } double min(double d1,double d2) { if(d1<=d2) return d1; else return d2; } bool different(point p[],int n,int start,int end) { for(int i=start;i<end;i++) { if(p[i].x==p[end].x&&p[i].y==p[end].y) return true; } return false; } int ClosestPoints1(point p[],int n,point & one,point & two)// 求出两最近点的相关信息{ int d=9999; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) 《算法分析与设计》实验报告- 3- { int temp=Sqrt(p[i],p[j]); if(temp<d) { one=p[i]; two=p[j]; d=temp; }} return d; } int ClosestPoints2(point S[],int n) { if(n<2) return 10000; if(n==2) { int d=Sqrt(S[0],S[1]); return d; } sort(S,S+n,cmpx);// 按照 X 大小排序 int m=S[n/2].x; int t=n/2;int i=0; point S1[5000],S2[5000]; for(i=0;i<t;i++) { S1[i]=S[i]; } for(i=t;i<n;i++) { S2[i-t]=S[i];