Percolation.java
import edu.princeton.cs.algs4.WeightedQuickUnionUF; /** * Created by LK on 2017/4/3. */ public class Percolation { private WeightedQuickUnionUF uf; private WeightedQuickUnionUF uf2; private int number; private boolean[][] map; private int numberOfOpenSites; public Percolation(int number) // create number-by-number grid, with all sites blocked { if (number <= 0) throw new java.lang.IllegalArgumentException(); uf = new WeightedQuickUnionUF(number * number + 2); uf2 = new WeightedQuickUnionUF(number * number + 1); this.number = number; map = new boolean[this.number][this.number]; for (int i = 0; i < this.number; ++i) for (int j = 0; j < this.number; ++j) map[i][j] = false; this.numberOfOpenSites = 0; } public void open(int row, int col) // open site (row, col) if it is not open already { if (row < 1 || col < 1 || row > number || col > number) throw new IndexOutOfBoundsException(); if (isOpen(row, col)) return; map[row - 1][col - 1] = true; ++numberOfOpenSites; int q = (row - 1) * number + col; if (row - 2 >= 0) { if (map[row - 2][col - 1]) { uf.union(q - number, q); uf2.union(q - number, q); } } else { uf.union(0, q); uf2.union(0, q); } if (col - 2 >= 0) { if (map[row - 1][col - 2]) { uf.union(q - 1, q); uf2.union(q - 1, q); } } if (row < number) { if (map[row][col - 1]) { uf.union(q + number, q); uf2.union(q + number, q); } } else { uf.union(number * number + 1, q); } if (col < number) { if (map[row - 1][col]) { uf.union(q + 1, q); uf2.union(q + 1, q); } } } public boolean isOpen(int row, int col) // is site (row, col) open? { if (row < 1 || col < 1 || row > number || col > number) throw new IndexOutOfBoundsException(); return map[row - 1][col - 1]; } public boolean isFull(int row, int col) // is site (row, col) full? { if (row < 1 || col < 1 || row > number || col > number) throw new IndexOutOfBoundsException(); return uf2.connected(0, (row - 1) * number + col); } public int numberOfOpenSites() // number of open sites { return numberOfOpenSites; } public boolean percolates() // does the system percolate? { return uf.connected(0, number * number + 1); } }PercolationStats .java
import edu.princeton.cs.algs4.StdRandom; import edu.princeton.cs.algs4.StdStats; /** * Created by LK on 2017/4/3. */ public class PercolationStats { private int number, trials; private double[] count; public PercolationStats(int number, int trials) // perform trials independent experiments on an number-by-number grid { if (number <= 0 || trials <= 0) throw new java.lang.IllegalArgumentException(); this.number = number; this.trials = trials; count = new double[this.trials]; for (int i = 0; i < this.trials; ++i) { count[i] = 0; Percolation p = new Percolation(this.number); while (!p.percolates()) { int x = StdRandom.uniform(this.number) + 1; int y = StdRandom.uniform(this.number) + 1; if (!p.isOpen(x, y)) { p.open(x, y); ++count[i]; } } count[i] /= (number * number); } } public double mean() // sample mean of percolation threshold { return StdStats.mean(count); } public double stddev() // sample standard deviation of percolation threshold { return StdStats.stddev(count); } public double confidenceLo() // low endpoint of 95% confidence interval { double mean = mean(); double stddev = stddev(); return mean - 1.96 * stddev / Math.sqrt(trials); } public double confidenceHi() // high endpoint of 95% confidence interval { double mean = mean(); double stddev = stddev(); return mean + 1.96 * stddev / Math.sqrt(trials); } public static void main(String[] args) // test client (described below) { if (args.length == 2) { int number = Integer.parseInt(args[0]); int trials = Integer.parseInt(args[1]); PercolationStats p = new PercolationStats(number, trials); System.out.println("mean = " + p.mean()); System.out.println("stddev = " + p.stddev()); System.out.println("95% confidence interval = [" + p.confidenceLo() + ", " + p.confidenceHi() + "]"); } } }提交结果
欢迎交流
