https://github.com/hym105289/Percolation
1. 基本介紹
1.作業(yè)地址：http://coursera.cs.princeton.edu/algs4/assignments/percolation.html
2.模型介紹
滲透模型
①有一個N-by-N矩陣，如上圖，每個小格子代表一個site
②當(dāng)site為black時說明當(dāng)前site為blocked(關(guān)閉的)
③非黑色為open
④當(dāng)一個site為open且他和其他相鄰的site連接并且可以連接到矩陣頂部我們稱這個site為full
⑤如果矩陣最底部有site可以連接到矩陣頂部，我們稱這個矩陣為滲透的
3.作業(yè)要求
每個site以概率p為open，1-p的概率阻塞，計算當(dāng)概率多少時系統(tǒng)是滲透的？
左n=20,右n=100
4.基本思路
假設(shè)要測試20*20的系統(tǒng)以概率多少能滲透，比如每次隨機(jī)地選擇一個site設(shè)置成open，當(dāng)系統(tǒng)滲透時有204個site是open的，那么p=204/400=0.51.我們需要做的就是反復(fù)試驗計算p的值。
2. 判斷系統(tǒng)是否是滲透？
1.數(shù)據(jù)結(jié)構(gòu)
public class Percolation {
private WeightedQuickUnionUF grid;//保存連通的信息
private boolean[] state;//保存每個site是否open
private final int n;
public Percolation(int n) // create n-by-n grid, with all sites blocked
public void open(int row, int col) // open site (row, col) if it is not open already
public boolean isOpen(int row, int col) // is site (row, col) open?
public boolean isFull(int row, int col) // is site (row, col) full?
public int numberOfOpenSites() // number of open sites
public boolean percolates() // does the system percolate?
public static void main(String[] args) // test client (optional)
}
2.如何進(jìn)行Open操作
①[row,col]當(dāng)前的state為true，則已經(jīng)open了則直接返回
②[row,col]當(dāng)前的state為false，先將state設(shè)置為true，然后判斷相鄰的上下左右四個點是否是open的，如果是open的就將其進(jìn)行連接。注意：每次都要檢測row和col的合法性質(zhì)，下標(biāo)從1開始。
2.如何進(jìn)行isFull操作
①首先判斷[row,col]isOpen，如果false直接返回false；
②for 第一行的第一列 to 第一行的最后一列：先判斷是否isOpen，如果false，直接返回false;如果是open的那么就繼續(xù)判斷[row,col]和該點是不是connected，如果是則返回true，否則返回false；
3.反復(fù)進(jìn)行實驗，計算概率p
①首先初始化一個N-by-N矩陣，全部為blocked。
②重復(fù)以下動作直到這個矩陣滲透為止：從blocked狀態(tài)的sites中隨機(jī)選擇一個site將其open，直到當(dāng)前模型滲透為止。
③然后計算open狀態(tài)的sites的個數(shù)設(shè)為number，利用number/(N*N)計算出滲透率。
假設(shè)進(jìn)行T次實驗，每次求得閾值為x，則有：
利用標(biāo)準(zhǔn)差和平均值思想找出置信率為95%的閥值：
public class PercolationStats {
private final double[] threshold;
private double x;
private double s;
public PercolationStats(int n, int trials) // perform trials 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)
}
總結(jié)
1.要注意row和col的取值范圍都是1-n，并不是我們通常的從0開始索引。
2.一定要記得判斷row和col的合法性質(zhì)
3.StdRandom.uniform(lo，hi)產(chǎn)生的是從lo到hi-1的隨機(jī)數(shù)
4.代碼：
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;
public class Percolation {
private WeightedQuickUnionUF grid;
private boolean[] state;
private final int n;
public Percolation(int n) {
if (n <= 0) {
throw new IllegalArgumentException();
} else {
this.n = n;
int size = this.n * this.n + 1;
grid = new WeightedQuickUnionUF(size);
state = new boolean[size];
for (int i = 1; i < size; i++) {
state[i] = false;
}
}
}
private boolean isInGrid(int i, int j) {
if ((i < 1 || i > n) || (j < 1 || j > n))
return false;
else
return true;
}
public void open(int row, int col) {
if (!isInGrid(row, col)) {
throw new IllegalArgumentException();
}
if (isOpen(row, col))
return;
int p = (row - 1) * this.n + col;
state[p] = true;
int up = p - this.n;
if (isInGrid(row - 1, col) && state[up]) {
grid.union(p, up);
}
int left = p - 1;
if (isInGrid(row, col - 1) && state[left]) {
grid.union(p, left);
}
int right = p + 1;
if (isInGrid(row, col + 1) && state[right]) {
grid.union(p, right);
}
int bottom = p + this.n;
if (isInGrid(row + 1, col) && state[bottom]) {
grid.union(p, bottom);
}
}
public boolean isOpen(int row, int col) {
if (row < 1 || row > this.n || col < 1 || col > this.n) {
throw new IllegalArgumentException();
}
int index = (row - 1) * this.n + col;
return state[index];
}
public boolean isFull(int row, int col) {
if (row < 1 || row > this.n || col < 1 || col > this.n) {
throw new IllegalArgumentException();
}
int p = (row - 1) * this.n + col;
for (int i = 1; i < this.n + 1; i++) {
// first must consider the row,col is open
if (isOpen(1, i) && isOpen(row, col) && grid.connected(p, i))
return true;
}
return false;
}
public int numberOfOpenSites() {
int num = 0;
int size = this.n * this.n + 1;
for (int i = 0; i < size; i++) {
if (state[i])
num++;
}
return num;
}
public boolean percolates() {
int row = this.n;
for (int col = 1; col < this.n + 1; col++) {
if (isFull(row, col))
return true;
}
return false;
}
public static void main(String[] args) {
int[] test = new In(args[0]).readAllInts();
Percolation percolation = new Percolation(test[0]);
for (int i = 1; i < test.length - 2; i += 2) {
percolation.open(test[i], test[i + 1]);
System.out.println(
test[i] + "," + test[i + 1] + " isopen:" + percolation.isOpen(test[i], test[i + 1]));
System.out.println(
test[i] + "," + test[i + 1] + " isfull:" + percolation.isFull(test[i], test[i + 1]));
System.out.println(test[i] + "," + test[i + 1] + " percolation:" + percolation.percolates());
}
}
}
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;
public class PercolationStats {
private final double[] threshold;
private double x;
private double s;
public PercolationStats(int n, int trials) {
if (n <= 0 || trials <= 0) {
throw new IllegalArgumentException();
}
threshold = new double[trials];
for (int i = 0; i < trials; i++) {
Percolation p = new Percolation(n);
while (!p.percolates()) {
int row = StdRandom.uniform(1, n + 1);
int col = StdRandom.uniform(1, n + 1);
if (!p.isOpen(row, col)) {
p.open(row, col);
}
}
threshold[i] = (double) p.numberOfOpenSites() / n / n;
}
}
public double mean() {
x=StdStats.mean(threshold);
return x;
}
public double stddev() {
s=StdStats.stddev(threshold);
return s;
}
public double confidenceLo() {
double low = x - 1.96 * s / (Math.sqrt((double) threshold.length));
return low;
}
public double confidenceHi() {
double hi = x + 1.96 * s / (Math.sqrt((double) threshold.length));
return hi;
}
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
int trials = Integer.parseInt(args[1]);
PercolationStats stats = new PercolationStats(n, trials);
double x = stats.mean();
double s = stats.stddev();
double low = stats.confidenceLo();
double hi = stats.confidenceHi();
System.out.printf("mean=%f\n", x);
System.out.printf("stddev=%f\n", s);
System.out.printf("%f %f\n", low, hi);
}
}
