正常的矩形

在矩形中(均匀地)随机选择两个点,可以算出两点间距离的期望值。

例如,在单位正方形中任意两点间距离的期望约为 0.521405,而在 2x3 的矩形中任意两点间距离的期望约为 1.317067。

使用以下 C 语言程序计算:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double sq(double x) { return x*x; }

int main(int argc, char* argv[])
{
  int wide = (argc > 1) ? atoi(argv[1]) : 1;
  int high = (argc > 2) ? atoi(argv[2]) : 1;
  int gap  = (argc > 3) ? atoi(argv[3]) : 7;
  long n = 1 << gap, cnt = 0;
  double step = 1.0 / n, v = 0;
  printf("%dx%d:%d %ld %.15lf\n", wide, high, gap, n, step);
  for (double x1 = 0; x1 < wide; x1 += step)
    for (double y1 = 0; y1 < high; y1 += step)
      for (double x2 = 0; x2 < wide; x2 += step)
        for (double y2 = 0; y2 < high; y2 += step, cnt++)
          v += sqrt(sq(x2 - x1) + sq(y2 - y1));
  printf("Count: %ld\n", cnt);
  printf("Dist.: %.7lf\n", v / cnt);
}

编译和运行:

$ clang -O 547.c -lm
$ time ./a.out 1 1 8
1x1:8 256 0.003906250000000
Count: 4294967296
Dist.: 0.5214016

real 0m34.895s
user 0m34.860s
sys 0m0.000s

$
$ time ./a.out 2 3 8
2x3:8 256 0.003906250000000
Count: 154618822656
Dist.: 1.3170659

real 20m53.643s
user 20m52.940s
sys 0m0.077s

有洞的矩形

以下 C 语言程序可以处理内部有洞的矩形:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

static long R;
double sq(double x) { return x*x; }
int hole(int x, int y, int u1, int v1, int u2, int v2)
{ return x >= u1 && y >= v1 && x < u2 && y < v2; }

double s(double z, int w, int h, int u1, int v1, int u2, int v2)
{
  double v = 0; long cnt = 0;
  for (double x1 = 0; x1 < w; x1 += z)
    for (double y1 = 0; y1 < h; y1 += z) {
      if (hole(x1, y1, u1, v1, u2, v2)) continue;
      for (double x2 = 0; x2 < w; x2 += z)
        for (double y2 = 0; y2 < h; y2 += z) {
          if (hole(x2, y2, u1, v1, u2, v2)) continue;
          cnt++, v += sqrt(sq(x2 - x1) + sq(y2 - y1));
        }
    }
  double a = v / cnt;
  printf("(%d,%d - %d,%d) %ld %.5lf\n", u1,v1,u2,v2,cnt/R,a);
  fflush(stdout); return a;
}

int main(int argc, char* argv[])
{
  int wide = (argc > 1) ? atoi(argv[1]) : 3;
  int high = (argc > 2) ? atoi(argv[2]) : 3;
  int e    = (argc > 3) ? atoi(argv[3]) : 5;
  long n = 1L << e; R = 1L << (e << 2);
  double step = 1.0 / n, v = 0;
  printf("%dx%d %.15lf\n", wide, high, step); fflush(stdout);
  if (wide < 3 || high < 3) {
    wide = high = 5;
    printf("%dx%d %.15lf\n", wide, high, step); fflush(stdout);
    v += s(step, wide, high, 3, 1, 4, 2);
    v += s(step, wide, high, 1, 1, 2, 2);
    v += s(step, wide, high, 2, 1, 3, 2);
    v += s(step, wide, high, 2, 2, 3, 3);
    v += s(step, wide, high, 1, 1, 2, 4);
    v += s(step, wide, high, 1, 1, 4, 2);
    v += s(step, wide, high, 1, 2, 4, 3);
  } else
    for (int x1 = 1; x1 < wide - 1; x1++)
      for (int y1 = 1; y1 < high - 1; y1++)
        for (int x2 = x1 + 1; x2 < wide; x2++)
          for (int y2 = y1 + 1; y2 < high; y2++)
            v += s(step, wide, high, x1, y1, x2, y2);
  printf("%.5lf\n", v); fflush(stdout);
}

编译和运行:

$ clang -O 547a.c -lm
$ ./a.out 2
2x3 0.031250000000000
5x5 0.031250000000000
(3,1 - 4,2) 576 2.63127
(1,1 - 2,2) 576 2.63127
(2,1 - 3,2) 576 2.64593
(2,2 - 3,3) 576 2.66106
(1,1 - 2,4) 484 2.69627
(1,1 - 4,2) 484 2.69627
(1,2 - 4,3) 484 2.74916
18.71125

前四个洞的形状都是相同的,只是位置不同。后三个洞也是如此。

其他示例:

$ ./a.out 4 4 7 | gnomon -i
 497.1861s | 4x4 0.007812500000000
 440.8185s | (1,1 - 2,2) 225 2.13702
 440.9056s | (1,1 - 2,3) 196 2.19346
 338.0687s | (1,1 - 3,2) 196 2.19346
 497.1671s | (1,1 - 3,3) 144 2.33447
 440.8064s | (1,2 - 2,3) 225 2.13702
 497.3825s | (1,2 - 3,3) 196 2.19346
 440.8649s | (2,1 - 3,2) 225 2.13702
 497.3056s | (2,1 - 3,3) 196 2.19346
   0.0001s | (2,2 - 3,3) 225 2.13702
   0.0036s | 19.65638
           |
     Total | 4090.5100s

这表明 S(4) ≈ 19.6564。