《算法设计与分析》实验报告学 号： 姓 名： 日 期： 得 分： 一、 实验内容：分治法和蛮力法求最近对问题及其时间复杂度比较二、所用算法的基本思想及复杂度分析：1.蛮力法求最近对问题：1） 基本思想：分别计算每一对点之间的距离，然后找出距离最小的那一对，为了避免对同一对点计算两次距离，只考虑的那些点对2）复杂度分析：对于此算法，主要就是算两个点的欧几里得距离注意到在求欧几里得距离时，避免了求平方根操作，其原因是：如果被开方的数越小，则它的平方根也越小所以复杂度就是求平方，求执行次数为：;即时间复杂度为2.分治法求最近对问题：1）基本思想：用分治法解决最近点对问题，就是将一个问题分解两个子问题，然后递归处理子问题，然后合并可能两个点在每个子问题中，也可能两个点分别在两个子问题中，就这两种情况则基本过程为：找一条中垂线(坐位集合坐标的中位数)把个元素分成左右两部分元素，然后分别求得两边的最短距离,，然后取两者中的最小者记为，在中线两边分别取的距离，记录该距离范围内点的个数，中线左边有个元素，右边有个元素，分别将两边的点按y坐标升序排列，在左边集合中每一个点，找右边集合的点，找到与之距离小于的点，更新最短距离，直到循环结束，即可求出最短距离。
2）复杂度分析：应用分治法求解含有个点的最近对问题，其时间复杂性可由递推式表示：由以上分析：合并子问题的解的时间进而可得分治法求最近对问题的时间复杂度为：三、 源程序及注释：#include#include#include#include#includeusing namespace std;#define eps 1e-8#define MAXN 10000000#define N 5000struct Point{ double x,y;};Point S[N*2],S1[N],S2[N],P1[N],P2[N];double Distance(Point a,Point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}int cmp1(Point a, Point b){ return a.xb?b:a;}//分治法求最近对问题double ClosestPoints1(Point S[],int n){ int i,j,m; if (n<2) return MAXN; else { double d0=MAXN; double d,d1,d2; int k1=0; int k2=0; int j1=0; int j2=0; sort(S,S+n,cmp1); Point p=S[n/2]; m=p.x; //m=S中各点x坐标的中位数 for(i=0;i<(n+1)/2;i++) { S1[j1].x=S[i].x; S1[j1].y=S[i].y; j1++; } //构造S1中点的坐标小于m for(i=(n+1)/2;i
五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训： 1.课本只给出了伪代码，具体的实验要靠自己动手上机反复实验才能完成要通过赋简单值法来初步检验程序的是否正确，再以相同数据检验两种方法的运行结果是否一致来进一步判断程序是否正确，同时使得两种算法的比较更加公平，实验更有可信度 2.要比较分治法和蛮力法求最近对问题的时间复杂度，就要两者各自的运行时间为此，必须要有大量数据，便利用了rand（）函数产生大量随机数，还增加了实验可信度3.不要太迷信课本其中课本上伪代码的函数返回值类型定义为int型，使得赋简单值时运行结果始终为0，注意到这一点，将int改为double才得到了较准确的运行结果所以，编程是要自己多动脑思考，才能真正解决问题。