普林斯顿大学算法Week1: Percolation 渗透(98分)--总结及代码

总结

视频讲述了并查集算法的细节,作业是该算法的实际应用

  1. 下载algs4.jar,并添加到CLASSPATH中
  2. 使用algs4.jar中的工具:求均值,求标准差,输入输出
  3. 需要传入外部参数的方法都得进行参数检测,否则扣分
  4. UnionFind算法的输入是一维的,Percolation系统是n*n的格子,每个site由坐标对(x,y)表示,
    所以要想描述点与点之间的关系,得先将二维坐标转换成一维的数值,我采用的转换规则是:(x,y)→x*(n+1)+y
    (1,1)到(n,n) 对应n+2到n*(n+2),注意:一维数值并不是连续的
    可以采用其它转换规则,比如易于理解的(x,y)→x*(n+2)+y,第5条有进一步的说明

  5. 之所以采用如上的转换规则:
    其一,方便判断某个点的上下左右邻居时不会有数组越界异常,对于四周的site来说,并不都有四个邻点 (如下图3*3.png,左上角的点1没有上邻居和左邻居,扩充为5*5.png后,点1就有上下左右四个邻居了)
    其二,节省空间,最容易理解的是使用(n+2)*(n+2)长的一维数组(如下图3*3.png和5*5.png),使用(n+2)*(n+1)+1长的也行,因为在转换规则的约束下,所有site的一维表示都是唯一的,并且最大值等于(n+2)*(n+1)

  6. 要区分好block,open,full这三个状态,block对应false,open对应true,full表示某个site和上虚拟点相连
  7. 为方便判断系统为渗透状态,在n*n格子的上下分别加两个虚拟的点,
    代码中:索引为0的代表上虚拟点,索引为(n+1)*(n+1)代表下虚拟点(找两个没用的索引值即可)
    这样做会导致backwash问题(即回流问题),因为在open方法中第n行的所有site都和下虚拟点union过了
  8. 解决backwash问题,需要再创建一个并查集对象,即代码中的uf2,该对象不将最后一行和下虚拟点相连,在isFull方法中使用uf2的connected方法就不会导致backwash问题了

    3*3.png

    3*3.png

    5*5.png

    5*5.png

代码

Percalation.java

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/**
* @author Sasuke
* @date 25/1/2018
*/

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {
// n*n grid
private int n ;
//status of each site
private boolean[] eachStatus ;
//number of open site
private int openNum;
//UF alg with virtual site
private WeightedQuickUnionUF uf1;
//UF alg with only top site due to backwash
private WeightedQuickUnionUF uf2;

// create n-by-n grid, with all sites blocked
public Percolation(int n){
if(n<=0) throw new IllegalArgumentException("illegal value of n!");
this.n = n;
//plus two virtual site
eachStatus = new boolean[(n+1)*(n+2)];

//all sites are blocked
for(int i=0; i< eachStatus.length;i++) eachStatus[i]=false;
// grid with top site and bottom site
uf1 = new WeightedQuickUnionUF((n+1)*(n+2));
// grid with only bottom site
uf2 = new WeightedQuickUnionUF((n+1)*(n+2));
}

//translate 2 dimentional coordinate to 1 dimentional pattern
private int oneDimention(int row, int col){
return row*(n+1)+col;
}
// open site (row, col) if it is not open already
public void open(int row, int col){
if(row<1 || row>n || col<1 || col>n) throw new IllegalArgumentException("illegal row or col!");
if(!isOpen(row,col)) {
eachStatus[oneDimention(row,col)]=true;
openNum++;
int temp1 = oneDimention(row,col);
//if neighbor could be connected?
if(row==1){
uf1.union(0,temp1);
uf2.union(0,temp1);
}
if(row==n) {
uf1.union((n+1)*(n+1),temp1);
}
int[] dx = {1,-1,0,0};
int[] dy = {0,0,1,-1};
for(int i=0; i<4;i++){
int tempX = row+dx[i];
int tempY = col+dy[i];
int temp2 = oneDimention(tempX,tempY);
if (eachStatus[temp2]){
uf1.union(temp1,temp2);
uf2.union(temp1,temp2);
}
}
}
}

//is site (row, col) open?
public boolean isOpen(int row, int col){
if(row<1 || row>n || col<1 || col>n) throw new IllegalArgumentException("illegal row or col!");
return eachStatus[oneDimention(row,col)];
}

//is site (row, col) full?
public boolean isFull(int row, int col){
if(row<1 || row>n || col<1 || col>n) throw new IllegalArgumentException("illegal row or col!");
return uf2.connected(0,oneDimention(row,col));
}

// number of open sites
public int numberOfOpenSites() {
return openNum;
}

// does the system percolate?
public boolean percolates() {
return uf1.connected(0,(n+1)*(n+1));
}

// test client (optional)
public static void main(String[] args) {
Percolation p = new Percolation(3);
p.open(1, 2);
p.open(2, 2);
p.open(3, 2);
StdOut.println(p.isOpen(1,1));
StdOut.println(p.percolates());
}

}

PercolationStats.java

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
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
* @author Sasuke
* @date 25/1/2018
*/

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;

public class PercolationStats {
//trial times
private int trialNum;
//threshold P
private double[] preP;
public PercolationStats(int n,int trialNum) {
if (n<1 || trialNum<1) throw new IllegalArgumentException("Illegal n or trialNum,please check");
this.trialNum = trialNum;
preP = new double[trialNum];
for(int i=0;i<trialNum;i++) {
Percolation p = new Percolation(n);
while(!p.percolates()) {
int row = StdRandom.uniform(n)+1;
int col = StdRandom.uniform(n)+1;
p.open(row,col);
if (p.percolates()) break;
}
preP[i] = (double)p.numberOfOpenSites()/(n*n);
}
}

// mean of p
public double mean() {
return StdStats.mean(preP);
}

// standard deviation
public double stddev() {
return StdStats.stddev(preP);
}

//confidence interval:low
public double confidenceLo() {
return mean()-1.96*stddev()/Math.sqrt(trialNum);
}

//confidence interval:high
public double confidenceHi() {
return mean()+1.96*stddev()/Math.sqrt(trialNum);
}

public static void main(String[] args) {
int n =10,trialNum=1000;
PercolationStats ps = new PercolationStats(n,trialNum);
StdOut.println("grid size :" + n+"*"+n);
StdOut.println("trial times :" + trialNum);
StdOut.println("mean of p :"+ ps.mean());
StdOut.println("standard deviation :"+ps.stddev());
StdOut.println("confidence interval low :"+ps.confidenceLo());
StdOut.println("confidence interval high :"+ps.confidenceHi());
}


}
0%