首页 > 代码库 > Coursera Algorithms Programming Assignment 1: Percolation
Coursera Algorithms Programming Assignment 1: Percolation
题目来源http://coursera.cs.princeton.edu/algs4/assignments/percolation.html
作业分为两部分：建立模型和仿真实验。
最关键的部分就是建立模型对象。模型对象要求如下：
The model. We model a percolation system using an n-by-n grid of sites. Each site is either open or blocked. A full site is an open site that can be connected to an open site in the top row via a chain of neighboring (left, right, up, down) open sites. We say the system percolates if there is a full site in the bottom row. In other words, a system percolates if we fill all open sites connected to the top row and that process fills some open site on the bottom row. (For the insulating/metallic materials example, the open sites correspond to metallic materials, so that a system that percolates has a metallic path from top to bottom, with full sites conducting. For the porous substance example, the open sites correspond to empty space through which water might flow, so that a system that percolates lets water fill open sites, flowing from top to bottom.)
边界要求： By convention, the row and column indices are integers between 1 and n, where (1, 1) is the upper-left site: Throw a java.lang.IllegalArgumentException if any argument to open(), isOpen(), or isFull() is outside its prescribed range. The constructor should throw a java.lang.IllegalArgumentException if n ≤ 0.
性能要求： The constructor should take time proportional to n2; all methods should take constant time plus a constant number of calls to the union–find methods union(), find(), connected(), and count().
我的分析
本次作业根据教授在视频课上提示，可以在grid的上方和下方各加入一个虚节点，grid第一行的open节点都与top虚节点连通，grid最后一行的open节点都与bottom虚节点连通。这样只需判断top虚节点与bottom虚节点是否连通就知道grid是否渗透，而不需要去一一选取特定节点比对了。照着这个思路，我实现了下述模型代码，作业得分98。值得注意的是，模型代码的main中测试方法不是仅仅进行各本地测试就可以了，提交作业的时候会进行自动脚本测试，所以提交的版本main方法中必须读取args[0]中的文件名，并加载文件内容进行生成grid和open对应的site。
1 import edu.princeton.cs.algs4.In; 2 import edu.princeton.cs.algs4.StdOut; 3 import edu.princeton.cs.algs4.WeightedQuickUnionUF; 4 5 public class Percolation { 6 private static final boolean BLOCK = false; // block state 7 private static final boolean OPEN = true; // open state 8 9 /* topUF bottomUF n 均为final是因为它们只在构造函数时初始化，后续其值未发生变化 */ 10 private final WeightedQuickUnionUF topUF; // 用来记录与top虚节点的连通性 11 private final WeightedQuickUnionUF bottomUF;// 用来记录与bottom虚节点的连通性 12 private final int n; 13 14 private boolean[][] grid; 15 private boolean percolateFlag = false; // grid是否渗透的标志 16 private int openedNum = 0;// 已经open的site数目 17 18 public Percolation(int n) { 19 // create n-by-n grid, with all sites blocked 20 if (n < 1) 21 throw new IllegalArgumentException("grid size should be bigger than one !"); 22 this.n = n; 23 topUF = new WeightedQuickUnionUF(n * n + 1); // 多了一个节点的空间，位置n*n处用来代表虚节点 24 bottomUF = new WeightedQuickUnionUF(n * n + 1); // 多了一个节点的空间，位置n*n处用来代表虚节点 25 grid = new boolean[n][n]; 26 // 初始化grid设为block 27 for (int i = 0; i < n; i++) 28 for (int j = 0; j < n; j++) 29 grid[i][j] = BLOCK; 30 } 31 32 private void validate(int row, int col) { 33 if (row < 1 || col < 1 || row > n || col > n) 34 throw new IllegalArgumentException("input row or col is not illegal!"); 35 } 36 37 public void open(int row, int col) { 38 // open site (row, col) if it is not open already 39 validate(row, col); 40 if (grid[row - 1][col - 1] == OPEN) 41 return; 42 43 grid[row - 1][col - 1] = OPEN; 44 openedNum++; 45 46 // n为1时，open一个节点就达到渗透要求 47 if (n == 1) { 48 topUF.union(0, 1); 49 bottomUF.union(0, 1); 50 percolateFlag = true; 51 return; 52 } 53 54 // 第一行的所有节点都与top虚节点连通 55 if (row == 1) 56 topUF.union(n * n, col - 1); 57 58 // 最后一行的所有节点都与bottom虚节点连通 59 if (row == n) 60 bottomUF.union(n * n, (n - 1) * n + col - 1); 61 62 // 与上方节点的连通性 63 if (row > 1 && grid[row - 2][col - 1] == OPEN) { 64 topUF.union((row - 2) * n + col - 1, (row - 1) * n + col - 1); 65 bottomUF.union((row - 2) * n + col - 1, (row - 1) * n + col - 1); 66 } 67 68 // 与下方节点的连通性 69 if (row < n && grid[row][col - 1] == OPEN) { 70 topUF.union(row * n + col - 1, (row - 1) * n + col - 1); 71 bottomUF.union(row * n + col - 1, (row - 1) * n + col - 1); 72 } 73 74 // 与左侧节点的连通性 75 if (col > 1 && grid[row - 1][col - 2] == OPEN) { 76 topUF.union((row - 1) * n + col - 2, (row - 1) * n + col - 1); 77 bottomUF.union((row - 1) * n + col - 2, (row - 1) * n + col - 1); 78 } 79 80 // 与右侧节点的连通性 81 if (col < n && grid[row - 1][col] == OPEN) { 82 topUF.union((row - 1) * n + col, (row - 1) * n + col - 1); 83 bottomUF.union((row - 1) * n + col, (row - 1) * n + col - 1); 84 } 85 86 /* 87 * 判断条件!percolateFlag是为了防止渗透以后的重复判断 判断条件openedNum>=n 88 * 是因为openedNum达到n时才有可能渗透，在未达到n之前，不需要进行后续判断 89 * 一个节点open的时候刚好使grid渗透的条件是该节点同时与top虚节点和bottom虚节点连通 90 */ 91 if (!percolateFlag && openedNum >= n && topUF.connected(n * n, (row - 1) * n + col - 1) 92 && bottomUF.connected(n * n, (row - 1) * n + col - 1)) 93 percolateFlag = true; 94 95 } 96 97 public boolean isOpen(int row, int col) { 98 // is site (row, col) open? 99 validate(row, col); 100 return grid[row - 1][col - 1] == OPEN; 101 } 102 103 /** 104 * 一个节点只有同时在open状态并且与top虚节点连通时才是full状态 105 * @param row 106 * @param col 107 * @return 108 */ 109 public boolean isFull(int row, int col) { 110 // is site (row, col) full? 111 validate(row, col); 112 if (isOpen(row, col) && topUF.connected(n * n, (row - 1) * n + col - 1)) 113 return true; 114 else 115 return false; 116 } 117 118 public int numberOfOpenSites() { 119 // number of open sites 120 return openedNum; 121 } 122 123 public boolean percolates() { 124 // does the system percolate? 125 return percolateFlag; 126 } 127 128 //打印一些便于查看的信息 129 private void printCheckResult(int row, int col) { 130 StdOut.println("p(" + row + "," + col + ") is open=" + isOpen(row, col) + ";is full=" + isFull(row, col) 131 + ";percolates=" + percolates()); 132 } 133 134 /** 135 * 作业提交时main需要调用该方法，因为提交后在线脚本要用一堆input文件进行测试 136 * 137 * @param arg0 138 */ 139 private static void fileInputCheck(String arg0) { 140 // test client (optional) 141 In in = new In(arg0);//读入input文件名，并加载文件内容 142 String s = null; 143 int n = -1; 144 //读入grid的n 145 while (in.hasNextLine()) { 146 s = in.readLine(); 147 if (s != null && !s.trim().equals("")) 148 break; 149 } 150 s = s.trim(); 151 n = Integer.parseInt(s); 152 Percolation p = new Percolation(n); 153 154 //读入open的site坐标 155 while (in.hasNextLine()) { 156 s = in.readLine(); 157 if (s != null && !s.trim().equals("")) { 158 s = s.trim();//去掉输入字符串头尾空格 159 String[] sa = s.split("\\s+");//去掉中间所有空格 160 if (sa.length != 2) 161 break; 162 int row = Integer.parseInt(sa[0]); 163 int col = Integer.parseInt(sa[1]); 164 p.open(row, col); 165 } 166 } 167 168 } 169 170 /** 171 * 本地测试专用 172 */ 173 private static void generateCheck() { 174 // test client (optional) 175 Percolation p = new Percolation(3); 176 int row = 1, col = 3; 177 p.open(row, col); 178 p.printCheckResult(row, col); 179 row = 2; 180 col = 3; 181 p.open(row, col); 182 p.printCheckResult(row, col); 183 row = 3; 184 col = 3; 185 p.open(row, col); 186 p.printCheckResult(row, col); 187 row = 3; 188 col = 1; 189 p.open(row, col); 190 p.printCheckResult(row, col); 191 row = 2; 192 col = 1; 193 p.open(row, col); 194 p.printCheckResult(row, col); 195 row = 1; 196 col = 1; 197 p.open(row, col); 198 p.printCheckResult(row, col); 199 } 200 201 public static void main(String[] args) { 202 generateCheck(); 203 // fileInputCheck(args[0]); 204 } 205 }
仿真分析这一部分比较简单，其中需要注意的地方就是“随机选取row和col进行open”，如果简单的用random(int n)，选取[0,n)获取row和col，会有很多重复节点被选中，随着n越大，命中率就越低。于是我采用生成一个[0,n*n)的数组，数组内容随机排序，依次读取数组内容，就相当于随机取site。
1 import edu.princeton.cs.algs4.StdOut; 2 import edu.princeton.cs.algs4.StdRandom; 3 import edu.princeton.cs.algs4.StdStats; 4 5 public class PercolationStats { 6 /* t fractions 均为final是因为它们只在构造函数时初始化，后续其值未发生变化*/ 7 private final int t;//尝试次数 8 private final double[] fractions;//每一次尝试的渗透率得分 9 10 private double mean; 11 private double stddev; 12 13 public PercolationStats(int n, int trials) { 14 // perform trials independent experiments on an n-by-n grid 15 if (n <= 0 || trials <= 0) 16 throw new IllegalArgumentException("n ≤ 0 or trials ≤ 0"); 17 t = trials; 18 fractions = new double[t]; 19 for (int i = 0; i < t; i++) {//t次尝试 20 Percolation p = new Percolation(n); 21 int openNum = 0; 22 //为了实现随机open一个site，模仿QuickUnion的定位方法 23 //先生成一个[0,n*n)的数组，数组内容随机排序,依次读取数组内容，就相当于随机取site 24 int[] rand = StdRandom.permutation(n * n); 25 for (int pos : rand) { 26 //pos = (row-1)*n + col -1 27 int row = pos / n + 1; 28 int col = pos % n + 1; 29 p.open(row, col); 30 openNum++; 31 //只有openNum>=n时才有判断是否渗透的必要 32 if (openNum >= n && p.percolates()) 33 break; 34 } 35 double pt = (double) openNum / (n * n);//单次尝试的渗透率 36 fractions[i] = pt; 37 } 38 } 39 40 public double mean() { 41 // sample mean of percolation threshold 42 mean = StdStats.mean(fractions);//作业提交系统要求要调用一次StdStats.mean方法 43 return mean; 44 } 45 46 public double stddev() { 47 // sample standard deviation of percolation threshold 48 stddev = StdStats.stddev(fractions);//作业提交系统要求要调用一次StdStats.stddev方法 49 return stddev; 50 } 51 52 public double confidenceLo() { 53 // low endpoint of 95% confidence interval 54 return mean - 1.96 * stddev / Math.sqrt(t); 55 } 56 57 public double confidenceHi() { 58 // high endpoint of 95% confidence interval 59 return mean + 1.96 * stddev / Math.sqrt(t); 60 } 61 62 public static void main(String[] args) { 63 // test client (described below) 64 int n = Integer.parseInt(args[0]); 65 int t = Integer.parseInt(args[1]); 66 PercolationStats ps = new PercolationStats(n, t); 67 StdOut.printf("%-25s %s %f \n", "means", "=", ps.mean()); 68 StdOut.printf("%-25s %s %f \n", "stddev", "=", ps.stddev()); 69 StdOut.printf("%-25s %s%f%s%f%s\n", "95% confidence interval", "= [", ps.confidenceLo(), ", ", 70 ps.confidenceHi(), "]"); 71 } 72 }
Coursera Algorithms Programming Assignment 1: Percolation
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。