蛮力法求最近点对问题

  • B2_514955
    了解作者
  • 920.6KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-04-01 15:48
    上传日期
按课本算法做出来的,请求大家指教,因为是作业所以有不必要的界面输出,请只研究核心代码。
蛮力法求最近点对问题.rar
  • 最近点对问题
  • Debug
  • test1.pch
    1.9MB
  • vc60.idb
    81KB
  • vc60.pdb
    108KB
  • test1.obj
    268.2KB
  • test1.ilk
    810.1KB
  • test1.exe
    584.1KB
  • test1.pdb
    1.1MB
  • test1.cpp
    4.3KB
  • test1.opt
    47.5KB
  • test1.vcproj
    5KB
  • test1.dsw
    518B
  • test1.dsp
    3.3KB
  • test1.plg
    244B
  • test1.vcproj.KURORO-4B2C31F7.kuroro.user
    1.4KB
  • test1.ncb
    41KB
  • test1.suo
    2.5KB
内容介绍
#include <iostream> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> using namespace std; const int N = 100005; const double MAX = 10e10; const double eps = 0.00001; struct Point { double x, y; int index; } ; Point a[N], b[N], c[N]; double closest(Point *, Point *, Point *, int, int); double dis(Point, Point); int cmp_x(const void *, const void*); int cmp_y(const void *, const void*); int merge(Point *, Point *, int, int, int); inline double min(double, double); int ClosestPoints(int,Point *,int &,int &); int main() { int n, i; float d,e; int index1=0,index2=0,index3=0,index4=0; char choice,choice2; do { system("cls"); cout<<"┌─────────────────────┐"<<endl; cout<<"│实验:最近对问题 │"<<endl; cout<<"│系别:计算机工程系 │"<<endl; cout<<"│班级:07级计算机科学与技术2班 │"<<endl; cout<<"│姓名:刘菲菲 │"<<endl; cout<<"│学号:200630891032 │"<<endl; cout<<"└─────────────────────┘"<<endl; cout<<endl<<"请输入点的个数"; cin>>n; cout<<"输入坐标格式为3 4,即(3,4)"<<endl; for (i = 0; i < n; i++) { cout<<"第"<<i+1<<"个点坐标(x,y):"; cin>>a[i].x>>a[i].y; } cout<<"请选择运算方法"<<endl; cout<<"1.蛮力法 2.分治法 3.结束:"; do { cin>>choice; if (choice == '1') {e = sqrt(ClosestPoints(n,a,index1,index2)); cout<<"第"<<index1+1<<"个点("<<a[index1].x<<","<<a[index1].y<<") 和第"<<index2+1<<"个点("<<a[index2].x<<","<<a[index2].y<<")的距离最短"<<endl; cout<<"蛮力法算出最近点对距离为"<<e<<endl; } else if(choice == '2') { qsort(a, n, sizeof(a[0]), cmp_x); for (i = 0; i < n; i++) a[i].index = i; memcpy(b, a, n *sizeof(a[0])); qsort(b, n, sizeof(b[0]), cmp_y); d = sqrt(closest(a, b, c, 0, n - 1)); cout <<"分治法算出最近点对距离为"<<d<<endl; } else if(choice == '3') break; else cout<<"选择错误,请重新选择"; }while(choice!='3'); cout<<"是否结束程序结束,结束请按n,继续请按任意键"<<endl; cin rel='nofollow' onclick='return false;'>>choice2; }while( choice2!='n' ) ; return 0; } int ClosestPoints(int n,Point a[],int &index1,int &index2)//蛮力法 { int i,j,d; int minDist=60000; for(i=1;i<n;i++) for(j=i+1;j<=n;j++) { d=(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y); if(d<minDist) {minDist=d; index1=i; index2=j; } } return minDist; } double closest(Point a[], Point b[], Point c[], int p, int q)//分治法 { if (q - p == 1) return dis(a[p], a[q]); if (q - p == 2) { double x1 = dis(a[p], a[q]); double x2 = dis(a[p + 1], a[q]); double x3 = dis(a[p], a[p + 1]); if (x1 < x2 && x1 < x3) return x1; else if (x2 < x3) return x2; else return x3; } int m = (p + q) / 2; int i, j, k; double d1, d2; for (i = p, j = p, k = m + 1; i <= q; i++) if (b[i].index <= m) c[j++] = b[i]; //数组c左半部保存划分后左部的点, 且对y是有序的. else c[k++] = b[i]; d1 = closest(a,c ,b, p, m); d2 = closest(a, c,b, m + 1, q); double dm = min(d1, d2); merge(b, c, p, m, q); //数组c左右部分分别是对y坐标有序的, 将其合并到b. for (i = p, k = p; i <= q; i++) if (fabs(b[i].x - b[m].x) < dm) c[k++] = b[i]; //找出离划分基准左右不超过dm的部分, 且仍然对y坐标有序. for (i = p; i < k; i++) for (j = i + 1; j < k && c[j].y - c[i].y < dm; j++) { double temp = dis(c[i], c[j]); if (temp < dm) { dm = temp; } } return dm; } double dis(Point p, Point q) //求两个点的距离函数 { double x1 = p.x - q.x, y1 = p.y - q.y; return x1 *x1 + y1 * y1; } int merge(Point p[], Point q[], int s, int m, int t) { int i, j, k; for (i = s, j = m + 1, k = s; i <= m && j <= t;) { if (q[i].y > q[j].y) { p[k++] = q[j]; j++; } else { p[k++] = q[i]; i++; } } while (i <= m) p[k++] = q[i++]; while (j <= t) p[k++] = q[j++]; memcpy(q + s, p + s, (t - s + 1) *sizeof(p[0])); return 0; } int cmp_x(const void *p, const void *q) //判断两点x坐标的大小关系 { double temp = ((Point*)p)->x - ((Point*)q)->x; if (temp > 0) return 1; else if (fabs(temp) < eps) return 0; else return - 1; } int cmp_y(const void *p, const void *q) ////判断两点y坐标的大小关系 { double temp = ((Point*)p)->y - ((Point*)q)->y; if (temp > 0) return 1; else if (fabs(temp) < eps) return 0; else return - 1; } inline double min(double p, double q) //返回两个double数的最小值 { return (p > q) ? (q): (p); }
评论
    相关推荐
    • 算法
      算法 算法
    • 程序员算法
      这是一个算法文档压缩包,其中包括《可能与不可能的边界》、《具体数学》、《算法的乐趣》、《啊哈!算法》。这些书很适合对算法感兴趣的朋友,书籍讲解算法非常有趣。注意,其中有些文档是试读版本。
    • 算法实验
      算法实验算法实验算法实验算法实验算法实验算法实验算法实验算法实验
    • SIFT 算法
      SIFT 算法SIFT 算法SIFT 算法SIFT 算法
    • RSA算法
      RSA算法是公钥加密算法中重要的算法之一,本算法即实现RSA的加解密过程。
    • 分词算法介分词算法
      算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语...
    • unify算法
      unify算法unify算法unify算法unify算法unify算法unify算法unify算法unify算法unify算法unify算法unify算法unify算法unify算法
    • 寻路算法
      寻路算法 寻路封装
    • dsp算法算法算法算法
      dsp各种算法
    • 大数据算法
      本书共分为10章,第1章概述大数据算法,第2章介绍时间亚线性算法,第3章介绍空间亚线性算法,第4章概述外存算法,第5章介绍大数据外存查找结构,第6章讲授外存图数据算法,第7章概述MapReduce算法,第8章通过一系列...