算法上机报告.doc

算 法上 机 报 告 上机题目 1. 使用合并-查找数据结构，实现估计渗漏(Percolation)问题阈值的程序。 思路分析 使用union-found 算法，利用quick-union方法，定义一个N*N的矩阵，依次从1-N*N编号，在模拟渗漏问题时采用一种流动的思想，当按序号增大的顺序一次判断该块是否被打开，按照老师课件上的提示在顶部和底部各设置一个点，顶部点和第一排所有点都联通，底部点和最后一排所有点都联通，流动完之后判断这两个点是否联通即可。 源代码 package Assignments; import java.util.Scanner; public class Percolation { private boolean[] matrix; private int row, col; private WeightedQuickUnionUF wquUF; private WeightedQuickUnionUF wquUFTop; private boolean alreadyPercolates; public Percolation(int N) { if (N 1) throw new IllegalArgumentException(Illeagal Argument); wquUF = new WeightedQuickUnionUF(N * N + 2); wquUFTop = new WeightedQuickUnionUF(N * N + 1); alreadyPercolates = false; row = N; col = N; matrix = new boolean[N * N + 1]; } private void validate(int i, int j) { if (i 1 || i row) throw new IndexOutOfBoundsException(row index i out of bounds); if (j 1 || j col) throw new IndexOutOfBoundsException(col index j out of bounds); } public void open(int i, int j) { validate(i, j); int curIdx = (i - 1) * col + j; matrix[curIdx] = true; if (i == 1) { wquUF.union(curIdx, 0); wquUFTop.union(curIdx, 0); } if (i == row) { wquUF.union(curIdx, row * col + 1); } int[] dx = { 1, -1, 0, 0 }; int[] dy = { 0, 0, 1, -1 }; for (int dir = 0; dir 4; dir++) { int posX = i + dx[dir]; int posY = j + dy[dir]; if (posX = row posX = 1 posY = row posY = 1 isOpen(posX, posY)) { wquUF.union(curIdx, (posX - 1) * col + posY); wquUFTop.union(curIdx, (posX - 1) * col + posY); } } } public boolean isOpen(int i, int j) { validate(i, j); return matrix[(i - 1) * col + j]; } public boolean isFull(int i, int j) { validate(i, j); int curIdx = (i - 1) * col + j; if (wquUFTop.find(curIdx) == wquUFTop.find(0)) return true; return false; } public boolean percolates() { if (alreadyPercolates) return true; if (wquUF.find(0) == wquUF.find(row * col + 1)) { alreadyPercolates