來自于《算法：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 閱讀(126)
評論(0) 編輯 收藏 引用