总结
视频讲述了并查集算法的细节,作业是该算法的实际应用
下载algs4.jar,并添加到CLASSPATH中
使用algs4.jar中的工具:求均值,求标准差,输入输出
需要传入外部参数的方法都得进行参数检测,否则扣分
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条有进一步的说明之所以采用如上的转换规则:
其一,方便判断某个点的上下左右邻居时不会有数组越界异常,对于四周的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)要区分好block,open,full这三个状态,block对应false,open对应true,full表示某个site和上虚拟点相连
为方便判断系统为渗透状态,在n*n格子的上下分别加两个虚拟的点,
代码中:索引为0的代表上虚拟点,索引为(n+1)*(n+1)代表下虚拟点(找两个没用的索引值即可)
这样做会导致backwash问题(即回流问题),因为在open方法中第n行的所有site都和下虚拟点union过了-
解决backwash问题,需要再创建一个并查集对象,即代码中的uf2,该对象不将最后一行和下虚拟点相连,在isFull方法中使用uf2的connected方法就不会导致backwash问题了
3*3.png
5*5.png
代码
Percalation.java
/**
* @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
/**
* @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());
}
}
