ConsoleApplication17.zip

  • mrwangZz
    了解作者
  • C/C++
    开发工具
  • 2KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 0
    下载次数
  • 2020-06-03 23:02
    上传日期
算法设计作业--分治策略求平面最近点对源码
ConsoleApplication17.zip
  • ConsoleApplication17.cpp
    5.5KB
内容介绍
// ConsoleApplication17.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 #include <math.h> #include <random> #include <iostream> #include <time.h> using namespace std; struct point//定义结构体 { int Point;//点的的下标 float x, y;//点的坐标x,y }; float a1[100000] = {0};//初始化数组a1 float b1[100000] = {0};//初始化数组b1 float Distance(point A, point B)//计算两点间距离 { return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y) * (A.y - B.y)); } void quickSort(float *arr, float *arr2, int L, int H)//快速排序 { float temp = arr[L]; float temp2 = arr2[L];//选定中轴数 int i = L;int j = H; if (L < H) { while (i < j) { while (i<j && arr[j] > temp)//数组中从右往左查找第一个比中轴数小的数 j--; arr[i] = arr[j]; arr2[i] = arr2[j]; while (i < j && arr[i] <= temp)//从左往右查找 i++; arr[j] = arr[i]; arr2[j] = arr2[i]; } arr[i] = temp; arr2[i] = temp2; quickSort(arr, arr2, L, i - 1);//递归 quickSort(arr, arr2, i + 1, H);} else return; } void cloest(point X[], point Y[], int l, int h, point &a, point &b, float &min)//分治法查找最近的点 { int i = 0, j = 0, mid = 0; point al, ar, bl, br; float ml = 0, mr = 0; if (h - l <= 0)//当输入点数小于等于1时 { cout << "请输入大于1的整数"; } else if ((h - l) == 1) //点数等于2时直接求距离 { min = Distance(X[l], X[h]); } else { if ((h - l) == 2) //当点数等于3时直接求最短距离 { ml = Distance(X[l], X[l + 1]);//求出1 2点距离 mr = Distance(X[l], X[l + 2]);//求出1 3点距离 min = Distance(X[l + 1], X[l + 2]);//求出2 3点距离 if ((ml <= mr) && (ml <= min))//比较得出最短距离 {a = X[l];//更新点a b = X[l + 1];//更新点b min = ml;//更新min } else {if (mr <= min) {a = X[l]; b = X[l + 2]; min = mr;} else {a = X[l + 1]; b = X[l + 2]; } } } else//当点数大于3时 {mid = (h - l) / 2 + l;//作中垂线 point *PL = new point[(h - l) / 2 + 1];//将平面分为左右均等的两部分点集 point *PR = new point[(h - l) / 2 + 1]; j = 0;int number = 0; for (i = 0; i <= h - l; i++) {if (Y[i].Point <= mid)//记录左边的点 {PL[j++] = Y[i];} else { PR[number++] = Y[i];// 记录右边的点 } } cloest(X, PL, l, mid, al, bl, ml); // 递归计算求得左点集的最近点 cloest(X, PR, mid + 1, h, ar, br, mr);// 递归计算求得右点集的最近点 if (ml < mr)//比较左右点集最短距离 {a = al;//更新点a b = bl;//更新点b min = ml;//更新最短距离min }else {a = ar; b = br; min = mr; } point *Temp = new point[h - l + 1];//定义点集Temp用于记录窄缝中的点 number = 0; for (i = 0; i <= h - l; i++) //记录距离中垂线距离小于min的点,保存到点集 { if ((X[mid].x - Y[i].x) < min || ((Y[i].x - X[mid].x) < min))//判断与中垂线距离是否小于min { Temp[number].x = Y[i].x; Temp[number++].y = Y[i].y; } } for (i = 0; i < number; i++)//计算窄缝中是否有点距小于min的点对 { for (j = i + 1; (j < (i + 7)) && (j < number); j++)//y坐标已排序,只需向下遍历6个点即可 { ml = Distance(Temp[i], Temp[j]); if (ml < min) //与min比较 { a = Temp[i];//更新点a b = Temp[j];//更新点b min = ml;//更新min } } } delete[]Temp;//删除点集Temp } } } void Init(point P1[], point P2[], int N) {std::default_random_engine rand;//生成随机不重复点对 for (int i = 0; i < N; i++) { a1[i] = rand()*0.0000001;//随机生成x坐标 b1[i] = rand()*0.0000001;//随机生成y坐标 //cout << a1[i] <<","<< b1[i] <<endl; } quickSort(a1,b1,0, N - 1);//对点对的横坐标快速排序 for (int i = 0; i < N; i++) { P1[i].x = a1[i];//储存在结构体P1中 P1[i].y = b1[i]; } quickSort(b1, a1, 0, N - 1);//对点对的纵坐标快速排序 for (int i = 0; i < N; i++) { P2[i].Point = i; P2[i].x = b1[i];//储存在结构体P2中 P2[i].y = a1[i]; } } void baoliqiujie(point P1[], point P2[], int N)//暴力求解,与分治求解结果作比较 { float D = 10000; for (int x = 0; x < N; x++) { for (int y = 1; y < N; y++) { float E = Distance(P1[y], P1[x]);//求每个点之间的距离 if (E < D&&E != 0) { D = E;//取最小值 } } }cout << "暴力求解得到的最近距离:" << D << endl;//输出暴力求解结果 } float main() { int n; cout << "输入点的个数n(n>1):"; cin >> n;//输入点对数 point A, B; float MIN = 0; point *X = new point[n];//定义点集X point *Y = new point[n];//定义点击Y clock_t start, finish;//计时 start = clock();//计时开始 Init(X, Y, n); //生成点对并排序 cloest(X,Y,0,n-1,A,B,MIN);//求最近点对 finish = clock();//计时结束 baoliqiujie(X, Y, n);//暴力求解 float t; t = float(finish - start) / CLOCKS_PER_SEC; cout<<"采用分治算法用时:"<< t; //输出算法运算时间 cout <<"平面最近的两个点为:("<< A.x <<","<< A.y <<")"<<"("<< B.x <<","<< B.y <<")\n两点距离为:"<<MIN;//输出最近点对及其距离 system("pause"); }
评论
    相关推荐
    • visualc++.rar
      通过编程实现递归与分治策略的有关算法,理解递归与分治策略算法的原理,掌握递归与分治策略基本思想与应用技巧。
    • DistanceSmallestPoints.rar
      通过分治策略,在O(nlogn)时间复杂度内,找到二维平面区域内距离最小的点对
    • IOI国家集训队论文集1999-2019
      + [最近公共祖先](#最近公共祖先) + [划分问题](#划分问题) * [数论](#数论) + [欧几里得算法](#欧几里得算法) + [同余方程](#同余方程) * [搜索](#搜索) + [搜索](#搜索-1) + [启发式](#启发式) + [优化]...
    • xim1.rar
      果园篱笆和飞行管理问题,java语言实现的,算法课程设计的题目
    • hduoj poj 的题目分类
      大家在刷题时,总是想找各种类型,或单一题型的题目,来提高自己,所以就把以前留下来的POJ,HDUOJ题目分类串传上来了
    • AdAlgo:高级算法知识详解
      分治 贪心 动规 划分问题 回溯 局搜 图灵机与P/NP/NPC P/NP/NPC/NPH 多项式归约和图灵归约 NPC 问题证明(按照归约顺序排序) 列表项中带有 未完成 前缀的问题只描述了问题,没有说明具体证明过程;带有 完成 前缀的...
    • 挑战程序设计竞赛(第2版)
      4.6.3 平面上的分治法 4.7 华丽地处理字符串 4.7.1 字符串上的动态规划算法 4.7.2 字符串匹配 4.7.3 后缀数组 4.8 一起来挑战GCJ的题目(3) 4.8.1 Mine Layer 4.8.2 Year of More Code Jam 4.8.3 Football Team ...
    • MATLAB数值类综合算法常用数值计算工具包
      MATLAB 数值类综合算法常用数值计算工具包龙贝格算法.改进欧拉法.龙格库塔方法.复合辛普森,Matlab数学建模工具箱以及众多实例.常用算法 如遗传算法精解、模拟退火算法、...分治算法.动态规划.组合算法.贪婪算法等等。
    • ShortestDistance.rar
      求平面最近的两个之间的距离,利用分治策略,时间复杂度为O(nlogn)
    • matlabcnhelp.rar
      matlab中文帮助很难找的,快速下载