欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-09 13:48:15
...

Programming Assignment 1: Percolation

问题描述

0.总结一下这个系列

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

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() +"]");

   }
}