设计求解平面最邻近点对算法 1)数据没有事先预排序,设计算法O(n(logn)2)。 2)数据事先预排序,设计算法O(nlogn) C·语言代码
时间: 2024-02-06 13:08:46 浏览: 19
1)数据没有事先预排序,设计算法O(n(logn)2)。
算法步骤:
1. 将所有点按照x坐标从小到大排序。
2. 用一个数组存储当前已知的最近邻点对,初始化为无穷大。
3. 对于每个点i,从i+1开始遍历所有点j,如果j的x坐标和i的x坐标之差大于当前最短距离,则跳过j。
4. 对于每个点i,从i+1开始遍历所有点j,如果j的y坐标和i的y坐标之差大于当前最短距离,则跳过j。
5. 对于每个点i,从i+1开始遍历所有点j,计算点i和点j之间的距离,如果比当前最短距离小,则更新最近邻点对数组。
6. 返回最近邻点对数组。
C语言代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct point {
double x;
double y;
};
int cmp(const void* a, const void* b) {
struct point* pa = (struct point*)a;
struct point* pb = (struct point*)b;
if (pa->x < pb->x) return -1;
if (pa->x > pb->x) return 1;
return 0;
}
double dist(struct point a, struct point b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
void closest_pair(struct point* p, int n, struct point* best_pair) {
int i, j, k;
double d;
qsort(p, n, sizeof(struct point), cmp);
d = dist(p[0], p[1]);
best_pair[0] = p[0];
best_pair[1] = p[1];
for (i = 0; i < n; i++) {
for (j = i + 1; j < n && p[j].x - p[i].x < d; j++) {
double d_ij = dist(p[i], p[j]);
if (d_ij < d) {
d = d_ij;
best_pair[0] = p[i];
best_pair[1] = p[j];
}
}
}
}
int main() {
struct point p[] = {{1, 2}, {3, 4}, {5, 6}, {7, 8}};
int n = sizeof(p) / sizeof(p[0]);
struct point best_pair[2];
closest_pair(p, n, best_pair);
printf("(%g,%g) (%g,%g)\n", best_pair[0].x, best_pair[0].y, best_pair[1].x, best_pair[1].y);
return 0;
}
```
2)数据事先预排序,设计算法O(nlogn)。
算法步骤:
1. 用一个数组存储当前已知的最近邻点对,初始化为无穷大。
2. 对于每个点i,从i+1开始遍历所有点j,计算点i和点j之间的距离,如果比当前最短距离小,则更新最近邻点对数组。
3. 返回最近邻点对数组。
C语言代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct point {
double x;
double y;
};
double dist(struct point a, struct point b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
void closest_pair(struct point* p, int n, struct point* best_pair) {
int i, j, k;
double d;
d = INFINITY;
for (i = 0; i < n; i++) {
for (j = i + 1; j < n && p[j].y - p[i].y < d; j++) {
double d_ij = dist(p[i], p[j]);
if (d_ij < d) {
d = d_ij;
best_pair[0] = p[i];
best_pair[1] = p[j];
}
}
}
}
int main() {
struct point p[] = {{1, 2}, {3, 4}, {5, 6}, {7, 8}};
int n = sizeof(p) / sizeof(p[0]);
struct point best_pair[2];
closest_pair(p, n, best_pair);
printf("(%g,%g) (%g,%g)\n", best_pair[0].x, best_pair[0].y, best_pair[1].x, best_pair[1].y);
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)