来自于《算法：C 语言实现》
在边长为 1 的正方形中随机产生 N 个点，计算有多少个点对之间的距离小于 d。
一种直观的解法就是对每个点，检查其余其他点的距离。
另一种改进的方法是，考虑到距离小于 d 才符合要求，对于许多一开始就能知道距离大于 d 的点对没有必要检查。这里借助一个二维的链表数组进行操作。
由 d 得到 G = 1 / d，把正方形划分成一个 (G + 2) * (G + 2) 的格子。对于要检查的点，只需要检查其所在格子以及周围的 8 个格子中的其他点与它的距离。这样效率得到很大的提升。
解法一：
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <math.h>
4 #include <time.h>
5
6 typedef struct
7 {
8 float x;
9 float y;
10 } point;
11
12 float distance(point a, point b)
13 {
14 float dx = a.x - b.x, dy = a.y - b.y;
15 return sqrt(dx * dx + dy * dy);
16 }
17
18 float randFloat()
19 {
20 return 1.0 * rand() / RAND_MAX;
21 }
22
23 int main()
24 {
25 float d = 0.1;
26 int i, j, cnt = 0, N = 100;
27
28 point* a = (point*)malloc(N * sizeof (*a));
29 srand(time(0));
30 for (i = 0; i < N; ++i)
31 {
32 a[i].x = randFloat();
33 a[i].y = randFloat();
34 }
35 for (i = 0; i < N; ++i)
36 {
37 for (j = i + 1; j < N; ++j)
38 {
39 if (distance(a[i], a[j]) < d)
40 {
41 ++cnt;
42 }
43 }
44 }
45 printf("%d edges shorter than %f\n", cnt, d);
46 }
改进的解法：
1 // 二维链表数组
2
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <math.h>
6 #include <time.h>
7
8 typedef struct
9 {
10 float x;
11 float y;
12 } point;
13
14 typedef struct node* link;
15 struct node
16 {
17 point p;
18 link next;
19 };
20
21 link** grid;
22 int G;
23 float d;
24 int cnt;
25
26 float distance(point a, point b)
27 {
28 float dx = a.x - b.x, dy = a.y - b.y;
29 return sqrt(dx * dx + dy * dy);
30 }
31
32 float randFloat()
33 {
34 return 1.0 * rand() / RAND_MAX;
35 }
36
37 void gridinsert(float x, float y)
38 {
39 int i, j;
40 link s;
41 int X = x * G + 1;
42 int Y = y * G + 1;
43 link t = (link)malloc(sizeof (*t));
44 t->p.x = x;
45 t->p.y = y;
46
47 for (i = X - 1; i <= X + 1; ++i)
48 {
49 for (j = Y - 1; j <= Y + 1; ++j)
50 {
51 for (s = grid[i][j]; s != 0; s = s->next)
52 {
53 if (distance(s->p, t->p) < d)
54 {
55 ++cnt;
56 }
57 }
58 }
59 }
60 t->next = grid[X][Y];
61 grid[X][Y] = t;
62 }
63
64 int** malloc2d(int r, int c)
65 {
66 int i;
67 int **t = (int**)malloc(r * sizeof (int*));
68 for (i = 0; i < r; ++i)
69 {
70 t[i] = (int*)malloc(c * sizeof (int));
71 }
72 return t;
73 }
74
75 int main()
76 {
77 int i, j, N = 100;
78 d = 0.1;
79 G = 1 / d;
80
81 grid = (link**)malloc2d(G + 2, G + 2);
82
83 for (i = 0; i < G + 2; ++i)
84 {
85 for (j = 0; j < G + 2; ++j)
86 {
87 grid[i][j] = 0;
88 }
89 }
90
91 srand(time(0));
92 for (i = 0; i < N; ++i)
93 {
94 gridinsert(randFloat(), randFloat());
95 }
96
97 printf("%d edges shorter than %f\n", cnt, d);
98 return 0;
99 }
posted on 2011-05-16 14:12
unixfy 阅读(118)
评论(0) 编辑 收藏 引用