算法导论第四版学习——习题一Percolation

题目正文：

http://coursera.cs.princeton.edu/algs4/assignments/percolation.html

作业难点：

1、backwash（倒灌）的判断，如果不使用另一个WeightedUnionFind对象，要在要求的时间和空间范围内实现是很困难的

和论坛里的学生一样，尝试只只使用上部的虚拟节点，下部判断联通使用循环+break，提交后不满足时间复杂度要求

你也可以不考虑backwash这种情况，因为backwash对连通性并没有直接影响

2、UnionFind数据结构是一维的，但是输入数据是二维的，不用说，这需要两个维度的转换

3、输入数据的下标是1到N，所以必须好好测试边界情况，这点可以用测试数据greeting57.txt测试

作业技巧：

1、一般来说避免不必要的计算，把某些固定的值缓存起来可以提高运行效率，比如计算mean和stddev

2、计算PercolationStats时，需要在未打开的site中按概率P取site打开

这一点其实用random一个站点，判断site已打开再循环找下一个site，直到找到未打开site，就可以满足要求了

应该有更有效率的方法，比如将所有site的下标按一维存储，每次将取出的site下标和最后一位互换，下次random时候取uniform（1，N-1），避免无效尝试，以此类推。

代码参考：

（这是我自己亲测100分的答案，不代表写得最好，请在自己实在完成不了的时候再看，不然的话做这个题目的意义一点都没有）

import edu.princeton.cs.algs4.WeightedQuickUnionUF;


public class Percolation {
    private WeightedQuickUnionUF firstUnionFind;
    private WeightedQuickUnionUF secondUnionFind;
    private int row = 0;
    private boolean[][] site;

    public Percolation(int n) // create n-by-n grid, with all sites blocked
     {
        if (n <= 0) {
            throw new IllegalArgumentException();
        }

        firstUnionFind = new WeightedQuickUnionUF((n * n) + 2);
        secondUnionFind = new WeightedQuickUnionUF((n * n) + 1);
        row = n;
        site = new boolean[n][n];
    }

    public void open(int i, int j) // open site (row i, column j) if it is not open already
     {
        if ((i < 1) || (i > row) || (j < 1) || (j > row)) {
            throw new IndexOutOfBoundsException();
        }
        site[i - 1][j - 1] = true;
        int self = (((i - 1) * row) + j) - 1;
        int up = self - row;
        int down = self + row;
        int left = self - 1;
        int right = self + 1;

        if (i == 1) {
            firstUnionFind.union(row * row, self);
            secondUnionFind.union(row * row, self);
        }
        if (i == row) {
            firstUnionFind.union(row * row+1, self);
        }

        if ((i != 1) && isOpen(i - 1, j)) {
            firstUnionFind.union(up, self);
            secondUnionFind.union(up, self);
        }

        if ((i != row) && isOpen(i + 1, j)) {
            firstUnionFind.union(down, self);
            secondUnionFind.union(down, self);
        }

        if ((j != 1) && isOpen(i, j - 1)) {
            firstUnionFind.union(left, self);
            secondUnionFind.union(left, self);
        }

        if ((j != row) && isOpen(i, j + 1)) {
            firstUnionFind.union(right, self);
            secondUnionFind.union(right, self);
        }
    }

    public boolean isOpen(int i, int j) // is site (row i, column j) open?
     {
        if ((i < 1) || (i > row) || (j < 1) || (j > row)) {
            throw new IndexOutOfBoundsException();
        }
        return site[i - 1][j - 1];
    }

    public boolean isFull(int i, int j) // is site (row i, column j) full?
     {
        if ((i < 1) || (i > row) || (j < 1) || (j > row)) {
            throw new IndexOutOfBoundsException();
        }
        int self = (((i - 1) * row) + j) - 1;
        return secondUnionFind.connected(row * row, self);
    }

    public boolean percolates() // does the system percolate?
     {
        return firstUnionFind.connected(row * row + 1, row * row);
    }

    public static void main(String[] args) // test client (optional)
     {
    }
}

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


public class PercolationStats {
    private int trys = 0;
    private double[] successTrials;
    private double mean = 0;
    private double stddev = 0;

    public PercolationStats(int n, int trials) // perform trials independent experiments on an n-by-n grid
     {
        if ((n <= 0) || (trials <= 0)) {
            throw new IllegalArgumentException();
        }

        trys = trials;
        successTrials = new double[trys];

        for (int i = 0; i < trials; i++) {
            successTrials[i] = 0;

            Percolation percolationTries = new Percolation(n);

            while (!percolationTries.percolates()) {
                int a = StdRandom.uniform(1, n + 1);
                int b = StdRandom.uniform(1, n + 1);

                while (percolationTries.isOpen(a, b)) {
                    a = StdRandom.uniform(1, n + 1);
                    b = StdRandom.uniform(1, n + 1);
                }

                percolationTries.open(a, b);
                successTrials[i]++;
            }

            successTrials[i] = successTrials[i] / (n * n);
        }
        mean = StdStats.mean(successTrials);
        stddev =  StdStats.stddev(successTrials);
    }

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

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

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

    public double confidenceHi() // high endpoint of 95% confidence interval
    {
        return mean + ((1.96 * stddev) / Math.sqrt(trys));
    }

    public static void main(String[] args) // test client (described below)
     {
        int n = Integer.parseInt(args[0]);
        int trials = Integer.parseInt(args[1]);
        PercolationStats percolationStatsCase = new PercolationStats(n, trials);
        StdOut.printf("%-24s", "mean");
        StdOut.printf("= %.16f\n", percolationStatsCase.mean());
        StdOut.printf("%-24s", "stddev");
        StdOut.printf("= %.18f\n", percolationStatsCase.stddev());
        StdOut.printf("%-24s", "95% confidence interval");
        StdOut.printf("= %.16f, %.16f\n", percolationStatsCase.confidenceLo(),
            percolationStatsCase.confidenceHi());
    }
}