普林斯顿Week1-Percolation 渗透

努力写了，只有89分。将就看吧。

Percolation.java

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

public class Percolation {
    private WeightedQuickUnionUF uf1;

    private WeightedQuickUnionUF uf2;

    private Boolean[] openStatus;

    private int N;

    private int num;

    public Percolation(int n){
        this.N = n;
        this.openStatus = new Boolean[(this.N+1)*(this.N+2)];
        this.num = 0;
        for(int i = 0;i<openStatus.length;i++){
            openStatus[i]=false;
        }
        this.uf1 = new WeightedQuickUnionUF((this.N+1)*(this.N+2));
        this.uf2 = new WeightedQuickUnionUF((this.N+1)*(this.N+2));
    }
 
    private int trans(int row,int col){
        return row*(N+1)+col;
    }
 
    private void checkArrayOrder(int row,int col){
        if(row<1 || row>N){
            throw new IllegalArgumentException("row error");
        }
        if(col<1 || row>N){
            throw new IllegalArgumentException("col error");
        }
    }
    public void open(int row, int col){
        int id = trans(row,col);
        if(isOpen(row,col)){
           return;
        }
      
        openStatus[id] = true;
        num++;
        if(row==1){
            uf1.union(0,id);
            uf2.union(0,id);
        }
        if(row==N){
            uf1.union((N+1)*(N+1),id);
        }
        int[] x = {1,-1,0,0};
        int[] y = {0,0,1,-1};

        for(int i=0;i<x.length;i++){
            int adjRow = row+x[i];
            int adjCol = col+y[i];
         
            if(openStatus[trans(adjRow,adjCol)]){
                uf1.union(trans(adjRow,adjCol),id);
                uf2.union(trans(adjRow,adjCol),id);
            }
        }
    }
    //is site (row, col) open?
    public boolean isOpen(int row, int col){
        checkArrayOrder(row,col);
        return openStatus[trans(row,col)];
    }
    //is site (row, col) full?
    public boolean isFull(int row, int col){
        checkArrayOrder(row,col);
        return uf2.connected(0,trans(row,col));
    }
    // number of open sites
    public int numberOfOpenSites() {
        return num;
    }
    // does the system percolate?
    public boolean percolates() {
        return uf1.connected(0,(N+1)*(N+1));
    }

}

PercolationStats.java

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

public class PercolationStats {
    //试验次数
    private int trials;
    //阈值
    private double[] p;
    // perform trials independent experiments on an n-by-n grid
    public PercolationStats(int n, int trials) {
        this.trials =trials;
        if(n<1||trials<1){
            throw new IllegalArgumentException("渗透模型大小与实验次数不可小于等于零");
        }
        p = new double[trials];
        for(int i = 0;i<this.trials;i++){
            Percolation percolation = new Percolation(n);
            while (!percolation.percolates()){
                int row = StdRandom.uniform(n)+1;
                int col = StdRandom.uniform(n)+1;
                if(!percolation.isOpen(row,col)){
                    percolation.open(row,col);
                }
                if(percolation.percolates()){
                    break;
                }
            }
            p[i] = (double) percolation.numberOfOpenSites()/(n*n);
        }
    }

    // sample mean of percolation threshold
    public double mean() {
        return StdStats.mean(p);
    }

    // sample standard deviation of percolation threshold
    public double stddev() {
        return StdStats.stddev(p);
    }

    // low  endpoint of 95% confidence interval
    public double confidenceLo() {
        return mean()-1.96*stddev()/Math.sqrt(this.trials);
    }

    // high endpoint of 95% confidence interval
    public double confidenceHi() {
        return mean()+1.96*stddev()/Math.sqrt(this.trials);
    }
    // test client (described below)
    public static void main(String[] args) {
        int n = 100;
        int trail = 100;
        PercolationStats percolationStats = new PercolationStats(n,trail);
        StdOut.println(percolationStats.mean());
        StdOut.println(percolationStats.stddev());
        StdOut.println(percolationStats.confidenceLo());
        StdOut.println(percolationStats.confidenceHi());
    }

}