算法上机报告.doc

算法 上机报告 班级：1403011 学号：14030110030 姓名： 付尧 1. 使用合并-查找数据结构，实现估计渗漏(Percolation)问题阈值的程序。 思路分析： 使用union-found 算法，利用quick-union方法，定义一个N*N的矩阵，依次从1-N*N编号，在模拟渗漏问题时采用一种流动的思想，当按序号增大的顺序一次判断该块是否被打开，按照老师课件上的提示在顶部和底部各设置一个点，顶部点和第一排所有点都联通，底部点和最后一排所有点都联通，流动完之后判断这两个点是否联通即可。 源代码： import java.util.ArrayList; import java.util.List; public class Percolation { private static int SITE_BLOCKED = -1; private int[][] wraper; private int N; private int openCounts = 0; int[][] topAndButtom; public Percolation(int N) //创建一个矩阵表示渗透图，每个图的格子初始化为被锁定状态，顶端行和底端行放到另外建立的2*N数组中 { this.N = N; wraper = new int[N][N]; topAndButtom = new int[2][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { wraper[i][j] = SITE_BLOCKED; if (i<2) { topAndButtom[i][j] = SITE_BLOCKED; } } } } public void open(int i, int j) { //检查坐标为(i, j)的点是否开启，如果没有开启，则将其开启。 //注意i，j的取值范围为1~N。此外，开启格子后，需要检查其上下左右的格子是否同样已经打开， if (!isOpen(i, j)) {//如果该点没打开 openCounts ++;//统计值+1 wraper[i][j] = i * N + j;//每个点的值初始化为当前点的坐标的hash值 if (isTopOrButtom(i)) topAndButtom[i/(N-1)][j] = wraper[i][j]; //开启格子后，需要检查其上下左右的格子是否同样已经打开，如果已经打开，则通过union()方法将两个格子连通起来；另外根据作业要求，需要首先检查是否越界， if ((j - 1) >= 0) { if (isOpen(i, j - 1)) //left { int pos = find(i, j - 1); union(pos / N, pos % N, i, j); } } if ((j + 1) < N) { if (isOpen(i, j + 1)) //right { int pos = find(i, j + 1); union(pos / N, pos % N, i, j); } } if ((i - 1) >= 0) { if (isOpen(i - 1, j)) //top { int pos = find(i - 1, j);//查找根节点 union(pos /