最近对问题 分治法 ——C语言代码

  • v2_125361
    了解作者
  • 1.5KB
    文件大小
  • 文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-05-10 04:22
    上传日期
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
最近对问题 分治法 详细版.cpp.rar
  • 最近对问题 分治法 详细版.cpp
    3.5KB
内容介绍
#include <iostream> using namespace std; #include <math.h> const int n = 10; struct point { int x, y; }; 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 Partition(point r[ ], int first, int end) //划分 { int i = first, j=end; //初始化待划分区间 while (i < j) { while (i < j && r[i].y <= r[j].y) j--; //右侧扫描 if (i < j) { point temp = r[i]; r[i] = r[j]; r[j] = temp; //将较小记录交换到前面 i++; } while (i < j && r[i].y <= r[j].y) i++; //左侧扫描 if (i < j) { point temp = r[i]; r[i] = r[j]; r[j] = temp; //将较大记录交换到后面 j--; } } return i; // 返回轴值记录的位置 } void QuickSort(point r[ ], int first, int end) //快速排序 { int pivot; if (first < end) { pivot = Partition(r, first, end); //划分,pivot是轴值在序列中的位置 QuickSort(r, first, pivot-1); //求解子问题1,对左侧子序列进行快速排序 QuickSort(r, pivot+1, end); //求解子问题2,对右侧子序列进行快速排序 } } double Closest(point S[ ], int low, int high,point rec[]) { double d1, d2, d3, d; int mid, i, j, index; point P[n],temp1[2],temp2[2],temp3[2]; //存放P1和P2 if (high - low == 1) { //只有两对点 rec[0].x=S[low].x;rec[0].y=S[low].y; rec[1].x=S[high].x;rec[1].y=S[high].y; return Distance(S[low], S[high]); } if (high - low == 2) //只有三对点 { d1 = Distance(S[low], S[low+1]); d2 = Distance(S[low+1], S[high]); d3 = Distance(S[low], S[high]); if ((d1 < d2) && (d1 < d3)){ rec[0].x=S[low].x;rec[0].y=S[low].y; rec[1].x=S[low+1].x;rec[1].y=S[low+1].y; return d1; } else if (d2 < d3){ rec[0].x=S[low+1].x;rec[0].y=S[low+1].y; rec[1].x=S[high].x;rec[1].y=S[high].y; return d2; } else { rec[0].x=S[low].x;rec[0].y=S[low].y; rec[1].x=S[high].x;rec[1].y=S[high].y; return d3; } } mid = (low + high)/2; d1 = Closest(S, low, mid,rec); temp1[0]=rec[0]; temp1[1]=rec[1]; d2 = Closest(S, mid+1, high,rec); temp2[0]=rec[0]; temp2[1]=rec[1]; if (d1 <= d2){ d = d1; rec[0]=temp1[0]; rec[1]=temp1[1]; } else{ d = d2; rec[0]=temp2[0]; rec[1]=temp2[1]; } index = 0; for (i = mid; (i >= low) && (S[mid].x - S[i].x < d); i--) //建立点集合P1 P[index++] = S[i]; for (i = mid + 1; (i <= high) && (S[i].x - S[mid].x < d); i++) //建立点集合P2 P[index++] = S[i]; QuickSort(P, 0, index-1); //对点集合P1和P2按y坐标升序排列 for (i = 0; i < index; i++) //依次处理集合P1和P2中的点 { for(j = i + 1; j < index; j++) { if (P[j].y - P[i].y >= d) //超出y坐标的范围,点P【i】处理完毕 break; else { d3 = Distance(P[i], P[j]); if (d3 < d){ rec[0].x=P[i].x;rec[0].y=P[i].y; rec[1].x=P[j].x;rec[1].y=P[j].y; d = d3; } } } } return d; } int main() { int n; cout<<"请输入共有多少组点对:"<<endl; cin>>n; point S[n]; cout<<"请输入"<<n<<"组点对:"<<endl; for(int i=0;i<n;i++) cin>>S[i].x>>S[i].y; point rec[2]; double minDist = Closest(S,0,n-1,rec); cout<<"最小距离点对为:("<<rec[0].x<<","<<rec[0].y<<"),("<<rec[1].x<<","<<rec[1].y<<")\n"; cout<<"最近点对相距"<<minDist<<endl; return 0; }
评论
    相关推荐
    • 谭浩强C语言
      这是谭浩强C语言的新版,有兴趣想学C语言的童鞋们可以下载来看看啊!
    • 谭浩强c语言
      谭浩强c语言,国内最权威的c语言学习宝典,从零基础开始,成为c语言高手。
    • Makefile c语言
      Makefile c语言Makefile c语言Makefile c语言Makefile c语言 四本资料!自己学习的时候整理的!
    • c语言教程
      c语言教程,优秀的c语言教程,简单基础,是学习c语言的好教程
    • C语言 实现
      C语言 项目实现 《计算方法》课件 俄罗斯方块游戏 C语言实训 综合案例-学生成绩管理程序 C语言程序设计学习与实践指导(源代码)
    • c语言
      c语言
    • C语言库函数
      C语言函数库,里面包括C语言的函数库,方便直接调用,还可以了解很多C语言一些函数模板
    • C语言
      C语言
    • 谭浩强C语言
      谭浩强C语言word版,学习C语言的,经典教材。 使用的编译工具有些老旧,建议是使用visual stdio 2008。
    • 水滴石穿C语言
      学习C语言的有用文档 水滴石穿C语言C语言的底层操作 水滴石穿C语言之extern声明辨析 水滴石穿C语言之static辨析 水滴石穿C语言之typedef的问题 水滴石穿C语言之编译器引出的问题 水滴石穿C语言之代码检查工具 ...