算法上机报告.

1、算法上机报告上机题目：1. 使用合并-查找数据结构，实现估计渗漏(Percolation)问题阈值的程序。思路分析：使用union-found 算法，利用quick-union方法，定义一个N*N的矩阵，依次从1-N*N编号，在模拟渗漏问题时采用一种流动的思想，当按序号增大的顺序一次判断该块是否被打开，按照老师课件上的提示在顶部和底部各设置一个点，顶部点和第一排所有点都联通，底部点和最后一排所有点都联通，流动完之后判断这两个点是否联通即可。源代码：package Assignments;import java.util.Scanner;public class Percolationpriva

2、te 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 Weighted

3、QuickUnionUF(N * N + 1);alreadyPercolates = false;row = N;col = N;matrix = new booleanN * N + 1;private void validate(int i, int j)if (i row)throw new IndexOutOfBoundsException(row index i out of bounds);if (j col)throw new IndexOutOfBoundsException(col index j out of bounds);public void open(int i,

4、 int j)validate(i, j);int curIdx = (i - 1) * col + j;matrixcurIdx = 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 + dxdir;int posY = j + dydir;if (p

5、osX = 1 & 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 (wq

6、uUFTop.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 = true;return true;return false;public static void main(String args)Percolation perc = new Percolation(2); perc.o

7、pen(1, 1); perc.open(1, 2); perc.open(2, 1); System.out.println(perc.percolates();package Assignments;import java.util.Scanner;public class PercolationStatsprivate double x;private int expTimes;public PercolationStats(int N, int T)if (N = 0 | T = 0)throw new IllegalArgumentException(Illeagal Argumen

8、t);x = new doubleT + 1;expTimes = T;for (int i = 1; i = T; +i)Percolation perc = new Percolation(N);boolean isEmptySiteLine = new booleanN + 1;int numOfLine = 0;while (true)int posX, posY;doposX = StdRandom.uniform(N) + 1;posY = StdRandom.uniform(N) + 1; while (perc.isOpen(posX, posY);perc.open(posX

9、, posY);xi += 1;if (!isEmptySiteLineposX)isEmptySiteLineposX = true;numOfLine+;if (numOfLine = N)if (perc.percolates()break;xi = xi / (double) (N * N);public double mean()double mu = 0.0;for (int i = 1; i = expTimes; +i)mu += xi;return mu / (double) expTimes;public double stddev()if (expTimes = 1)re

10、turn Double.NaN;double sigma = 0.0;double mu = mean();for (int i = 1; i = expTimes; +i)sigma += (xi - mu) * (xi - mu);return Math.sqrt(sigma / (double) (expTimes - 1);public double confidenceLo()double mu = mean();double sigma = stddev();return mu - 1.96 * sigma / Math.sqrt(expTimes);public double c

11、onfidenceHi()double mu = mean();double sigma = stddev();return mu + 1.96 * sigma / Math.sqrt(expTimes);public static void main(String args)int N = Integer.parseInt(args0); int T = Integer.parseInt(args1); PercolationStats percStats = new PercolationStats(N, T); StdOut.printf(mean = %fn, percStats.me

12、an(); /StdOut.printf(stddev = %fn, percStats.stddev(); StdOut.printf(95% confidence interval =( %f, %f )n, percStats.confidenceLo(), percStats.confidenceHi();运行结果：2. You are asked to write and perform an empirical complexity analysis of the following sorting algorithms:/实现并做性能分析比较(1) Insertion sort;

13、(2) Merge sort (please write the recursive merge sort and bottom-up mergesort);(3) Quick sort (please write a randomized quicksort method as covered in class);(4) Quicksort with Dijkstra 2-way partitioning;(5)* Quicksort with Bentley-McIlroy 3-way partitioning.Note that the question with a star is o

14、ptional.源代码：package algo;import java.util.*;class statisticsstatistics ()run_time = 0;run_count = 0;assign_count = 0;statistics (long ru,int run,int as)run_time = ru;run_count = run;assign_count = as;statistics (long ru,int run,int as,ArrayList ls)run_time = ru;run_count = run;assign_count = as;res

15、= ls;long run_time;int run_count;int assign_count;ArrayList res;class Sort_Collstatic int min (Integer lhs,Integer rhs)return lhsrhs? lhs:rhs;static statistics insertion_sort (ArrayList lst)long beg_time = System.currentTimeMillis();int assign_count = 0,run_count = 0;int len = lst.size();for (int i=

16、1,j=0;i=0;-j)+run_count;if (lst.get(j)elem)lst.set(j+1, lst.get(j);+assign_count;elsebreak;lst.set(j+1, elem);return new statistics (System.currentTimeMillis()-beg_time,run_count,assign_count,lst);/)static statistics merge (ArrayList lst,int beg,int mid,int en)long beg_time = System.currentTimeMilli

17、s();int run_count=0,assign_count=0;ArrayList tmp = new ArrayList (lst);for (int i=beg,l=beg,r=mid;i=mid)lst.set(i,tmp.get(r);+r;else if (r=en)lst.set(i,tmp.get(l);+l;else if (tmp.get(l)tmp.get(r)lst.set(i,tmp.get(l);+l;elselst.set(i, tmp.get(r);+r;return new statistics (System.currentTimeMillis()-be

18、g_time,run_count,assign_count);/)static statistics merge_sort (ArrayList lst,int beg,int en)statistics s0 = new statistics (),s1 = new statistics (),s2 = new statistics ();long beg_time = System.currentTimeMillis();if (enbeg+1)int mid = (beg+en)/2;s0 = merge_sort (lst,beg,mid);s1 = merge_sort (lst,m

19、id,en);s2 = merge (lst,beg,mid,en);return new statistics (System.currentTimeMillis()-beg_time,s0.run_count+s1.run_count+s2.run_count,s0.assign_count+s1.assign_count+s2.assign_count,lst);static statistics merge_sort_u (ArrayList lst,int beg,int en)statistics s0 = new statistics ();long beg_time = Sys

20、tem.currentTimeMillis();for (int stp=1;stpen-beg;stp*=2)for (int i=beg;(i+1)*stpen;i+=2)statistics s1 = merge (lst,beg+i*stp,beg+(i+1)*stp,min(beg+(i+2)*stp,en);s0.assign_count += s1.assign_count;s0.run_count += s1.run_count;return new statistics (System.currentTimeMillis()-beg_time,s0.run_count,s0.

21、assign_count,lst);static int random_part (ArrayList lst,int beg,int en,statistics s)int run_count = 0,assign_count = 0;/* Choose a random number and switch it with last number */Random rnd = new Random ();int r = rnd.nextInt(en-beg)+beg;int tem = lst.get(en-1);lst.set(en-1, lst.get(r);lst.set(r, tem

22、);int key = lst.get(en-1);int i=beg;for (int j=beg;jen-1;+j)+s.run_count;if (lst.get(j)=key)int v = lst.get(j);lst.set(j, lst.get(i);lst.set(i, v);s.assign_count += 2;+i;lst.set(en-1, lst.get(i);lst.set(i, key);return i;/)static statistics quick_sort (ArrayList lst,int beg,int en)statistics s0 = new

23、 statistics (),s1 = new statistics (),s2 = new statistics ();long beg_time = System.currentTimeMillis();if (enbeg)int key = random_part (lst,beg,en,s0);s1 = quick_sort (lst,beg,key);s2 = quick_sort (lst,key+1,en);return new statistics (System.currentTimeMillis()-beg_time,s0.run_count+s1.run_count+s2

24、.run_count,s0.assign_count+s1.assign_count+s2.assign_count,lst);/)static statistics dijkstra_sort (ArrayList lst,int beg,int en)long beg_time = System.currentTimeMillis();int run_count = 0,assign_count = 0;statistics s1 = new statistics (),s2 = new statistics ();if (enbeg+1)int i=beg,le=beg,gt=en,ke

25、y=lst.get(en-1);while (igt)+run_count;if (lst.get(i)key)-gt;int t = lst.get(i);lst.set(i,lst.get(gt);lst.set(gt,t);assign_count += 2;else+i;s1 = dijkstra_sort (lst,beg,le);s2 = dijkstra_sort (lst,gt,en);return new statistics (System.currentTimeMillis()-beg_time,run_count+s1.run_count+s2.run_count,as

26、sign_count+s1.assign_count+s2.assign_count,lst);static boolean test_sort_res (ArrayList lst)boolean rig = true;Integer last_num = new Integer (0);for (int i=0;ilst.size();+i)if (i = 0)last_num = lst.get(0);elseif (lst.get(i) last_num)System.out.println (Array unordered);rig = false;if (rig)System.ou

27、t.println (Result check valid);return rig;static ArrayList generate_num (int size)Random rnd = new Random ();ArrayList res = new ArrayList ();for (int i=0;isize;+i)res.add(rnd.nextInt();return res;public class Sort static void test_sort_function ()ArrayList lst = Sort_Coll.generate_num(50000);ArrayL

28、ist lst_c = (ArrayList)lst.clone ();statistics s0 = Sort_Coll.insertion_sort(lst_c);System.out.println (Inserition_sort: Run_time:+s0.run_time+ Run_Count:+s0.run_count+ Assign_Count:+s0.assign_count);Sort_Coll.test_sort_res(s0.res);lst_c = (ArrayList)lst.clone ();s0 = Sort_Coll.merge_sort(lst_c, 0,

29、lst_c.size();System.out.println (Merge_sort: Run_time:+s0.run_time+ Run_Count:+s0.run_count+ Assign_Count:+s0.assign_count);Sort_Coll.test_sort_res(s0.res);lst_c = (ArrayList)lst.clone ();s0 = Sort_Coll.merge_sort_u (lst_c, 0, lst_c.size();System.out.println (Merge_sort_u: Run_time:+s0.run_time+ Run

30、_Count:+s0.run_count+ Assign_Count:+s0.assign_count);Sort_Coll.test_sort_res(s0.res);lst_c = (ArrayList)lst.clone ();s0 = Sort_Coll.quick_sort(lst_c, 0, lst_c.size();System.out.println (Quick_sort: Run_time:+s0.run_time+ Run_Count:+s0.run_count+ Assign_Count:+s0.assign_count);Sort_Coll.test_sort_res

31、(s0.res);lst_c = (ArrayList)lst.clone ();s0 = Sort_Coll.dijkstra_sort(lst_c, 0, lst_c.size();System.out.println (Dijkstra: Run_time:+s0.run_time+ Run_Count:+s0.run_count+ Assign_Count:+s0.assign_count);Sort_Coll.test_sort_res(s0.res);public static void main(String args) / TODO Auto-generated method

32、stub/*ArrayList lst = Sort_Coll.generate_num(10);ArrayList lst_c = (ArrayList)lst.clone ();/*System.out.println (Sort_Coll.insertion_sort(lst_c);*/*System.out.println (Sort_Coll.merge_sort(lst_c, 0, lst.size();*/*System.out.println (Sort_Coll.merge_sort_u(lst_c, 0, lst.size();*/*Sort_Coll.test_sort_

33、res(Sort_Coll.insertion_sort(lst_c);System.out.println (Sort_Coll.quick_sort(lst_c, 0, lst.size();*/*System.out.println (Sort_Coll.dijkstra_sort(lst_c, 0, lst_c.size();*/*Sort_Coll.test_sort_res(Sort_Coll.dijkstra_sort(lst_c, 0, lst_c.size();*/*System.out.println (lst);*/test_sort_function ();运行结果：3

34、. 实现Dijkstra单源点最短路径算法，并应用于Map Routing/GIS问题。思路分析： 根据Dijkstr算法寻找最短路径。源代码：package dijistala;import java.util.ArrayList;import java.util.TreeMap; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; class Point private int id;/ 点的id private boolean flag = false;/

35、 标志是否被遍历 int sum;/ 记录总的点个数 private TreeMap thisPointMap = new TreeMap();/ 该点到各点的距离。 BufferedReader bufr = new BufferedReader(new InputStreamReader(System.in); Point(int sum) / 构造函数 带有顶点个数 this.sum = sum; public void setId(int id) / 设置顶点id this.id = id; public int getId() / 获得顶点id return this.id; pub

36、lic void changeFlag() / 修改访问状态。 this.flag = true; public boolean isVisit() / 查看访问状态 return flag; public void setLenToOther()throws IOException/ 初始化改点到各顶点的距离。 System.out.println(=请输入顶点 + (this.id + 1) + 至其他各顶点的边距=); for (int i = 0; i sum; i+) if (i = this.id) thisPointMap.put(this.id, 0); else System

37、.out.print(至 顶点 + (i + 1) + 的距离 ：); boolean flag =true; int len = 0; while(flag) try len = Integer.valueOf(bufr.readLine(); flag = false; catch (NumberFormatException e) System.out.print(输入有误，请重新输入：); ; thisPointMap.put(i, len); / 该点到顶尖id的 距离。 public int lenToPointId(int id) return thisPointMap.get(id)