《2022年算法设计与分析-实验-递归与分治算法- .pdf》由会员分享，可在线阅读，更多相关《2022年算法设计与分析-实验-递归与分治算法- .pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、淮海工学院计算机工程学院实 验 报 告 书课 程 名 ：算法分析与设计题目：实验 1 递归与分治算法班级：学号：姓名：评语：成绩：指导教师：批阅时间：年月日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - 算法分析与设计实验报告- 1 - 实验 1 递归与分治算法实验目的和要求（1）进一步掌握递归算法的设计思想以及递归程序的调试技术；（2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。（3）分别用蛮力法和分治法求解最近对
2、问题；（4）分析算法的时间性能，设计实验程序验证分析结论。实验内容设 p1=(x1, y1), p2=(x2, y2), , pn=(xn, yn)是平面上 n 个点构成的集合 S，设计算法找出集合 S中距离最近的点对。实验环境Turbo C 或 VC+ 实验学时2 学时，必做实验数据结构与算法#include #include #include #define N 100 using namespace std; struct point int x,y; ; bool cmpx(point a,point b) return a.xb.y; 名师资料总结 - - -精品资料欢迎下载 - -
3、 - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - 算法分析与设计实验报告- 2 - int Sqrt(point a,point b)/两点间的距离的平方 int k; k=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); return k; double min(double d1,double d2) if(d1=d2) return d1; else return d2; bool different(point p,int n,int s
4、tart,int end) for(int i=start;iend;i+) if(pi.x=pend.x&pi.y=pend.y) return true; return false; int ClosestPoints1(point p,int n,point & one,point & two)/求出两最近点的相关信息 int d=9999; for(int i=0;in;i+) for(int j=i+1;jn;j+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，
5、共 9 页 - - - - - - - - - 算法分析与设计实验报告- 3 - int temp=Sqrt(pi,pj); if(tempd) one=pi; two=pj; d=temp; return d; int ClosestPoints2(point S,int n) if(n2) return 10000; if(n=2) int d=Sqrt(S0,S1); return d; sort(S,S+n,cmpx);/按照 X大小排序int m=Sn/2.x; int t=n/2;int i=0; point S15000,S25000; for(i=0;it;i+) S1i=Si
6、; for(i=t;in;i+) S2i-t=Si; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 9 页 - - - - - - - - - 算法分析与设计实验报告- 4 - int d1=ClosestPoints2(S1,t); int d2=ClosestPoints2(S2,n-t); int d=min(d1,d2); point p1N,p2N; int j=0; int p1l=0,p2l=0; / 对 x 坐标差值在2d 之间的点进行归类，找到这些点f
7、or(i=0;it;i+) if(abs(S1i.x-m)d) p1p1l=S1i; p1l+; for(i=0;in-t;i+) if(abs(S2i.x-m)d) p2p2l=S2i; p2l+; / 对两个区间内的点沿Y坐标轴进行排序 sort(p1,p1+p1l,cmpy); sort(p2,p2+p2l,cmpy); int md=9999; for(i=0;ip1l;i+) for(j=0;fabs(p2j.y-p1i.y)d;j+) int pd=Sqrt(p1i,p2j); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -
8、 - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - 算法分析与设计实验报告- 5 - md=min(pd,md); return min(d,md); void main() point pN,a,b; int n=20;int d; coutn; cout 请输入各点（中间用空格）:endl; for(int i=0;in;i+) cout 第 i+1pi.xpi.y; d=ClosestPoints1(p,n,a,b); coutn蛮力法求最近点对：endl; cout 最短距离为 :sqrt(d)endl; cout 两个点分别
9、为 :(a.x,a.y) , (b.x,b.y)endl; d=ClosestPoints2(p,n); coutn分治法求最近点对：endl; cout 最短距离为 :sqrt(d)endl; cout 两个点分别为 :(a.x,a.y) , (b.x,b.y)endl; 核心源代码蛮力法核心源代码：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - 算法分析与设计实验报告- 6 - int ClosestPoints1(poin
10、t p,int n,point & one,point & two)/蛮力法求出两最近点的相关信息 int d=9999; for(int i=0;in;i+) for(int j=i+1;jn;j+) int temp=Sqrt(pi,pj); if(tempd) one=pi; two=pj; d=temp; return d; 分治法核心源代码：int ClosestPoints2(point S,int n) if(n2) return 10000; if(n=2) int d=Sqrt(S0,S1); return d; sort(S,S+n,cmpx);/按照 X大小排序int m
11、=Sn/2.x; int t=n/2;int i=0; point S15000,S25000; for(i=0;it;i+) S1i=Si; for(i=t;in;i+) S2i-t=Si; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - 算法分析与设计实验报告- 7 - int d1=ClosestPoints2(S1,t); int d2=ClosestPoints2(S2,n-t); int d=min(d1,d2);
12、point p1N,p2N; int j=0; int p1l=0,p2l=0; / 对 x 坐标差值在2d 之间的点进行归类，找到这些点for(i=0;it;i+) if(abs(S1i.x-m)d) p1p1l=S1i; p1l+; for(i=0;in-t;i+) if(abs(S2i.x-m)d) p2p2l=S2i; p2l+; / 对两个区间内的点沿Y坐标轴进行排序 sort(p1,p1+p1l,cmpy); sort(p2,p2+p2l,cmpy); int md=9999; for(i=0;ip1l;i+) for(j=0;fabs(p2j.y-p1i.y)d;j+) int
13、pd=Sqrt(p1i,p2j); md=min(pd,md); return min(d,md); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - 算法分析与设计实验报告- 8 - 实验结果实验体会通过这次实验，我更加了解了蛮力法与分治法的本质区别，当我们在面对庞大数据时，分治法能更高效的完成任务，分治法将一个复杂的问题简单抽象地分成若干个子问题，很轻而易举的利用递归就完成了，本次实验存在的问题是：对最近点对相关的算法细节不是很清晰。所以在今后的学习中，我将会把学习的重点放在理解、掌握并熟练地运用上， 这样才能更上一层楼。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -