《算法设计与分析》分治法实验报告一.doc

宁波工程学院电信学院计算机教研室 实验报告 课程名称： 算法设计与分析 实验项目：实验一：分治法 指导教师： 苏日娜 实验位置： 计算机中心二楼 姓 名： 梅胤 班 级： 计科094 学 号： 29 日 期： 2011/10/17  实验目的 通过上机实验，要求掌握分治法算法的问题描述、算法设计思想、程序设计和算法复杂性分析等。 二、实验环境：VC6.0 三、实验内容 用分治法算法解最接近点对问题 （1）问题的描述 给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。#includeiostream #includecstdlib #includectime #includecmath using std::cout; using std::endl; #define N 5 int x[N],y[N],record[N]; //产生原始点数据，x坐标放在x[]中，y坐标放在y[]中。 double Min; /////////////////////////产生随机数组///////////////////////////// void randnum() { int i; srand(time(0)); for (i=0;iN;i++) { x[i]=rand()%N; coutx[i] ; } coutendl; for (i=0;iN;i++) { y[i]=rand()%N; couty[i] ; } coutendl; } ///////////////////////////交换数组元素/////////////////////////// void swap(int a, int b) { int temp=a; a=b; b=temp; } //求平方// int square(int x) { return x*x; } //求两点之间距离// double lengthf(int x1,int y1,int x2,int y2) { return sqrt(square(x1-x2)+square(y1-y2)); } //求两者中最小者// double min(double a,double b) { if (a=b) return b; else return a; } //对平面数组排序// void sort(int A[]) { int i,j; for (i=0;iN;i++) record[i]=i; for (j=1;jN;j++) { i=j; while (i=0A[i]A[i-1]) { swap(A[i],A[i-1]); swap(record[i-1],record[i]); //得到x排序后对应的原y的坐标 i--; } } cout排序后的元素数组：endl; for (i=0;iN;i++) coutA[i] ; coutendl; for (i=0;iN;i++) coutrecord[i] ; coutendl; } //分治法// double merge(int left,int right) { double mlength; if (right==left) mlength=10e-6; if (right==left+1) mlength=lengthf(x[right],y[record[right]],x[left],y[record[left]]); //两个点时求最小值 if (right-left==2) mlength=min(min(len