یه مبحثی توی فیزیک قبل از اختراع کامپیوتر مطرح بود که میگه چه زمانی ماده از بالای یه جسم میتونه به پائین تراوش کنه ؟ مثلا تو عکس زیر ما هر خونه ای که داریم یا بازه(سفید) یا بسته است(سیاه) یا بازه و مایع توشه(ابی) . زمانی که از سطح بالا با استفاده از خونه های باز همجوار راهی به سطح پائین وجود داشته باشه ، میگیم که توارش انجام شده .
percolation-250.png
ازمایشها نشون دادن که pی استانه ای وجود دارد به گونه ای که اگر احتمال باز بودن خانه ها از ان p بیشتر باشد ، به احتمال بسیار قوی تراوش انجام خواهد شد و اگر کمتر باشد تراوشی انجام نخواهد شد . در شکل زیر این نمودار را مشاهده میکنید :
Captیبسure.PNG
هدف این برنامه ای که نوشتیم محاسبه این p هست . به طوری که ما ابتدا یه جدول n*n انتخاب میکنیم و تابع ایجاد اعداد شانسی رو بر روی اون لحاظ مکنیم . تا بهصورت شانسی به تعداد 1000 بار ویا بیشتر(وردی کاربر) این کار را انجام دهد و مقدار p را محاسبه کند .
برای اینکار داد ه ساختاری را معرفی کرده ایم که بتونه این عمل رو پیاده سازیکنه . این داده ساختار مثل همبندی پویاست و عکسشو اینجا قرار میدم :کدهاشو بخونید متوجه میشید نیازی ب توضیح نیست :
Captشسیure.PNG
کلاس WeightedQuickUnionFind همون ساختار داده هست
کلاس PercolationStats و Percolation عمل و شرط تراوش رو بررسی میکنند
کلاس PercolationVisualizerهم برای گرافیکی بودن برنامه هست :
public class WeightedQuickUnionUF { private int[] id; // id[i] = parent of i
private int[] sz; // sz[i] = number of objects in subtree rooted at i
private int count; // number of components
// Create an empty union find data structure with N isolated sets.
public WeightedQuickUnionUF(int N) {
count = N;
id = new int[N];
sz = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
sz[i] = 1;
}
}
// Return the number of disjoint sets.
public int count() {
return count;
}
// Return component identifier for component containing p
public int find(int p) {
while (p != id[p])
p = id[p];
return p;
}
// Are objects p and q in the same set?
public boolean connected(int p, int q) {
return find(p) == find(q);
}
// Replace sets containing p and q with their union.
public void union(int p, int q) {
int i = find(p);
int j = find(q);
if (i == j) return;
// make smaller root point to larger one
if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
else { id[j] = i; sz[i] += sz[j]; }
count--;
}
public static void main(String[] args) {
int N = StdIn.readInt();
WeightedQuickUnionUF uf = new WeightedQuickUnionUF(N);
// read in a sequence of pairs of integers (each in the range 0 to N-1),
// calling find() for each pair: If the members of the pair are not already
// call union() and print the pair.
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (uf.connected(p, q)) continue;
uf.union(p, q);
StdOut.println(p + " " + q);
}
StdOut.println(uf.count() + " components");
}
}
..
public class Percolation {
private int N;
private int topVS;
private int bottomVS;
private boolean[][] grid;
private WeightedQuickUnionUF union;
private WeightedQuickUnionUF PRBL;
public Percolation(int n) {
N = n;
union = new WeightedQuickUnionUF((n + 1) * (n + 1) + 2);
PRBL = new WeightedQuickUnionUF((n + 1) * (n + 1) + 2);
topVS = (n + 1) * (n + 1);
bottomVS = (n + 1) * (n + 1) + 1;
for (int j = 1; j <= N; j++) {
union.union(topVS, xyTo1D(1, j));
PRBL.union(topVS, xyTo1D(1, j));
}
for (int j = 1; j <= N; j++) {
union.union(bottomVS, xyTo1D(N, j));
}
grid = new boolean[N + 1][N + 1];
}
/**
* Opens the site located at row i and column j.
*/
public void open(int i, int j) {
checkIndices(i, j);
grid[i][j] = true;
int site1D = xyTo1D(i, j);
if (i < N) {
if (grid[i + 1][j]) {
union.union(site1D, xyTo1D(i + 1, j));
PRBL.union(site1D, xyTo1D(i + 1, j));
}
} if (i > 1) {
if (grid[i - 1][j]) {
union.union(site1D, xyTo1D(i - 1, j));
PRBL.union(site1D, xyTo1D(i - 1, j));
}
} if (j < N) {
if (grid[i][j + 1] && j < N) {
union.union(site1D, xyTo1D(i, j + 1));
PRBL.union(site1D, xyTo1D(i, j + 1));
}
} if (j > 1) {
if (grid[i][j - 1] && j > 0) {
union.union(site1D, xyTo1D(i, j - 1));
PRBL.union(site1D, xyTo1D(i, j - 1));
}
}
}
/**
* Returns true if site (i, j) is open,
* otherwise returns false.
*/
public boolean isOpen(int i, int j) {
checkIndices(i, j);
return grid[i][j];
}
/**
* Returns true if site (i, j) is full,
* otherwise returns false.
*/
public boolean isFull(int i, int j) {
checkIndices(i, j);
if (!PRBL.connected(xyTo1D(i, j), topVS)) {
return false;
}
if (grid[i][j] && union.connected(xyTo1D(i, j), topVS)) {
return true;
}
return false;
}
/**
* Returns true if the system percolates,
* otherwise returns false.
*/
public boolean percolates() {
return union.connected(topVS, bottomVS);
}
/**
* Converts the position (row and column) of
* a site to its corresponding object number.
*/
private int xyTo1D(int i, int j) {
return N * i + j;
}
/**
* Checks if the site (i, j) exists in the grid.
* If it does not exist, throws an exception.
*/
private void checkIndices(int i, int j) {
if (i > N || i < 1) {
new IndexOutOfBoundsException("Row index i out of bounds");
} if (j > N || j < 1) {
new IndexOutOfBoundsException("Column index j out of bounds");
}
}
// test client
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
Percolation percolation = new Percolation(N);
percolation.open(1, 1);
percolation.open(2, 1);
percolation.open(3, 1);
percolation.open(4, 1);
percolation.open(5, 1);
StdOut.println(percolation.percolates());
}
}
..
public class PercolationStats {
private int T;
private double[] result;
public PercolationStats(int N, int T)
{
if (N <= 0 || T <= 0)
throw new IllegalArgumentException("N and T must be greater than 0");
this.T = T;
Percolation percolation;
result = new double[T];
for (int t = 0; t < T; t++)
{
percolation = new Percolation(N);
int openSites = 0;
while (!percolation.percolates())
{
int i = StdRandom.uniform(N) + 1;
int j = StdRandom.uniform(N) + 1;
if (!percolation.isOpen(i, j))
{
percolation.open(i, j);
openSites++;
}
}
result[t] = (double) openSites / (N * N);
}
}
public double mean()
{
return StdStats.mean(result);
}
public double stddev()
{
if (T > 1) return StdStats.stddev(result);
else return Double.NaN;
}
public double confidenceLo()
{
return mean() - 1.96 * Math.sqrt(StdStats.var(result)) / Math.sqrt(T);
}
public double confidenceHi()
{
return mean() + 1.96 * Math.sqrt(StdStats.var(result)) / Math.sqrt(T);
}
public static void main(String[] args)
{
int N = Integer.parseInt(args[0]);
int T = Integer.parseInt(args[1]);
PercolationStats percolationStats = new PercolationStats(N, T);
StdOut.printf("%-23s = %f\n", "mean", percolationStats.mean());
StdOut.printf("%-23s = %f\n", "stddev", percolationStats.stddev());
StdOut.printf("%-23s = %f, %f\n", "95% confidence interval",
percolationStats.confidenceLo(),
percolationStats.confidenceHi());
}
}
..
import java.awt.Font;
public class PercolationVisualizer {
// draw N-by-N percolation system
public static void draw(Percolation perc, int N) {
StdDraw.clear();
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setXscale(0, N);
StdDraw.setYscale(0, N);
StdDraw.filledSquare(N/2.0, N/2.0, N/2.0);
// draw N-by-N grid
int opened = 0;
for (int row = 1; row <= N; row++) {
for (int col = 1; col <= N; col++) {
if (perc.isFull(row, col)) {
StdDraw.setPenColor(StdDraw.BOOK_LIGHT_BLUE);
opened++;
}
else if (perc.isOpen(row, col)) {
StdDraw.setPenColor(StdDraw.WHITE);
opened++;
}
else
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.filledSquare(col - 0.5, N - row + 0.5, 0.45);
}
}
// write status text
StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 12));
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.text(.25*N, -N*.025, opened + " open sites");
if (perc.percolates()) StdDraw.text(.75*N, -N*.025, "percolates");
else StdDraw.text(.75*N, -N*.025, "does not percolate");
}
public static void main(String[] args) {
In in = new In(args[0]); // input file
int N = in.readInt(); // N-by-N percolation system
// repeatedly read in sites to open and draw resulting system
Percolation perc = new Percolation(N);
draw(perc, N);
while (!in.isEmpty()) {
StdDraw.show(0); // turn on animation mode
int i = in.readInt();
int j = in.readInt();
perc.open(i, j);
draw(perc, N);
StdDraw.show(50); // pause for 100 miliseconds
}
}
}
البته برای اجرای این برنامه به کتابخانه StdLib نیاز خواهید داشت که به همراه فایلهای ورودی براتون میزارم :
http://uplod.ir/7m2sgvb3p4jg/percolation.rar.htm
پاسخ با نقل قول
