算法报告

西安电子科技大学

算法大作业

(2016

年度

)

实

验

报

告

实验名称：

算法的设计与分析

班级：

1403019

姓名：

张致远

学号：

西安电子科技大学《算法分析与设计》实验报告

2016

年度

一、实验内容

1.

使用合并

-

查找数据结构，实现估 计渗漏（

Percolation

）问题阈值的程序。

问题描述：

Write a program to estimate the value of the

percolation threshold

via Monte Carlo simulation.

Install a Java programming environment.

Install a Java

programming environment on your computer by following these

step-by-step instructions for your operating system [

Mac OS

X

·

Windows

·

Linux

]. After following these instructions, the

commands javac- algs4 and java-algs4 will classpath in both

and

: the former contains libraries for reading

data from

standard input

, writing data to

standard output

, drawing

results to

standard draw

, generating random numbers, computing

statistics, and timing programs; the latter contains all of the

algorithms in the textbook.

Percolation.

Given a composite systems comprised of randomly

distributed insulating and metallic materials: what fraction of the

materials need to be metallic so that the composite system is an

electrical conductor? Given a porous landscape with water on the

surface (or oil below), under what conditions will the water be able

to drain through to the bottom (or the oil to gush through to the

surface)? Scientists have defined an abstract process known as

percolation

to model such situations.

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

西安电子科技大学《算法分析与设计》实验报告

2016

年度

space through which water might flow, so that a system that

percolates lets water fill open sites, flowing from top to bottom.)

The problem.

In a famous scientific problem, researchers are

interested in the following question: if sites are independently set

to be open with probability

p

(and therefore blocked with

probability 1

?

p

), what is the probability that the system

percolates? When

p

equals 0, the system does not percolate; when

p

equals 1, the system percolates. The plots below show the site

vacancy probability

p

versus the percolation probability for 20-by-

20 random grid (left) and 100-by-100 random grid (right).

When

N

is sufficiently large, there is a

threshold

value

p

* such that

when

p

<

p

* a random

N

-by-

N

grid almost never percolates, and

when

p

>

p

*, a random

N

-by-

N

grid almost always percolates. No

mathematical solution for determining the percolation threshold

p

*

has yet been derived. Your task is to write a computer program to

estimate

p

*.

西安电子科技大学《算法分析与设计》实验报告

2016

年度

Percolation data type.

To model a percolation system, create a

data type Percolation with the following API:

西安电子科技大学《算法分析与设计》实验报告

2016

年度

public class Percolation {

public Percolation(int N)

public void open(int i, int j)

public boolean isOpen(int i, int j) public boolean isFull(int i, int j)

public boolean percolates()

public static void main(String[] args)

}

// create N-by-N grid, with all sites blocked

// open site (row i, column j) if it is not already // is site (row i,

column j) open?

// is site (row i, column j) full? // does the system percolate?

// test client, optional

By convention, the row and column indices

i

and

j

are integers

between 1 and

N

, where (1, 1) is the upper-left site: Throw an

IndexOutOfBoundsException if any argument to open(),

isOpen(), or isFull() is outside its prescribed range. The

constructor should throw an IllegalArgumentException if

N

≤

0.

The constructor should take time proportional to

N

2

; all methods

should take constant time plus a constant number of calls to the

union- find methods union(), find(), connected(), and count().

Monte Carlo simulation.

To estimate the percolation threshold,

consider the following computational experiment:

?

Initialize all sites to be blocked.

?

Repeat the following until the system percolates:

o

Choose a site (row

i

, column

j

) uniformly at random among all

blocked sites.

西安电子科技大学《算法分析与设计》实验报告

2016

年度

o

Open the site (row

i

, column

j

).

?

The fraction of sites that are opened when the system percolates

provides an estimate of the

percolation threshold.

For example, if sites are opened in a 20-by-20 lattice according to

the snapshots below, then our estimate of the percolation

threshold is 204/400 = 0.51 because the system percolates when

the 204th site is opened.

50 open sites 100 open sites 150 open sites 204 open sites

By repeating this computation experiment

T

times and averaging

the results, we obtain a more accurate estimate of the percolation

threshold. Let

x

t

be the fraction of open sites in computational

experiment

t

. The sample mean

μ

provides an estimate of the

percolation threshold; the sample standard deviation

σ

measures

the sharpness of the threshold.

Assuming

T

is sufficiently large (say, at least 30), the following

provides a 95% confidence interval for the percolation threshold:

To perform a series of computational experiments, create a data

type PercolationStats with the following API.

public class PercolationStats {

public PercolationStats(int N, int T) // perform T independent

computational experiments on

an N-by-N grid

西安电子科技大学《算法分析与设计》实验报告

2016

年度

}

public double mean()

public double stddev()

public double confidenceLo() public double confidenceHi() public

static void main(String[] args)

// sample mean of percolation threshold

// sample standard deviation of percolation threshold // returns

lower bound of the 95% confidence interval // returns upper

bound of the 95% confidence interval

// test client, described below

The constructor should throw a

lArgumentException if either

N

≤

0 or

T

≤

0.

Also, include a main() method that takes two

command-line arguments

N

and

T

, performs

T

independent computational experiments

(discussed above) on an

N

-by-

N

grid, and prints out the mean,

standard deviation, and the

95% confidence interval

for the

percolation threshold. Use

standard random

from our standard

libraries to generate random numbers; use

standard statistics

to

compute the sample mean and standard deviation.

分析设计：本题我的思路是构建 一个

N*N

的网格，开始将网格设计的全空，这

样必然无法渗漏。写一个

while

循环调用

unionfind

来判断改系统是否渗漏，如

果没有渗漏，则调用

isopen

函数来随即打开一个格子，再 次判断，直到能够渗

漏为止，记下打开格子的数目，利用大量的实验样本来求出渗漏的置 信区间

核心代码如下：

package

Al1;

import

ption;

西安电子科技大学《算法分析与设计》实验报告

2016

年度

/**

*

*

@author

zhangzhiyuan

*

*/

//

异常抛出

publicclass

IlleagalArgumentException

extends

IOException

{

privatestaticf inallong

serialVersionUID

= 1L;

IlleagalArgumentException()

{

}

}

System.

out

输入的行列值不符合要求

);

(0);

此为异常保护。

package

Al1;

publicclass

UnionFind

//

加权带压缩路径

quick- union

{

privateint

[]

id

;

privateint

count

;

privateint

openco unt

=0;

privateint

[]

sz

;

privateboolean

[]

openflag

;

privateint

scale

;

public

UnionFind(

int

N

)

{

scale

=

N

;

N

=

N

*

N

;

count

=

N

;

id

=

newint

[

N

+2];

sz

=

newint

[

N

+2];

openflag

=

newboo lean

[

N

+2];

for

(

int

i

=0;

i

<

N

+2;

i

++)

{

< /p>

id

[

i

]=< /p>

i

;

sz

[

i< /p>

]=1;

openflag

[

i

] =

false

;

}

< /p>

openflag

[

N

< br>] =

true

;

openflag

[

N

+1] =

true

;

}

publicvoid

open(

int

i

,

int

j

)

{

int

index

= (