西安电子科技大学算法上机报告.docx

西安电子科技大学（2018年度） 算法分析 实验报告实验名称：渗透实验班级：1603012 名： 学号： 实验一：渗透问题（Percolation） 一、实验题目 使用合并-查找（union-find）数据结构，编写程序通过蒙特卡罗模拟（MonteCarlosimulation）来估计渗透阈值的值。 给定由随机分布的绝缘材料和金属材料构成的组合系统:金属材料占多大比例才能使组合系统成为电导体？给定一个表面有水的多孔渗水地形（或下面有油），水将在什么条件下能够通过底部排出（或油渗透到表面）？科学家们已经定义了一个称为渗透（percolation）的抽象过程来模拟这种情况。 percokitesdoes响gog模型：我们使用NXN网格点来模型一个渗透系统。每个格点或是open格点或是blocked格点。一个fullsite是一个open格点，它可以通过一连串的邻近（左，右，上，下）open格点连通到顶行的一个open格点。如果在底行中有一个fullsite格点，则称系统是渗透的。（对于绝缘/金属材料的例子，o^t^en格点对应于金属材料，渗透系统有一条从顶行到底行的金属路径，且fullsites格点导电。对于多孔物质示例，open格点对应于空格，水可能流过，从而渗透系统使水充满 percokitesdoes响gog 血\/opensiteconnectedfol?noopensite,contiectearotap问题：在一个著名的科学问题中，研究人员对以下问题感兴趣：如果将格点以空置概率刀独立地设置为open格点（因此以概率1-p被设置为blocked 问题：在一个著名的科学问题中，研究人员对以下问题感兴趣：如果将格点以空置概率刀独立地设置为open格点（因此以概率1-p被设置为blocked格点），系统渗透的概率是多少？当p=0时，系统不会渗出；当p=1时，系统渗透。下图显示了20X20随机网格和100X100随机网格的格点空置概率p与渗滤概率。 当N足够大时，存在阈值p*，使得当pp*，随机NxN网格几乎不会渗透，并且当pp*时，随机NxN网格几乎总是渗透。尚未得出用于确定渗滤阈值p*的数学解。你的任务是编写一个计算机程序来估计p*。 Percolation数据类型:模型化一个Percolation系统，创建含有以下API的数据类型Percolation。 publicclassPercolation{ publicPercolation(intN) publicvoidopen(inti,intj) publicbooleanisOpen(inti,intj) publicbooleanisFull(inti,intj)publicbooleanpercolates() publicstaticvoidmain(String[]args) //createN-by-Ngrid,withallsitesblocked //opensite(rowi,columnj)ifitisnotalready //issite(rowi,columnj)open? //issite(rowi,columnj)full? //doesthesystempercolate? //testclient,optional } 约定行/列顶下标在1和N之间，其中(1,1)为左上格点位置:如果open(),isOpen。,orisFull。不在这个规定的范围，则抛出IndexOutOfBoundsException例夕卜。如果N0，构造函数应该抛出IllegalArgumentException例外。构造函数应该与N2成正比。所有方法应该为常量时间加上常量次调用合并-查找方法union。，find。,connected。,andcount。。 蒙特卡洛模拟(MonteCarlosimulation).要估计渗透阈值，考虑以下计算实验: ?初始化所有格点为blocked。 ?重复以下操作直到系统渗出： o在所有blocked的格点之间随机均匀选择一个格点(rowi,columnj)。 o设置这个格点(rowi,columnj)为open格点。 ?open格点的比例提供了系统渗透时渗透阈值的一个估计。 例如，如果在20X20的网格中，根据以下快照的open格点数，那么对渗滤阈值的估计是204/400=0.51，因为当第204个格点被open时系统渗透。 50opensites100opensites150opensites204opensites通过重复该计算实验T次并对结果求平均值，我们获得了更准确的渗滤阈值估计。令xt是第t次计算实验中 50opensites 100opensites 150opensites 204opensites 日—兀决