一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 674|回复: 0
收起左侧

cs61b 16sp HW 2 Percolation

[复制链接] |试试Instant~ |关注本帖
oumizx 发表于 2016-5-29 18:25:13 | 显示全部楼层 |阅读模式

[其他]CS61B Data Structures #8 - 16 Spring@UCB

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Percolation模型,以及计算threshold。
1.png    2.png    3.png    4.png


output.png


Percolation.java
  1. package hw2;

  2. import edu.princeton.cs.algs4.WeightedQuickUnionUF;
  3. import java.lang.Math;

  4. public class Percolation {
  5.     int N; //grid size
  6.     String[] grid;
  7.     int top;
  8.     int bottom;
  9.     WeightedQuickUnionUF wqu, wqu2;
  10.     int[] openSites;
  11.     int sizeOfOpenSites;

  12.     Percolation(int N) {
  13.         this.N = N;
  14.         wqu = new WeightedQuickUnionUF((N * N) + 2);
  15.         wqu2 = new WeightedQuickUnionUF((N * N) + 1);
  16.         top = N * N;
  17.         bottom = N * N + 1;
  18.         grid = new String[N * N];
  19.         openSites = new int[N * N];
  20.         sizeOfOpenSites = 0;
  21.         for (int i = 0; i < N * N; i ++) {
  22.             grid[i] = "blocked";
  23.         }
  24.         for (int i = 0; i < N; i ++) {
  25.             wqu.union(top, pos(0, i));
  26.             wqu2.union(top, pos(0, i));
  27.             wqu.union(bottom, pos(N - 1, i));
  28.         }
  29.     }

  30.     int pos(int row, int col) {
  31.         return (row * N) + col;
  32.     }

  33.     int size() {
  34.         return N * N;
  35.     }

  36.     void open(int row, int col) {
  37.         if (grid[pos(row, col)].equals("blocked")) grid[pos(row, col)] = "open";
  38.         openSites[sizeOfOpenSites] = pos(row, col);
  39.         sizeOfOpenSites ++;
  40.         for (int i = 0; i <sizeOfOpenSites; i ++) {
  41.             for (int j = i + 1; j < sizeOfOpenSites; j ++) {
  42.                 if ((Math.abs(openSites[i] - openSites[j]) == 1 && (Math.max(openSites[i], openSites[j]) % N) != 0) || (Math.abs(openSites[i] - openSites[j]) == N)) {
  43.                     if (!wqu.connected(openSites[i], openSites[j])) {
  44.                         wqu.union(openSites[i], openSites[j]);
  45.                         wqu2.union(openSites[i], openSites[j]);
  46.                     }
  47.                 }
  48.             }
  49.         }
  50.     }

  51.     boolean iSOPen(int row, int col) {
  52.         return grid[pos(row, col)].equals("open");
  53.     }

  54.     boolean isFull(int row, int col) {
  55.         if (grid[pos(row, col)].equals("blocked")) {
  56.             return false;
  57.         } else {
  58.             if(wqu.connected(top, bottom)) {
  59.                 return wqu2.connected(top, pos(row, col));
  60.             } else {
  61.                 return wqu.connected(top, pos(row, col));
  62.             }
  63.         }
  64.     }

  65.     int numberOfOpenSites() {
  66.         int n = 0;
  67.         for (int i = 0; i < size(); i ++) {
  68.             if (grid[i].equals("open")) n ++;
  69.         }
  70.         return n;
  71.     }

  72.     boolean percolates() {
  73.         return wqu.connected(top, bottom);
  74.     }

  75.     public static void main(String[] args) {

  76.     }

  77. }
复制代码
PercolationStats.java
  1. package hw2;                       
  2. import edu.princeton.cs.introcs.StdRandom;
  3. import edu.princeton.cs.introcs.StdStats;
  4. import java.lang.Math;

  5. public class PercolationStats {
  6.     int N, T;
  7.     double u, sigma;
  8.     double confidenceLow, confidenceHigh;
  9.     double[] percData;
  10.     Percolation perc;
  11.     int[] order;
  12.     int numberOfSites;
  13.     double percentage;

  14.     public PercolationStats(int N, int T) {
  15.         if (N <= 0 || T <= 0) throw new java.lang.IllegalArgumentException("N and T should be integers bigger than 0");
  16.         this.N = N;
  17.         this.T = T;
  18.         percData = new double[T];
  19.         perc = new Percolation(N);
  20.         order = new int[N * N];
  21.         numberOfSites = 0;
  22.         for (int i = 0; i < N * N; i ++) {
  23.             order[i] = i;
  24.         }
  25.         for (int i = 0; i < T; i ++) {
  26.             StdRandom.shuffle(order);
  27.             numberOfSites = 0;
  28.             perc = new Percolation(N);
  29.             for (int j = 0; j < N * N && !perc.percolates(); j++) {
  30.                 perc.open(order[j] / N, order[j] % N);
  31.                 numberOfSites ++;
  32.             }
  33.             percentage = (double) numberOfSites / (double) (N * N);
  34.             percData[i] = percentage;
  35.         }
  36.     }

  37.     public double mean() {
  38.         u = StdStats.mean(percData);
  39.         return u;
  40.     }

  41.     public double stddev() {
  42.         sigma = StdStats.stddev(percData);
  43.         return sigma;
  44.     }

  45.     public double confidenceLow() {
  46.         confidenceLow = u - (1.96 * sigma) / (Math.sqrt(T));
  47.         return  confidenceLow;
  48.     }

  49.     public double confidenceHigh() {
  50.         confidenceHigh = u + (1.96 * sigma) / (Math.sqrt(T));
  51.         return confidenceHigh;
  52.     }

  53.     public static void main(String[] args) {
  54.         PercolationStats ps = new PercolationStats(10, 50);
  55.         System.out.println("mean = " + ps.mean());
  56.         System.out.println("standard deviation = " + ps.stddev());
  57.         System.out.println("percolation threshold: " + "[" + ps.confidenceLow() + ", " + ps.confidenceHigh() + "]");
  58.     }
  59. }                       
复制代码

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 20:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表