Coursera-Algorithms,Part I-Robert Sedgewick-Programming Assignment 1

Programming Assignment 1: Percolation

问题描述

0.总结一下这个系列

• 挺有意思
• 偏向应用，有空还是要回头把课上的底层代码实现一遍。（做作业之前敲那是更好了，可惜我没啥时间，只有部分章节做到了这一点）
• 很好地体现了面向对象编程思想。对于一个对OOP理解停留在“People - Student” “Shape - Circle” 层面的学习者，这份作业应该会是一种很好的引导，也让人开了开眼界。
• Java的Comparable Comparator Iterable Iterator等概念对初学者可能有点抽象，个人认为是语言方面的一大难点。稍微翻一点Java教程有关部分，结合例子多看看，就慢慢觉得很合理了。作业其它地方用到的Java很简单，有C++基础可以很快入门。
• OJ的style check虽然不计分，但值得一看！虽然里面的规则可能不是普适的，但对一个对代码风格没有一点概念的初学者来说，还是有必要锤炼一下。
  

1.代码

Percolation.java

import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {
    private final WeightedQuickUnionUF uf1;  // including both "top site" and "bottom site"
    private final WeightedQuickUnionUF uf2;  // including only "top site" 
    private final int size;                  // store value n
    private final int size2;                 // store value n^2
    private int openNumber;            
    private boolean[][] grid;                // store the state of each site: 1-open 0-blocked

    public Percolation(int n) // create n-by-n grid, with all sites blocked
    {
        if (n <= 0) throw new IllegalArgumentException();
        uf1 = new WeightedQuickUnionUF(n * n + 2);
        uf2 = new WeightedQuickUnionUF(n * n + 1);
        size = n;
        size2 = n * n;
        openNumber = 0;
        grid = new boolean[n][n];  
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                grid[i][j] = false;
            }   
        }
    }
// ------------------------------------------------------- //    
//         Private Methods: debugging tools                //
// ------------------------------------------------------- //
    private void showGrid()// print 1/0s representing if the site is open
    {
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                if (grid[i][j]) System.out.print("1 ");
                else System.out.print("0 ");
            }
            System.out.println();           
        }
        System.out.println();
    }

    private void showIfFull()// print 1/0s representing if the site is full
    {
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                if (isFull(i + 1, j + 1)) System.out.print(1 + " ");
                else System.out.print(0 + " ");
            }
            System.out.println();            
        }
        System.out.println();
    }

    private void showIfConnected(int row1, int col1, int row2, int col2)// print if the two sites are connected
    {
        System.out.println(uf1.connected(idx(row1, col1), idx(row2, col2)));
    }
// ------------------------------------------------------- //    
//      Private Methods: often used function block         //
// ------------------------------------------------------- //
    private int idx(int row, int col)// convert to the index in UF model for each site
    {
        return size * (row - 1) + col - 1;
    }
    private void union(int row, int col, String s)// handling connections w.r.t. "top site" and "bottom site" 
    {        
        if (s.compareTo("top") == 0)
        {
            uf1.union(idx(row, col), size2);
            uf2.union(idx(row, col), size2);
        }
        if (s.compareTo("bottom") == 0) uf1.union(idx(row, col), size2 + 1);
    }
    private void unionIfBothOpen(int rowOpen, int colOpen, int rowTest, int colTest)// connceting two nomal sites if both open
    {    
        if (isOpen(rowTest, colTest)) {            
            uf1.union(idx(rowOpen, colOpen), idx(rowTest, colTest));
            uf2.union(idx(rowOpen, colOpen), idx(rowTest, colTest));
        }
    }
// ------------------------------------------------------- //    
//     Public Methods: assignment requirements             //
// ------------------------------------------------------- //
    public void open(int row, int col) // open site (row, col) if it is not open already
    {
        if (row < 1 || row > size || col < 1 || col > size) 
            throw new IllegalArgumentException();
        if (isOpen(row, col)) return;
        grid[row - 1][col - 1] = true;                   
        // Check vertically
        if (row != 1) unionIfBothOpen(row, col, row - 1, col);
        else union(row, col, "top");
        if (row != size) unionIfBothOpen(row, col, row + 1, col);
        else union(row, col, "bottom");
        // Check horizontally
        if (col != 1) unionIfBothOpen(row, col, row, col - 1);     
        if (col != size) unionIfBothOpen(row, col, row, col + 1);    
        openNumber++;
    }
    public boolean isOpen(int row, int col) // is site (row, col) open?
    {
        if (row < 1 || row > size || col < 1 || col > size) 
            throw new IllegalArgumentException();
        return grid[row - 1][col - 1];
    }
    public boolean isFull(int row, int col) // is site (row, col) full? 
    {
        if (row < 1 || row > size || col < 1 || col > size) 
            throw new IllegalArgumentException();
        return uf2.connected(idx(row, col), size2);
    }
    public int numberOfOpenSites() // number of open sites
    {
        return openNumber;
    }
    public boolean percolates() // does the system percolate?
    {
        return uf1.connected(size2, size2 + 1);
    }
    public static void main(String[] args) // test client (optional)
    {       
        Percolation p = new Percolation(4);
        p.open(1, 1);
        p.open(1, 2);
        p.open(4, 3);
        p.open(4, 1);
        p.open(2, 3);
        p.open(2, 4);
        p.open(3, 3);
        p.open(3, 4);
        p.open(1, 4);
        p.showGrid();
        p.showIfFull();
        p.showIfConnected(4, 4, 4, 3);
        System.out.println(p.percolates());
    }
}

PercolationStats.java

import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;
// import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class PercolationStats {
   private final double[] threshold;
   private final int trials;
   private final double mu;
   private final double sigma;
   public PercolationStats(int n, int trials)    // perform trials independent experiments on an n-by-n grid
   {
       if(n <=0 || trials <= 0) throw new IllegalArgumentException();
       threshold = new double[trials];
       this.trials = trials;
       for (int i = 0; i < trials; i++)
       {
           threshold[i] = singleGo(n);
       }
       mu = StdStats.mean(threshold);
       sigma = StdStats.stddev(threshold);
   }
   private double singleGo(int n)// implementing one Monte Carlo experiment
   {
       Percolation p = new Percolation(n);
       while (!p.percolates())
       {
           p.open(StdRandom.uniform(n) + 1, StdRandom.uniform(n) + 1);
       }
       return p.numberOfOpenSites() * 1.0 / n / n;
   }
   public double mean()                          // sample mean of percolation threshold
   {
       return mu;
   }
   public double stddev()                        // sample standard deviation of percolation threshold
   {
       return sigma;
   }
   public double confidenceLo()                  // low  endpoint of 95% confidence interval
   {
       return mu - 1.96 * sigma / Math.sqrt(trials);
   }
   public double confidenceHi()                  // high endpoint of 95% confidence interval
   {
       return mu + 1.96 * sigma / Math.sqrt(trials);
   }
   public static void main(String[] args)        // test client (described below)
   {
       PercolationStats ps = new PercolationStats(Integer.parseInt(args[0]),Integer.parseInt(args[1]));
       System.out.println("mean                    = " + ps.mu);
       System.out.println("stddev                  = " + ps.sigma);
       System.out.println("95% confidence interval = [" + ps.confidenceLo() + ", " + ps.confidenceHi() +"]");

   }
}