Coursera算法Programming Assignment 1: Percolation

代码实现

题目链接：http://coursera.cs.princeton.edu/algs4/assignments/percolation.html

题目中要求编写两个类Percolation和PercolationStats，Percolation类要求能模拟渗透系统，PercolationStats类则用于渗透系统的测试，下面是我的实现。

Percolation类

Percolation类有两点需要注意。第一，为了方便判断系统是否渗透，可在顶底端分别加上一个虚拟方块；第二，打开某个方块时，需要将该方块与周围已打开方块相连。

//Percolation类
package com.percolation;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {
    private int N;
    private int count = 0;
    private int[][] a;
    private int top,bottom; //虚拟方块
    private WeightedQuickUnionUF wq;
    public Percolation(int n) { // create n-by-n grid, with all sites blocked
        if(n <= 0) throw new IllegalArgumentException();
        N = n;top = 0;bottom = N*N+1;
        a = new int[N+1][N+1];
        wq = new WeightedQuickUnionUF(N*N+2);
    }
    public    void open(int row, int col){ // open site (row, col) if it is not open already
        if(row < 1 || row > N || col < 1 || col > N) throw new IllegalArgumentException();
        if(a[row][col] != 0) return;
        a[row][col] = (row-1)*N+col; 
        if(row==1&&a[row][col]!=0)  wq.union(a[row][col], 0);
        if(row==N&&a[row][col]!=0)  wq.union(a[row][col], bottom); //将顶（底）层已打开的方块与顶（底）部虚拟方块相连
        if(col>1&&a[row][col-1]!=0) wq.union(a[row][col-1],a[row][col]);
        if(row>1&&a[row-1][col]!=0) wq.union(a[row-1][col],a[row][col]);
        if(col<N&&a[row][col+1]!=0) wq.union(a[row][col+1],a[row][col]);
        if(row<N&&a[row+1][col]!=0) wq.union(a[row+1][col],a[row][col]); //将已打开方块与四周已打开方块相连
        count++;
    }
    public boolean isOpen(int row, int col){ // is site (row, col) open?
        if(row < 1 || row > N || col < 1 || col > N) throw new IllegalArgumentException();
        return a[row][col] != 0;
    }
    public boolean isFull(int row, int col){ // is site (row, col) full?
        if(row < 1 || row > N || col < 1 || col > N) throw new IllegalArgumentException();
        if(a[row][col] == 0) return false;
        return wq.connected(a[row][col],0); //top=0
    }
    public     int numberOfOpenSites(){ // number of open sites
        return count;
    }
    public boolean percolates(){ // does the system percolate?
        return wq.connected(bottom,top);
    }
    public static void main(String[]  args){ //optional
        Percolation p=new Percolation(5);
        for(int i=0;i<20;i++){
            p.open(StdRandom.uniform(1,6),StdRandom.uniform(1,6));
        }
       if(p.isOpen(5, 5)) System.out.println(p.isFull(5, 5));
       if(p.percolates()) System.out.println("percolates");
       else System.out.println("does not percolate");
       System.out.println(p.numberOfOpenSites());
    }
}

PercolationStats类

PercolationStats类要求对系统进行trials次试验，并格式化输出概率的平均值，标准差及95%的置信区间。

//PercolationStats类
package com.percolation;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;

public class PercolationStats {
	private double[] opensites; //每次试验打开触点的比例
	private int trials;
	private int k ;
	private Percolation p;
	private double meanofopensites;
	private double stddevofopensites;
    public PercolationStats(int n, int trials){ // perform trials independent experiments on an n-by-n grid
    	if(n <= 0 || trials <= 0) throw new IllegalArgumentException();
    	this.trials = trials;
    	opensites = new double[trials];
    	while(k < trials){
    		p = new Percolation(n);
    		while(!p.percolates()){
    			p.open(StdRandom.uniform(1,n+1), StdRandom.uniform(1,n+1));
    		}
    		opensites[k]=1.0*p.numberOfOpenSites()/(n*n);
    		k++;
    		p=null;
    	}
    }
	public double mean(){ // sample mean of percolation threshold
		meanofopensites=StdStats.mean(opensites);
		return meanofopensites;
	}
	public double stddev(){ // sample standard deviation of percolation threshold
		stddevofopensites=StdStats.stddev(opensites);
		return stddevofopensites;
	}
    public double confidenceLo(){ // low  endpoint of 95% confidence interval
    	return meanofopensites-(1.96*stddevofopensites/Math.sqrt(trials));
    }
	public double confidenceHi(){ // high endpoint of 95% confidence interval
		return meanofopensites+(1.96*stddevofopensites/Math.sqrt(trials));
	}

	public static void main(String[] args){ // test client (described below)
		PercolationStats per = new PercolationStats(Integer.parseInt(args[0]),Integer.parseInt(args[1]));
		System.out.printf("%-23s"+" = "+per.mean()+"\n","mean");
		System.out.printf("%-23s"+" = "+per.stddev()+"\n","stddev");
		System.out.printf("%-23s"+" = ["+per.confidenceLo()+","+per.confidenceHi()+"]","95% confidence interval");
	}
 }

小结

在实现目标功能时，同时也要注意代码的内存占用量及运行时间，在本题目中，Percolation类的open及percolates等方法需要反复调用，如果其中的方法块出现与n有关的for循环，则会出现运行时间~n的平方的情况。

本处实现亦还有改进之处，比如Percolation类中的数组a可以定义为布尔型，便可进一步节省内存占用。