把格子纸里的格子随机染黑白两色,平均每片色斑有多少格子?

前因

这是在知乎上回答的一个问题,原答案在此https://www.zhihu.com/question/33596209/answer/57056534

问题

把格子纸里的格子随机染黑白两色,平均每片色斑有多少格子?
无限大的格子纸(4连通),每一块等概率染黑或者白
平均连通的每一块有多大?

答案

假定有限空间,随机一个 NN的数组,每个数值为0或1,算出有多少个封闭块,就可以得出平均联通区域大小了。
结果是这样的:
001101001110101100111010101100
111111110010010011000000111110
100100111010100110100010111100
001011001101111011010100100000
100000100110110000011110010101
000110000100111010000010011010
101001011000101110000110011101
111010010001110011010010011000
001110001110010011110100100110
000111111011101001001110100111
011001011011101100111001011100
000101001010000010010011011100
110101111101011010111100011000
111011100010001010111110111111
100010111010100101010101111000
000100011101111111000100001111
101011001111101110101001000111
001111100111110001100111100000
000010111001010011001010011010
101011000000001101110010110100
011110110100101001100101110100
011000001001011011101000111110
110110101001001010000111000101
001100100000010000011000111100
010001110011001000011001101101
111100100010000001111011011101
100111111100010111010111110011
011100111101011000011111000001
011101111110010101111101011011
100101111110100001000110100100
30
30区域 ;144个封闭块;平均每块大小6.25
下面就不打印数组了,有兴趣可以自己试试,我的代码贴在下面。
100100区域 ;1466个封闭块;平均每块大小6.8212824010914055
500
500区域 ;33344个封闭块;平均每块大小7.497600767754319
10001000区域 ;132331个封闭块;平均每块大小7.55680830644369
5000
5000区域 ;3291136个封闭块;平均每块大小7.596161325451151
1000010000区域 ;13161184个封闭块;平均每块大小7.598100596420505
15000
15000区域 ;29618321个封闭块;平均每块大小7.596649384683217
再大就成这样了,定义的数组太大,内存溢出了
Exception in thread “main” java.lang.OutOfMemoryError: Java heap space
at Test.(Test.java:7)
at Test.main(Test.java:10)

源码

非常简单的代码相信会点的人都能看懂,写得很水,欢迎指教

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 	
import java.util.Random;

public class Test {

public static final int NUM = 10000;

int[][] num = new int[NUM][NUM];

public static void main(String[] args) {
Test test = new Test();
test.initNum();
test.scanAll();
}
void initNum() {
Random random = new Random();
for (int i = 0; i < NUM; i++) {

for (int j = 0; j < NUM; j++) {
num[i][j] = random.nextInt(2);
System.out.print(num[i][j]);
}
System.out.println();
}
}
void scanAll() {
int areaCount = 0;
for (int i = 0; i < NUM; i++) {
for (int j = 0; j < NUM; j++) {
if (num[i][j] < 2) {
int areaNum = scanOne(i, j, num[i][j]);
// System.out.println(i + ":" + j + ":" + areaNum);
areaCount++;
}

}
}
System.out.println(NUM+"*"+NUM+"区域 ;"+areaCount + "个封闭块;平均每块大小" + (double) NUM * NUM / areaCount);
}

private int scanOne(int i, int j, int value) {
if (i < NUM && j < NUM && i >= 0 && j >= 0 && num[i][j] == value) {
num[i][j] = 2;
return 1 + scanOne(i + 1, j, value) + scanOne(i, j + 1, value)
+ scanOne(i - 1, j, value) + scanOne(i, j - 1, value);
}
return 0;
}

}