Coursera普林斯顿大学算法课

Coursera普林斯顿大学算法课

题目主页

以下程序100分通过测试。其中使用2个并查集来解决backlash问题，所以无法获得测试报告里提到的bonus，但仍然可以满分。

PercolationVisualizer.java和InteractivePercolationVisualizer.java是题目给的percolation-testing.zip里的图形动画显示程序，用来测试InteractivePercolationVisualizer.java的正确性。

例如：

java-algs4 

Percolation.java文件

import edu.princeton.cs.algs4.WeightedQuickUnionUF;public class Percolation {// create n-by-n grid, with all sites blockedprivate boolean[][] table;private final int nVal;private int openSites;private final WeightedQuickUnionUF uf;private final WeightedQuickUnionUF uf1;public Percolation(int n) {if (n <= 0)throw new IllegalArgumentException();nVal = n;openSites = 0;table = new boolean[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++)table[i][j] = false;}uf = new WeightedQuickUnionUF(n * n + 2);uf1 = new WeightedQuickUnionUF(n * n + 2);}// open site (row, col) if it is not open alreadypublic void open(int row, int col) {validIndices(row, col);if (!table[row - 1][col - 1]) {table[row - 1][col - 1] = true;openSites++;int pos = map2Dto1D(row, col);if (row == 1) {uf.union(pos, 0);uf1.union(pos, 0);}if (row > 1 && table[row - 2][col - 1]) {uf.union(pos, pos - nVal);uf1.union(pos, pos - nVal);}if (row < nVal && table[row][col - 1]) {uf.union(pos, pos + nVal);uf1.union(pos, pos + nVal);}if (col > 1 && table[row - 1][col - 2]) {uf.union(pos, pos - 1);uf1.union(pos, pos - 1);}if (col < nVal && table[row - 1][col]) {uf.union(pos, pos + 1);uf1.union(pos, pos + 1);}if (row == nVal)uf.union(pos, nVal * nVal + 1);}}// is site (row, col) open?public boolean isOpen(int row, int col) {validIndices(row, col);return table[row - 1][col - 1];}// is site (row, col) full?public boolean isFull(int row, int col) {validIndices(row, col);
//        if (!table[row][col])
//            return false;int pos = map2Dto1D(row, col);ted(pos, 0);}// number of open sitespublic int numberOfOpenSites() {return openSites;}// does the system percolate?public boolean percolates() {ted(0, nVal * nVal + 1);}private void validIndices(int row, int col) {if (row < 1 || row > nVal || col < 1 || col > nVal)throw new IllegalArgumentException();}private int map2Dto1D(int row, int col) {return (row - 1) * nVal + col;}
}

命令行测试输入

java-algs4 PercolationStats 200 100

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;public class PercolationStats {private final double meanVal;private final double stddevVal;private final double halfInterval;// perform trials independent experiments on an n-by-n gridpublic PercolationStats(int n, int trials) {if (n <= 0 || trials <= 0)throw new IllegalArgumentException();double[] samples = new double[trials];final int times = trials;for (int i = 0; i < trials; i++) {Percolation percolation = new Percolation(n);while (!percolation.percolates()) {int openSite = StdRandom.uniform(n * n) + 1;int row, col;if (openSite % n == 0) {row = openSite / n;col = n;} else {row = openSite / n + 1;col = openSite % n;}percolation.open(row, col);}double num = n * n;samples[i] = percolation.numberOfOpenSites() / num;}meanVal = an(samples);stddevVal = StdStats.stddev(samples);halfInterval = 1.96 * stddevVal / java.lang.Math.sqrt(times);}// sample mean of percolation thresholdpublic double mean() {return meanVal;}// sample standard deviation of percolation thresholdpublic double stddev() {return stddevVal;}// low  endpoint of 95% confidence intervalpublic double confidenceLo() {return meanVal - halfInterval;}// high endpoint of 95% confidence intervalpublic double confidenceHi() {return meanVal + halfInterval;}// test client (described below)public static void main(String[] args) {int n = Integer.parseInt(args[0]);int times = Integer.parseInt(args[1]);// int n=4, times=5;PercolationStats percolationStats = new PercolationStats(n, times);double mean = an();double stddev = percolationStats.stddev();double conLo = fidenceLo();double conHi = fidenceHi();StdOut.printf("mean%20s= %fn", " ", mean);StdOut.printf("stddev%18s= %fn", " ", stddev);StdOut.printf("95%% confidence interval = [%f, %f]", conLo, conHi);}
}