• Arix11
    了解作者
  • C/C++
    开发工具
  • 1KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 0
    下载次数
  • 2021-03-16 11:44
    上传日期
1. 对于平面上给定的N个点,给出所有点对的最短距离,即,输入是平面上的N个点,输出是N点中具有最短距离的两点。 2. 要求随机生成N个点的平面坐标,应用蛮力法编程计算出所有点对的最短距离。 3. 要求随机生成N个点的平面坐标,应用分治法编程计算出所有点对的最短距离。 4. 分别对N=100,1000,10000,100000,统计算法运行时间,比较理论效率与实测效率的差异,同时对蛮力法和分治法的算法效率进行分析和比较。 5. 如果能将算法执行过程利用图形界面输出,可获加分。
test.zip
  • test.cpp
    4.2KB
内容介绍
#include<iostream> #include<cstdio> #include<cmath> #include<time.h> #include<algorithm rel='nofollow' onclick='return false;'> #define MAX 9999999 #define db double #define tl long long #define maxn 100001 using namespace std; struct point { int x, y; }; point* arr; int chongfu, fpa, fpb; db fzmin; db min(db a, db b) { if (a == b) { return a; } else if (a > b) return b; else return a; } bool cmp(const point& a, const point& b) { //按x升排序辅助函数 return a.x < b.x; } bool cmp2(int a, int b) { //下标数组的排序 return arr[a].y < arr[b].y; } int bigRand(int min, int max) { srand(time(0) + rand()); if (min > max) { min = max; } int rand1 = rand() % 10000; int rand2 = rand() % 10000; int randV = (rand1 * 10000 + rand2) % (max - min + 1);// int randResult = min + randV; return randResult; } int littleRand(int min, int max) { if (min > max) { min = max; } int randV = rand() % (max - min + 1); int randResult = min + randV; return randResult; } db distance1(point A, point B) { return sqrt((B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y)); } void violent2(point* Array, int n)//输出的点为最后一个最小点对 { chongfu = 0; int pa = 0, pb = 0; db min = MAX; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) { db temp = distance1(Array[i], Array[j]); if (fabs(temp - min)<1e-6) chongfu++; else if (temp < min) { min = temp; pa = i; pb = j; } } cout << "有" << chongfu + 1 << "个距离相等的最小点对,其中一组为:(" << arr[pa].x << "," << arr[pa].y << ")与(" << arr[pb].x << "," << arr[pb].y << "),距离为" << min << endl; } db violent1(point* Array, int start, int end) { db min = MAX; int pa = 0, pb = 0; for (int i = start; i < end; i++) for (int j = i + 1; j < end; j++) { db temp = distance1(Array[i], Array[j]); if (temp < min) { min = temp; pa = i; pb = j; } } if (fzmin > min) { fzmin = min; fpa = pa; fpb = pb; } return min; } void createrand(point* arr, int n) { //随机化随机数种子 for (int i = 0; i < n; i++) { arr[i].x = bigRand(0, 30000); arr[i].y = bigRand(0, 30000); //遍历已经生成的所有点,一旦发现重合则重新生成该点 for (int j = 0; j < i; j++) { if (arr[j].x == arr[i].x && arr[j].y == arr[i].y) { i--; break; } } } } db Merge(point* arr, int left, int right) { db d = MAX; if (right - left <= 3) { return violent1(arr, left, right); } //如果点小于等于3,则使用暴力法计算 int mid = (left + right) / 2; db d1 = Merge(arr, left, mid), d2 = Merge(arr, mid, right); d = min(d1, d2); int temp[maxn], k = 0;//建立临时数组用来存储第三个集合的点的下标 for (int i = left; i <= right; i++) if (fabs(arr[mid].x - arr[i].x) <= d) temp[k++] = i; sort(temp, temp + k, cmp2); int pa = 0, pb = 0; for (int i = 0; i < k; i++) for (int j = i + 1; j < k && arr[temp[i]].y - arr[temp[j]].y < d; j++) { db d3 = distance1(arr[temp[i]], arr[temp[j]]); if (d3 < d) { d = d3; pa = temp[i]; pb = temp[j]; } } if (fzmin > d) { fzmin = d; fpa = pa; fpb = pb; } return d; } void Mergeall(point* arr, int n) { sort(arr, arr + n, cmp); fpa = 0; fpb = 0; fzmin = MAX; db result = Merge(arr, 0, n); cout << "有" << chongfu + 1 << "个距离相等的最小点对,其中一组为:(" << arr[fpa].x << "," << arr[fpa].y << ")与(" << arr[fpb].x << "," << arr[fpb].y << "),距离为" << result << endl; } int main() { clock_t start, end,start2,end2; double total,total2; int n; cin >> n; arr = new point[n]; createrand(arr, n); // for (int i = 0; i < n; i++) // cin >> arr[i].x >> arr[i].y; cout << "构造完毕" << endl; // for (int i = 0; i < n; i++) // cout << arr[i].x << " " << arr[i].y << endl; start = clock(); violent2(arr, n); end = clock(); total = (double)end - (double)start; cout << "蛮力法用时" << total << "ms" << endl; start2 = clock(); Mergeall(arr, n); end2 = clock(); total2 = (double)end2 - (double)start2; cout << "分治法用时" << total2 << "ms" << endl; system("pause"); }
评论
    相关推荐