西安电子科技大学《算法设计与分析》上机题_霍红卫算法分析与设计笔记 - CSDN文库

需积分: 45 170 浏览量更新于2023-03-16 评论 4 收藏 153KB DOCX 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

实验题目

（一）渗透问题（Percolation）

使用合并-查找（union-nd）数据结构，编写程序通过蒙特卡罗模拟（Monte Carlo

simulation）来估计渗透阈值的值。

安装 Java 编程环境。按照以下各步指令，在你的计算机上（操作系统 Mac OS X

（http://algs4.cs.princeton.edu/mac）· Windows （http://algs4.cs.princeton.edu/windows）·

Linux （http://algs4.cs.princeton.edu/linux）安装 Java 编程环境。执行这些指令后，在你的

Java classpath 下会有 stdlib.jar and algs4.jar。前者包含库：从标准输入读数据、向标准输出

写数据以及向标准绘制绘出结果，产生随机数、计算统计量以及计时程序；后者包含了教

科书中的所有算法。

给定由随机分布的绝缘材料和金属材料构成的组合系统：金属材料占多大比例才能使组合

系统成为电导体？给定一个表面有水的多孔渗水地形（或下面有油），水将在什么条件下

能够通过底部排出（或油渗透到表面）？科学家们已经定义了一个称为渗透

（percolation）的抽象过程来模拟这种情况。

模型。我们使用 N×N 网格点来模型一个渗透系统。每个格点或是 open 格点或是

blocked 格点。一个 full site 是一个 open 格点，它可以通过一连串的邻近（左，右，上，

下）open 格点连通到顶行的一个 open 格点。如果在底行中有一个 full site 格点，则称

系统是渗透的。（对于绝缘/金属材料的例子，open 格点对应于金属材料，渗透系统有一

条从顶行到底行的金属路径，且 full sites 格点导电。对于多孔物质示例，open 格点对应

于空格，水可能流过，从而渗透系统使水充满 open 格点，自顶向下流动。）

问题。在一个著名的科学问题中，研究人员对以下问题感兴趣：如果将格点以空置概率 p 独立地设置为

open 格点（因此以概率 1-p 被设置为 blocked 格点），系统渗透的概率是多少？当 p = 0 时，系统不

会渗出; 当 p=1 时，系统渗透。下图显示了 20×20 随机网格（左）和 100×100 随机网格（右）的格

点空置概率 p 与渗滤概率。

- 1 -

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余7页未读，立即下载

评论0

feipooky

粉丝: 0
资源: 1

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈