distp.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <math.h>
   4
   5
   6 struct rec {
   7         int d;
   8         int x;
   9 };
  10
  11
  12 static int comp(struct rec *r1, struct rec *r2)
  13 {
  14         return r1->x - r2->x;
  15 }
  16
  17 void shuffle(struct rec *d, int n)
  18 {
  19         int i;
  20
  21         for (i=0;i<n;i++)
  22                 d[i].x = random();
  23
  24         qsort(d, n, sizeof(*d), comp);
  25 }
  26
  27 int count(struct rec *d, int n, int x)
  28 {
  29         int i, ret=0;
  30
  31         for (i=0;i<n;i++)
  32                 if (d[i].d == x) ret++;
  33         return ret;
  34 }
  35
  36
  37 static double avg(struct rec *d, int n, int loops)
  38 {
  39         int sum=0;
  40         int i;
  41
  42         for (i=0;i<loops;i++) {
  43                 shuffle(d, 2*n);
  44                 sum += abs(n/2 - count(d, n, 1));
  45         }
  46         return sum/(1.0*i);
  47 }
  48
  49 static double Pn(int n)
  50 {
  51         return 0.20 * sqrt(1.*n);
  52 }
  53
  54 static int log2(int n)
  55 {
  56         int i;
  57         for (i=1;(1<<i)<n;i++) ;
  58         return i;
  59 }
  60
  61 int main(int argc, char *argv[])
  62 {
  63         struct rec *d;
  64         int i;
  65         int N = atoi(argv[1]);
  66         int P = atoi(argv[2]);
  67         double r=0;
  68         double k=0.4;
  69
  70         r = log2(P/4)*2*(P-3)*k*sqrt(N/P);
  71
  72         printf("P=%d N=%d Pn=%g\n", P, N/P, r);
  73 }
  74