实验1++递归与分治算法.docVIP

淮海工学院计算机工程学院 实验报告书 课程名： 《算法分析与设计》 题 目： 实验1 递归与分治算法 班 级： 学 号： 姓 名： 实验1 递归与分治算法 实验目的和要求 （1）进一步掌握递归算法的设计思想以及递归程序的调试技术； （2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。 （3）分别用蛮力法和分治法求解最近对问题； （4）分析算法的时间性能，设计实验程序验证分析结论。 实验内容 设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。 实验环境 Turbo C 或VC++ 实验学时 2学时，必做实验 数据结构与算法 核心源代码 蛮力法： #include iostream.h #include stdio.h #include math.h int ClosestPoints(int x[ ], int y[ ], int n); int main() { int x[3],y[3]; printf(请输入各点的横坐标: ); for(int i=0;i4;i++) { scanf(%d,x[i]); } printf(请输入各点的纵坐标: ); for(int j=0;j4;j++) { scanf(%d,y[i]); } ClosestPoints(x,y,4); return 0; } 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的点对 { 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最近的点对是：index1 和 index2endl; return minDist; } 分治法： #include iostream.h #include math.h const int n = 4; struct point //定义点的结构体 { int x, y; }; double Closest(point S[ ], int low, int high); double Distance(point a, point b); int Partition(point r[ ], int first, int end); void QuickSort(point r[ ], int first, int end); int main() { point S[n] = {{1,1},{3,2},{5,4},{1,2}}; //存放点集合 double minDist = Closest(S,0,n-1); cout最近点对之间的距离为:minDistendl; return 0; } double Closest(point S[ ], int low, int high) { double d1, d2, d3, d; int mid, i, j, index; point P[n]; //存放P1和P2 if (high - low == 1) //只有两个点返回两点之间的距离 return Distance(S[low], S[high]); if (high - low == 2) //只有三个点求最近对距离 { d1 = Distance(S[low], S[low+1]