应某位在国外学习多年的大神要求，翻译斯坦福算法课程第一道算法作业（percolation），原文点这里。

ps.这位大神说每个单词都能看懂，连在一起就看不懂了。大神亲自提出要求，我这个没见过市面的土包子只好硬着头皮翻译了。。。

来都来，点下广告吧

渗透

假设一种由随机分布的绝缘材料和金属材料组成的复合系统：材料中的哪些部分得是金属的才能让这个复合系统成为导体呢？假设一种表面有水（或下面是油）的多空的景观，在什么条件下，水能排到底部（或油能喷到表面）？科学家抽象出了一个被称为渗透的过程来模拟上面描述的这类情况。

模型

我们使用n×n的网格模拟渗流系统，网格中的每一个位都是两种状态中的一种，或是开放的，或是关闭的。一个完整位得是一个开放位，并且能够通过一系列相邻（上下左右）的开放位连通到最上面一行的某个开放位。当在最下面一行存在一个完整位时，我们说这个系统是可渗透的。换句话说，如果我们填充所有连通顶行的开放位，并且这个过程能填充位于最下面一行的开放位，那么这个系统渗透。（在绝缘体/金属复合材料的例子中，开放位对应于金属材料的部分，复合材料导电（渗透）意味着它有一条从上到下连通的金属路径。在有孔介质的例子中，开放为对应空的空间，水能通过这些空间流动，介质渗流（渗透）意味着水能顺着这些空的空间从顶部流动到底部。）

模型

问题

在一个有名的科学问题中，科学家对下面的问题超感兴趣：如果一个系统中的位相互独立地以几率P（关闭状态的几率就是1-P）被设为开放状态，整个系统渗透的几率是多少呢。当P=0，这个系统完全不渗透，当P=1，这个系统肯定渗透。下面两张图给出了P和系统渗透几率的关系，横坐标表示P，纵坐标表示系统渗透的几率（上图是20×20的网格系统，下图是100×100的网格系统）。

estimate thread

当网格的基数n足够大，就会有一个阈值P*，当P<P*时，一个随机的n×n系统几乎总是不能渗透，当P>P*时，一个随机的n×n系统几乎总是能渗透。到现在，还没能从数学的角度算出阈值P。你的任务就是写一个程序来估算出P``。

渗透类

要模拟一个渗透系统，需要写一个包含下面接口的渗透类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Percolation {

    // creates n-by-n grid, with all sites initially blocked
    public Percolation(int n)

    // opens the site (row, col) if it is not open already
    public void open(int row, int col)

    // is the site (row, col) open?
    public boolean isOpen(int row, int col)

    // is the site (row, col) full?
    public boolean isFull(int row, int col)

    // returns the number of open sites
    public int numberOfOpenSites()

    // does the system percolate?
    public boolean percolates()

    // test client (optional)
    public static void main(String[] args)
}

注意：

  1. 边界情况：通常来说，行和列的索引是介于1和n之间的整数比如（1,1）表示网格的左上角位。任何传入open()，isOpen()， isFull()的参数如果超出的了刚才描述的这个位，都要抛出java.lang.IllegalArgumentException异常。
    如果n≤0，构造函数应抛出java.lang.IllegalArgumentException。

  2. 性能要求：构造函数初始化花费的时间要正比于n2；所有的方法都应该采用常量时间加上对union-find方法union()，find()，connected(),count()的常数次数的调用。

Monte Carlo 模拟

要估计渗透阈值，考虑下面的计算试验：

  1. 初始化所有的位为关闭状态

  2. 重复下面的过程，直至系统渗透

    • 在所有为关闭状态的位中随机选择一个位
    • 修改这个位为开放状态
  3. 当系统渗透时，开放状态的位的比例就能提供一个对渗透阈值的估测

比如，根据下面的快照，在一个20×20的网格里打开位，那么我们对逾渗阈值的估计值为204/400 = 0.51，因为系统在第204个站点打开时渗透。

experiment

重复上面这个计算试验T次取平均值，我们获得的渗透阈值会更精确。xt表示在第t次试验中开放位的比例。样本平均值

stats1

假设T足够大（比如至少30），下面的公式提供了渗透阈值95%的置信区间。

stats2

为了实现一系列的计算试验，创建一个带有如下接口的渗透统计类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class PercolationStats {

    // perform independent trials on an n-by-n grid
    public PercolationStats(int n, int trials)

    // sample mean of percolation threshold
    public double mean()

    // sample standard deviation of percolation threshold
    public double stddev()

    // low endpoint of 95% confidence interval
    public double confidenceLo()

    // high endpoint of 95% confidence interval
    public double confidenceHi()

   // test client (see below)
   public static void main(String[] args)

}

注意：如果n或者trials<=0，构造函数要抛出java.lang.IllegalArgumentException异常。

另外，这个类中要有一个main()函数，这个函数接受两个来自命令行的采纳数n和T，这个函数用来实现在n×n的网格中执行T次上面描述的计算试验，并输出阈值的样本平均值，标准差以及95%的置信区间。使用StdRandom生成随机数，用StdStats计算样本的平均值和标准差。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
~/Desktop/percolation> java-algs4 PercolationStats 200 100
mean                    = 0.5929934999999997
stddev                  = 0.00876990421552567
95% confidence interval = [0.5912745987737567, 0.5947124012262428]

~/Desktop/percolation> java-algs4 PercolationStats 200 100
mean                    = 0.592877
stddev                  = 0.009990523717073799
95% confidence interval = [0.5909188573514536, 0.5948351426485464]

~/Desktop/percolation> java-algs4 PercolationStats 2 10000
mean                    = 0.666925
stddev                  = 0.11776536521033558
95% confidence interval = [0.6646167988418774, 0.6692332011581226]

~/Desktop/percolation> java-algs4 PercolationStats 2 100000
mean                    = 0.6669475
stddev                  = 0.11775205263262094
95% confidence interval = [0.666217665216461, 0.6676773347835391]

分析运行时间和内存使用情况（可选不参与打分）

使用QuickFindUF中的quick find算法来操控渗透类型。

  • 使用Stopwatch测量PercolationStats类型对于n和T各种值的总运行时间。n加倍如何影响总运行时间？T加倍如何影响总运行时间？给出在你的计算机上总运行时间和n以及T的关系（using tilde notation（这不知道是个啥））（以秒位单位）。

  • 使用讲座中提到的64位内存成本模型，给出Percolation对象用于模拟n×n渗透系统所使用的总内存量（using tilde notation）。计算包括union-find数据结构占用内存在内的所有内存使用量。

现在使用WeightedQuickUnionUF中的weighted quick union算法来执行Percolation类回答上篇中提到的问题。

网上提交

提交且仅提交一个包含Percolation.java（使用WeightedQuickUnionUF中的weighted quick-union算法）和PercolationStats.java的.zip压缩包。我们提供algs4.jar。你的提交中不能使用下面给出的函数以外的库函数，可用函数包括：StdIn，StdOut，StdRandom，StdStats，WeightedQuickUnionUF以及java.lang。