注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
Percolation模型,以及计算threshold。
Percolation.java- package hw2;
- import edu.princeton.cs.algs4.WeightedQuickUnionUF;
- import java.lang.Math;
- public class Percolation {
- int N; //grid size
- String[] grid;
- int top;
- int bottom;
- WeightedQuickUnionUF wqu, wqu2;
- int[] openSites;
- int sizeOfOpenSites;
- Percolation(int N) {
- this.N = N;
- wqu = new WeightedQuickUnionUF((N * N) + 2);
- wqu2 = new WeightedQuickUnionUF((N * N) + 1);
- top = N * N;
- bottom = N * N + 1;
- grid = new String[N * N];
- openSites = new int[N * N];
- sizeOfOpenSites = 0;
- for (int i = 0; i < N * N; i ++) {
- grid[i] = "blocked";
- }
- for (int i = 0; i < N; i ++) {
- wqu.union(top, pos(0, i));
- wqu2.union(top, pos(0, i));
- wqu.union(bottom, pos(N - 1, i));
- }
- }
- int pos(int row, int col) {
- return (row * N) + col;
- }
- int size() {
- return N * N;
- }
- void open(int row, int col) {
- if (grid[pos(row, col)].equals("blocked")) grid[pos(row, col)] = "open";
- openSites[sizeOfOpenSites] = pos(row, col);
- sizeOfOpenSites ++;
- for (int i = 0; i <sizeOfOpenSites; i ++) {
- for (int j = i + 1; j < sizeOfOpenSites; j ++) {
- if ((Math.abs(openSites[i] - openSites[j]) == 1 && (Math.max(openSites[i], openSites[j]) % N) != 0) || (Math.abs(openSites[i] - openSites[j]) == N)) {
- if (!wqu.connected(openSites[i], openSites[j])) {
- wqu.union(openSites[i], openSites[j]);
- wqu2.union(openSites[i], openSites[j]);
- }
- }
- }
- }
- }
- boolean isOpen(int row, int col) {
- return grid[pos(row, col)].equals("open");
- }
- boolean isFull(int row, int col) {
- if (grid[pos(row, col)].equals("blocked")) {
- return false;
- } else {
- if(wqu.connected(top, bottom)) {
- return wqu2.connected(top, pos(row, col));
- } else {
- return wqu.connected(top, pos(row, col));
- }
- }
- }
- int numberOfOpenSites() {
- int n = 0;
- for (int i = 0; i < size(); i ++) {
- if (grid[i].equals("open")) n ++;
- }
- return n;
- }
- boolean percolates() {
- return wqu.connected(top, bottom);
- }
- public static void main(String[] args) {
- }
- }
复制代码 PercolationStats.java- package hw2;
- import edu.princeton.cs.introcs.StdRandom;
- import edu.princeton.cs.introcs.StdStats;
- import java.lang.Math;
- public class PercolationStats {
- int N, T;
- double u, sigma;
- double confidenceLow, confidenceHigh;
- double[] percData;
- Percolation perc;
- int[] order;
- int numberOfSites;
- double percentage;
- public PercolationStats(int N, int T) {
- if (N <= 0 || T <= 0) throw new java.lang.IllegalArgumentException("N and T should be integers bigger than 0");
- this.N = N;
- this.T = T;
- percData = new double[T];
- perc = new Percolation(N);
- order = new int[N * N];
- numberOfSites = 0;
- for (int i = 0; i < N * N; i ++) {
- order[i] = i;
- }
- for (int i = 0; i < T; i ++) {
- StdRandom.shuffle(order);
- numberOfSites = 0;
- perc = new Percolation(N);
- for (int j = 0; j < N * N && !perc.percolates(); j++) {
- perc.open(order[j] / N, order[j] % N);
- numberOfSites ++;
- }
- percentage = (double) numberOfSites / (double) (N * N);
- percData[i] = percentage;
- }
- }
- public double mean() {
- u = StdStats.mean(percData);
- return u;
- }
- public double stddev() {
- sigma = StdStats.stddev(percData);
- return sigma;
- }
- public double confidenceLow() {
- confidenceLow = u - (1.96 * sigma) / (Math.sqrt(T));
- return confidenceLow;
- }
- public double confidenceHigh() {
- confidenceHigh = u + (1.96 * sigma) / (Math.sqrt(T));
- return confidenceHigh;
- }
- public static void main(String[] args) {
- PercolationStats ps = new PercolationStats(10, 50);
- System.out.println("mean = " + ps.mean());
- System.out.println("standard deviation = " + ps.stddev());
- System.out.println("percolation threshold: " + "[" + ps.confidenceLow() + ", " + ps.confidenceHigh() + "]");
- }
- }
复制代码 |