• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 183,  comments - 10,  trackbacks - 0

            來自于《算法: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 **= (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 閱讀(127) 評論(0)  編輯 收藏 引用
            久久久久久一区国产精品| 亚洲va久久久噜噜噜久久| 国产成人久久精品二区三区| 久久99国产精一区二区三区| 99久久精品无码一区二区毛片 | 99久久精品九九亚洲精品| 99久久精品国产一区二区三区| 亚洲国产综合久久天堂| 久久精品www人人爽人人| 久久精品无码一区二区三区免费| 亚洲国产精品成人AV无码久久综合影院 | 香蕉久久av一区二区三区| 久久91精品久久91综合| 伊人伊成久久人综合网777| 久久超乳爆乳中文字幕| 日韩久久无码免费毛片软件| 99精品国产99久久久久久97 | 久久亚洲精品无码AV红樱桃| 国内精品久久久久久麻豆| 色综合久久久久综合体桃花网| 久久婷婷五月综合色99啪ak| 少妇高潮惨叫久久久久久| 亚洲国产一成久久精品国产成人综合| 国产美女久久精品香蕉69| 精品伊人久久大线蕉色首页| 久久精品综合一区二区三区| 精品久久久噜噜噜久久久| 亚洲精品乱码久久久久久按摩| 久久久久久亚洲精品无码| 伊人久久综在合线亚洲2019| 99久久免费国产特黄| 婷婷伊人久久大香线蕉AV| 亚洲午夜久久久久久久久久| 亚洲国产成人久久综合一区77| 亚洲国产精品久久久久婷婷软件| 久久ww精品w免费人成| 婷婷五月深深久久精品| 欧美黑人又粗又大久久久| 亚洲人成伊人成综合网久久久| 日韩影院久久| 久久亚洲精品无码aⅴ大香|