[TOC]

# model & problem

(原文描述太啰嗦了)
A system using an N-by-N grid of sites.
→ Each site is either open or blocked.
→ A full site is an open site that can be connected to an open site in the top row via a chain of neighboring open sites. (这个full的定义有玄机 而且导致后面写程序时有个问题, 看论坛想了半天才想出来, 见后文.)
→ We say the system percolates if there is a path of connected open sites form the top row to the bottom row.

⇒ pb: if sites are independently set to be open with probability p, what is the probability that the system percolates?

→ When N is sufficiently large, there is a threshold value **p such that when p < p a random N-by-N grid almost never percolates, and when p > p, a random N-by-N grid almost always percolates.
→ No mathematical solution for determining the percolation threshold p
has yet been derived.
⇒ Your task is to *write a computer program to estimate p
.

# Method

• API:

```public class Percolation {
public Percolation(int N)               // create N-by-N grid, with all sites blocked
public void open(int i, int j)          // open site (row i, column j) if it is not open already
public boolean isOpen(int i, int j)     // is site (row i, column j) open?
public boolean isFull(int i, int j)     // is site (row i, column j) full?
public boolean percolates()             // does the system percolate?
public static void main(String[] args   // test client (optional)
}
```
• Corner cases: the row and column indices i and j are integers between 1 and N. 1≤i,j≤N

if i/j out of range: `java.lang.IndexOutOfBoundsException` if N<=0 in constructor: `java.lang.IllegalArgumentException`

• Performance requirements: N2 for constructor, const for other operations

• Monte Carlo simulation

• all sites init to be closed

→ randomly choose a blocked site (i,j) and open it → repeat until percolates ⇒ the fraction of opened sites is an estimation of p*

• ex. 20*20 grid, when percolated:

⇒ estimated p* = 204/400=0.51

• repeat the estimation for T times, get T estimations

→ get mean and std:

→ 95% 置信区间:

• create API for this simulation:

```public class PercolationStats {
public PercolationStats(int N, int T)     // perform T independent experiments on an N-by-N grid
public double mean()                      // sample mean of percolation threshold
public double stddev()                    // sample standard deviation of percolation threshold
public double confidenceLo()              // low  endpoint of 95% confidence interval
public double confidenceHi()              // high endpoint of 95% confidence interval
public static void main(String[] args)    // test client (described below)
}
```

-if N ≤ 0 or T ≤ 0: `java.lang.IllegalArgumentException`
-`main()` : takes two command-line arguments N and T
⇒ performs T independent computational experiments on an N-by-N grid, and prints out the mean, standard deviation, and the 95% confidence interval for p*.
(Use standard random from our standard libraries to generate random numbers; use standard statistics to compute the sample mean and standard deviation.
Here is the algo API: http://algs4.cs.princeton.edu/code/index.php)

# Code

shuffle, mean, stddev什么的直接用他们的函数库就可以做到.
http://algs4.cs.princeton.edu/code/index.php

### backwash问题

1. UF只建立顶部虚拟节点, 不建立底部虚拟节点.
2. 判断isFull只需要用UF的connected()一下就好了
3. 问题是怎么判断percolation:
a. 建立一个数组 `boolean connectedToBottom[]`, 指示某一点是否和底部相连
b. trick在这里: 不必修改一个联通分支的所有点的`connectedToBottom`的值, 只需要修改联通分支的root(UF的find)即可. 在进行union的时候先查看两个component的root是不是连到底部, 然后有一个连到底部的话, 在union以后把合并后的联通分支的`connectedToBottom`状态改为true即可
c. 然后判断percolate: 先找到顶部虚拟节点锁在component的root, 然后看这个root是否连到底部即可!