首页 > 代码库 > 算法导论第四版学习——习题一Percolation
算法导论第四版学习——习题一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分的答案，不代表写得最好，请在自己实在完成不了的时候再看，不然的话做这个题目的意义一点都没有）
1 import edu.princeton.cs.algs4.WeightedQuickUnionUF; 2 3 4 public class Percolation { 5 private WeightedQuickUnionUF firstUnionFind; 6 private WeightedQuickUnionUF secondUnionFind; 7 private int row = 0; 8 private boolean[][] site; 9 10 public Percolation(int n) // create n-by-n grid, with all sites blocked11 {12 if (n <= 0) {13 throw new IllegalArgumentException();14 }15 16 firstUnionFind = new WeightedQuickUnionUF((n * n) + 2);17 secondUnionFind = new WeightedQuickUnionUF((n * n) + 1);18 row = n;19 site = new boolean[n][n];20 }21 22 public void open(int i, int j) // open site (row i, column j) if it is not open already23 {24 if ((i < 1) || (i > row) || (j < 1) || (j > row)) {25 throw new IndexOutOfBoundsException();26 }27 site[i - 1][j - 1] = true;28 int self = (((i - 1) * row) + j) - 1;29 int up = self - row;30 int down = self + row;31 int left = self - 1;32 int right = self + 1;33 34 if (i == 1) {35 firstUnionFind.union(row * row, self);36 secondUnionFind.union(row * row, self);37 }38 if (i == row) {39 firstUnionFind.union(row * row+1, self);40 }41 42 if ((i != 1) && isOpen(i - 1, j)) {43 firstUnionFind.union(up, self);44 secondUnionFind.union(up, self);45 }46 47 if ((i != row) && isOpen(i + 1, j)) {48 firstUnionFind.union(down, self);49 secondUnionFind.union(down, self);50 }51 52 if ((j != 1) && isOpen(i, j - 1)) {53 firstUnionFind.union(left, self);54 secondUnionFind.union(left, self);55 }56 57 if ((j != row) && isOpen(i, j + 1)) {58 firstUnionFind.union(right, self);59 secondUnionFind.union(right, self);60 }61 }62 63 public boolean isOpen(int i, int j) // is site (row i, column j) open?64 {65 if ((i < 1) || (i > row) || (j < 1) || (j > row)) {66 throw new IndexOutOfBoundsException();67 }68 return site[i - 1][j - 1];69 }70 71 public boolean isFull(int i, int j) // is site (row i, column j) full?72 {73 if ((i < 1) || (i > row) || (j < 1) || (j > row)) {74 throw new IndexOutOfBoundsException();75 }76 int self = (((i - 1) * row) + j) - 1;77 return secondUnionFind.connected(row * row, self);78 }79 80 public boolean percolates() // does the system percolate?81 {82 return firstUnionFind.connected(row * row + 1, row * row);83 }84 85 public static void main(String[] args) // test client (optional)86 {87 }88 }
1 import edu.princeton.cs.algs4.StdOut; 2 import edu.princeton.cs.algs4.StdRandom; 3 import edu.princeton.cs.algs4.StdStats; 4 5 6 public class PercolationStats { 7 private int trys = 0; 8 private double[] successTrials; 9 private double mean = 0;10 private double stddev = 0;11 12 public PercolationStats(int n, int trials) // perform trials independent experiments on an n-by-n grid13 {14 if ((n <= 0) || (trials <= 0)) {15 throw new IllegalArgumentException();16 }17 18 trys = trials;19 successTrials = new double[trys];20 21 for (int i = 0; i < trials; i++) {22 successTrials[i] = 0;23 24 Percolation percolationTries = new Percolation(n);25 26 while (!percolationTries.percolates()) {27 int a = StdRandom.uniform(1, n + 1);28 int b = StdRandom.uniform(1, n + 1);29 30 while (percolationTries.isOpen(a, b)) {31 a = StdRandom.uniform(1, n + 1);32 b = StdRandom.uniform(1, n + 1);33 }34 35 percolationTries.open(a, b);36 successTrials[i]++;37 }38 39 successTrials[i] = successTrials[i] / (n * n);40 }41 mean = StdStats.mean(successTrials);42 stddev = StdStats.stddev(successTrials);43 }44 45 public double mean() // sample mean of percolation threshold46 {47 return mean;48 }49 50 public double stddev() // sample standard deviation of percolation threshold51 {52 return stddev;53 }54 55 public double confidenceLo() // low endpoint of 95% confidence interval56 {57 return mean - ((1.96 * stddev) / Math.sqrt(trys));58 }59 60 public double confidenceHi() // high endpoint of 95% confidence interval61 {62 return mean + ((1.96 * stddev) / Math.sqrt(trys));63 }64 65 public static void main(String[] args) // test client (described below)66 {67 int n = Integer.parseInt(args[0]);68 int trials = Integer.parseInt(args[1]);69 PercolationStats percolationStatsCase = new PercolationStats(n, trials);70 StdOut.printf("%-24s", "mean");71 StdOut.printf("= %.16f\n", percolationStatsCase.mean());72 StdOut.printf("%-24s", "stddev");73 StdOut.printf("= %.18f\n", percolationStatsCase.stddev());74 StdOut.printf("%-24s", "95% confidence interval");75 StdOut.printf("= %.16f, %.16f\n", percolationStatsCase.confidenceLo(),76 percolationStatsCase.confidenceHi());77 }78 }
算法导论第四版学习——习题一Percolation
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。