最近又回顾了一遍Coursera上的神课,普林斯顿大学教授Robert Sedgewick主讲的Algorithms. Week1中interview questions已经贴出来了,今天给大家分享的是Week1的assignment:Percolation.
链接:课程的Specification
这个作业的目的是通过蒙特卡洛来估算一个由n*n格子组成系统的渗透阈值。
何为渗透
在n*n中,一个格子有三种状态:
(1)开放状态open
(2)堵塞状态blocked
(3)开放且能渗透状态full
从系统顶端能通过开放状态的格子到达系统底端,即为渗透。
何为阈值
假设一个格子开放的概率为p,可知p=0时系统永不渗透,p=1时系统一定渗透。逐渐增加p值,可以获得渗透阈值。
代码部分
可以看出这个问题和老爷子讲的union-find离不开关系,本次作业就是利用Union-find来实现的。
仔细思考过后发现问题其实并不困难,我用了virtualTop和virtualBottoom,将virtualTop和第一行相连通,virtualBottom和最后一行相连通。最后只要判断virtualTop和virtualBottom有没有连通即可。但是跑了测试样例之后发现一个问题,也就是checklist里面提到的backwash。
通过一个WeightedQuickUnionUF似乎不能解决这个问题,因为我用了两个【手动狗头】一个WeightedQuickUnionUF是带有virtualTop和virtualBottom的,另一个只带有virtualTop。判断full的时候利用第二个WeightedQuickUnionUF,判断是否渗透则用第一个。
以下是percolation.java的代码。代码中还需注意的一点是我将virtualTop和virtualBottom分别放在了数组的前两位,这样计算其余格子的索引比较方便。
1 | import edu.princeton.cs.algs4.In; |
这样跑下来是能够获得100分的,但是bonus没有做到。为此还得继续改进。参考了forum中的回答之后,做出如下改动:
(1)只用一个WeightedQuickUnionUF
(2)将map类型改为byte。0表示堵塞,1表示open,2表示full
(3)需多多利用find()函数
(4)只加一个virtualTop
如果开放最后一行的格子,则赋值2,其余赋1.
如果任何一方的root是full的,则将双方Union后的root设为full。
更改后代码如下。
1 | import edu.princeton.cs.algs4.In; |