算法课程报告.doc

算法上机报告实验题目一题目要求：使用合并 - 查找数据结构，实现估计渗漏（Percolation）问题阈值的程序。我们的模型使用网站的N-by-N坐标渗滤系统。每个站点是打开或阻塞。一个完整的网站是一个开放的网站，可以通过周边（左，右，上，下）打开网站链被连接到一个开放的网站上排。我们说的渗滤系统如果在底部行中的完整的站点。换句话说，一个系统渗滤如果我们填连接到顶部行的所有公开的网站和该进程填充在底部行一些开放部位。（对于绝缘/金属材料实例，开放位置对应于金属材料，使得渗透的系统具有从顶部到底部的金属路径，全部位点导电。对于多孔物质示例，开放位点对应于空白空间水可能流过，使得渗透的系统允许水填充开放位点，从顶部流到底部。）当N是足够大的，有一个阈值p*，使得当pP*，一个随机N-by-N坐标几乎总是渗滤液。用于确定渗透阈值P*没有数学溶液尚未而得。你的任务是写来估计P*的计算机程序，并且使用程序计算出数据的标准差和95%置信区间的上界和下界。题目分析：使用QuickUnion算法来实现该程序。渗漏问题可以抽象为创建一个N*N的方格组，对这N*N个小格使用Quick算法进行连接。初始情况下，所有的格子均设置关闭状态，每次随机开放一个格子，对格子的上下左右的邻居进行开放判断，并且进行连接。当第一行的格子和最后一行的格子存在根节点相同的格子时，表明已经有一个连通分量实现了从顶部到底部的连接，即系统发生了渗漏。为了减少比较次数，我们可以在第一行和最后一行抽像出Begin和End两个格子，每次只需比较这两个格子的根节点是否相同即可。程序主框架：public class Percolation /构造函数public Percolation（int N）/创建N-N网格，所有网站被阻止/打开第i行j列的格子public void open（int i，int j）/判断指定格子是否开放public boolean isOpen（int i，int j/判断指定格子是否处于已经有水状态public boolean isFull（int i，int j）/系统是否已经渗漏public boolean percolates（）/主函数输出结果public static void main（String args）程序详细代码：package Percolation;import java.util.Scanner;import edu.princeton.cs.algs4.*;public class Percolation/布尔数组记录每个小格是否开放private boolean matrix; /行数列数private int row, col;private WeightedQuickUnionUF wquUF;private boolean alreadyPercolates;public Percolation(int N)/对输入的N进行合法性检测，不合法抛出异常 if (N 1) throw new IllegalArgumentException(Illeagal Argument); / wquUF = new WeightedQuickUnionUF(N*N+2); /设置判断系统是否已经渗漏的标志量 alreadyPercolates = false; row = N; col = N; /创建的boolean型数组，标志每个方格是否开放 matrix = new booleanN*N+1;/i,j是否在方框里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); /获取i行j列的小格，将他打开public void open(int i, int j) validate(i, j); int curIdx = (i-1)*col + j; matrixcurIdx = true; /如果是第一行的格子和0号连接起来 if (i = 1) wquUF.union(curIdx, 0); /如果是最后一行的话，将他们和wquUF连接起来 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 (posX = 1 & posY = 1 & isOpen(posX, posY) wquUF.union(curIdx, (posX-1)*col+posY); /判断小格是否已经开放public boolean isOpen(int i, int j) validate(i, j); return matrix(i-1)*col + j;/判断i行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 = true; return true; return false;/主函数public static void main(String args)System.out.println(请输入矩阵的规模和运算分次数);/创建一个输入流Scanner in = new Scanner(System.in);int N,count;int sum = 0;N= in.nextInt();count = in.nextInt();double answer = 0;double result = new doubleN;for(int temp=0; tempcount; temp+)sum = 0;/输入0跳出循环，if (N = 0) break;elsePercolation perc = new Percolation(N);while(!perc.percolates()/渗透/随机设定i和j来产生一个小格int i = (int)(Math.random()*N+1);int j = (int)(Math.random()*N+1);/如果对应的格子没有开放的话，打开 if(!perc.isOpen(i, j)perc.open(i, j);sum+=1; resulttemp = (double)sum/(N*N); answer = answer + (double)sum/(N*N);double weight = 0;answer = answer/count;System.out.println(answer);for(int i=0;icount; i+)resulti -= answer;resulti = (resulti * resulti);weight += resulti;System.out.println(渗透发生的平均概率是：+answer);weight = Math.sqrt(weight/count);System.out.println(标准差：+weight);double a = answer - weight*1.96/count;double b = answer + weight*1.96/count;System.out.println(95%置信区间为：+a+,+b+);心得体会渗漏系统这个程序，将模型抽象为对N*N个节点运用QuickUnion算法进行连接的问题。当起始行和末行处于同一个连通分量中时，系统便达到了连通。通过编写这个程序，熟练掌握了加权QuickUnion算法，并且了解了实现过程中一些要注意的细节问题。通过这个算法，可以实现对百万级别的数据进行快速运算，深刻体会到了好的算法对于程序的重要性。实验题目二、题目要求：你被要求写和执行下列排序算法进行了实证分析的复杂性：/实现并做性能分析比较（1）插入排序;（2）合并排序（请写递归合并排序和自下而上合并）;（3）快速排序（请写上类中的随机快速排序方法）;（4）Dijkstra双向分区快速排序;（5）*使用Bentley-McIlroy 3路分区快速排序。题目分析：1、实现五个排序，并且对排序过程进行结果分析。为了便于统一对排序方法进行分析，首先创建一个测试类，该类具有程序运行时间，循环次数和赋值次数三个数据成员作为考核排序性能的参数。2、根据五个排序的原理，逐个编写程序，并且进行调用分析程序的效率。 插入排序是基于已经有序的数组进行逐个插入的排序方法。 归并排序运用减治的思想来将排序过程简化，将较小的有序 数组逐渐合并为大的有序数组。快速排序：快速排序取定关键值之后，从左往右按照关键值的大小，将其余值排在关键值的左侧和右侧，依次递归直至数组有序。双向分区快速排序：思想与上一种实现相同，只是使用不同的划分策略。使用left和right将数组划分成三部分，left之前的部分为小于等于划分元素P的值，right之后的部分为大于划分元素P的值，left和right之间的部分是没有进行划分的区域。外循环使得left自左向右遍历，同时right自右向左遍历，在这个过程中当left遇见大于P的值则停止，等待right遇见小于等于P的值又停止之后，交换他们的值，这个循环在left和right相遇或者交叉之后停止。最后交换ar和left的值，并返回left；代码的具体实现：package sorting;import java.util.ArrayList;/排序的测试类public class TestFun long run_time;int run_count;int assign_count;ArrayList res;public TestFun() / TODO Auto-generated constructor stubrun_time = 0;run_count = 0;assign_count = 0;TestFun(long ru,int run,int as)run_time = ru;run_count = run;assign_count = as;TestFun (long ru,int run,int as,ArrayList ls)run_time = ru;run_count = run;assign_count = as;res = ls;package sorting;import java.util.*;class Sort_Collstatic int min (Integer lhs,Integer rhs)return lhsrhs? lhs:rhs;/插入排序static TestFun insertion_sort (ArrayList lst)long beg_time = System.currentTimeMillis();int assign_count = 0,run_count = 0;int len = lst.size();for (int i=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 TestFun (System.currentTimeMillis()-beg_time,run_count,assign_count,lst);/归并排序static TestFun merge (ArrayList lst,int beg,int mid,int en)long beg_time = System.currentTimeMillis();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 TestFun (System.currentTimeMillis()-beg_time,run_count,assign_count);/地柜static TestFun merge_sort (ArrayList lst,int beg,int en)TestFun s0 = new TestFun (),s1 = new TestFun (),s2 = new TestFun ();long beg_time = System.currentTimeMillis();if (enbeg+1)int mid = (beg+en)/2;s0 = merge_sort (lst,beg,mid);s1 = merge_sort (lst,mid,en);s2 = merge (lst,beg,mid,en);return new TestFun (System.currentTimeMillis()-beg_time,s0.run_count+s1.run_count+s2.run_count,s0.assign_count+s1.assign_count+s2.assign_count,lst);/下 上static TestFun merge_sort_u (ArrayList lst,int beg,int en)TestFun s0 = new TestFun ();long beg_time = System.currentTimeMillis();for (int stp=1;stpen-beg;stp*=2)for (int i=beg;(i+1)*stpen;i+=2)TestFun 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 TestFun (System.currentTimeMillis()-beg_time,s0.run_count,s0.assign_count,lst);/快速排序static int random_part (ArrayList lst,int beg,int en,TestFun 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);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 TestFun quick_sort (ArrayList lst,int beg,int en)TestFun s0 = new TestFun (),s1 = new TestFun (),s2 = new TestFun ();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 TestFun(System.currentTimeMillis()-beg_time,s0.run_count+s1.run_count+s2.run_count,s0.assign_count+s1.assign_count+s2.assign_count,lst);/迪杰斯特拉static TestFun dijkstra_sort (ArrayList lst,int beg,int en)long beg_time = System.currentTimeMillis();int run_count = 0,assign_count = 0;TestFun s1 = new TestFun (),s2 = new TestFun ();if (enbeg+1)int i=beg,le=beg,gt=en,key=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 TestFun (System.currentTimeMillis()-beg_time,run_count+s1.run_count+s2.run_count,assign_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.out.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(10000);ArrayList lst_c = (ArrayList)lst.clone ();TestFun s0 = Sort_Coll.insertion_sort(lst_c);System.out.println (Inserition_sort:+n+t+Run_time:+s0.run_time+n+t+Run_Count:+s0.run_count+n+t+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, lst_c.size();System.out.println (Merge_sort:+n+t+Run_time:+s0.run_time+n+t+Run_Count:+s0.run_count+n+t+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:+n+t+Run_time:+s0.run_time+n+t+Run_Count:+s0.run_count+n+t+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:+n+t+Run_time:+s0.run_time+n+t+Run_Count:+s0.run_count+n+t+Assign_Count:+s0.assign_count);Sort_Coll.test_sort_res(s0.res);lst_c = (ArrayList)lst.clone ();s0 = Sort_Coll.dijkstra_sort(lst_c, 0, lst_c.size();System.out.println (Dijkstra:+n+t+Run_time:+s0.run_time+n+t+Run_Count:+s0.run_count+n+t+Assign_Count:+s0.assign_count);Sort_Coll.test_sort_res(s0.res);public static void main(String args) test_sort_function ();心得体会：通过编写这五个不同的排序，并且对其实现，了解到了五个不同的排序算法的运行时间和比较次数等性能参数，从排序的结果中可以看到，插入排序的性能和快速排序的性能相差很大，快速排序的时间应该在NlgN的级别上，但是遇到已经大致有序的数组时，他的性能会变得比较差，与插入排序大致相同。题目三、迪杰斯特拉算法求最短路径题目要求：实现经典的Dijkstra的最短路径算法并优化它的地图。这样的算法广泛用于地理信息系统（GIS），包括MapQuest和基于GPS的汽车导航系统。测试该文件usa.txt包含87575交叉口和美国大陆121961道路。图表非常稀疏 - 平均度为2.8。您的主要目标应该是快速回答这个网络上的顶点对的最短路径查询。根据两个顶点是相邻还是相距较远，您的算法可能会有不同的执行效果。我们提供测试这两种情况的输入文件。您可以假设所有的x和y坐标都是0到10,000之间的整数。题目分析：迪杰斯特拉算法是典型最短路径算法，用于计算图或网中某个特定顶点到其他所有顶点的最短路径。主要特点是以起始点为中心向外，层层扩展，直到扩展覆盖所有顶点。在迪杰斯特拉算法中，每次找到距离目标点最近的点，将其取出，然后寻找下一个最近的点，当发现新加入的点可以使原来的路径有更短的路径时，可以调用松弛函数，进行修改最短路径。算法的数据结构基础是，基于堆维护的优先队列，每次从中取出优先级最高的点，即最近的点然后进行链接。实现过程，从txt文件中读出点的编号和位置信息，很据给出的通路情况来计算有路两点之间的距离信息，进行连接。题目代码：package Dijkstra;import edu.princeton.cs.algs4.BlackFilter;import edu.princeton.cs.algs4.DirectedEdge;import edu.princeton.cs.algs4.EdgeWeightedDigraph;import edu.princeton.cs.algs4.In;import edu.princeton.cs.algs4.IndexMinPQ;import edu.princeton.cs.algs4.RedBlackBST;import edu.princeton.cs.algs4.Stack;import edu.princeton.cs.algs4.StdDraw;import edu.princeton.cs.algs4.StdIn;import edu.princeton.cs.algs4.StdOut;public class Dijkstra private DirectedEdge edgeTo;private IndexMinPQ pq;private double distTo;public Dijkstra() / TODO Auto-generated constructor stubpublic Dijkstra(EdgeWeightedDigraph G, int s)for (DirectedEdge e : G.edges() if (e.weight() 0)/检测 throw new IllegalArgumentException(edge + e + has negative weight); edgeTo = new DirectedEdgeG.V(); distTo = new doubleG.V(); for (int v = 0; v G.V(); v+) distTov = Double.POSITIVE_INFINITY; /权值初始化设为无穷大 distTos = 0.0; / relax vertices in order of distance from s pq = new IndexMinPQ(G.V(); pq.insert(s, distTos); while (!pq.isEmpty() relax(G,pq.delMin(); private void relax(EdgeWeightedDigraph G, int v) for(DirectedEdge e :G.adj(v) int w = e.to();if (distTow distTov + e.weight() distTow = distTov + e.weight();edgeTow = e;if (pq.contains(w) pq.decreaseKey(w, distTow);else pq.insert(w, distTow); public double distTo(int v) return distTov; /油路 public boolean hasPathTo(int v) return distTov Double.POSITIVE_INFINITY; public Iterable pathTo(int v) if (!hasPathTo(v) return null; Stack path = new Stack(); for (DirectedEdge e = edgeTov; e != null; e = edgeToe.from() path.push(e); return path; public void getFunction(int beginSite,int aimSite) In in = new In(usa.txt); /点的数量和边的数量 读 int VertexSum = in.readInt(); int edgeSum = in.readInt(); int Vertex = new intVertexSum; int vGetx = new intVertexSum; int vGety = new intVertexSum; /创建具有VertexSum个点的加权图 EdgeWeightedDigraph G = new EdgeWeightedDigraph(VertexSum); for(int i= 0;iVertexSum;i+) Vertexi =in.readInt(); vGetxi = in.readInt(); vGetyi = in.readInt(); for(int i=0;iedgeSum;i+) int v=in.readInt(); int w=in.readInt(); double weight = Math.sqrt(vGetxv-vGetxw)*(vGetxv-vGetxw) +(vGetyv-vGetyw)*(vGetyv-vGetyw); G.addEdge(new DirectedEdge(v, w, weight); int destinationV = aimSite; int startingV = beginSite; Dijkstra sp = new Dijkstra(G, startingV); Iterable path = sp.pathTo(destinationV); if(sp.hasPathTo(destinationV) System.out.println(sp.pathTo(destinationV); else System.out.println(两个点之间没有通路); public static void main(String args) int begin = 0,end = 0; In in = new In(); Dijkstra dijkstra = new Dijkstra(); while(true) System.out.println(输入起始地址和结束地址进行计算:); begin = in.readInt(); end = in.readInt(); dijkstra.getFunction(begin, end); 心得体会：编写程序，实现了迪杰斯特拉求最短路径的算法，对于在图上求最短距离，例如GPS导航等模型有了更多认识。迪杰斯特拉算法是贪心算法中的著名一例，通过每次取出最短路径的点，直至实现所有路径的连通这个过程，最终实现了目标点到其余点的最短路径的求解。通过上机，掌握了最短路径的求法，也对这种算法的思想了更多了解。题目四 哈弗曼编码题目要求：实现霍夫曼编码，对于给定的字符串进行压缩，并且将编制成的二进制码输出。题目分析：理解霍夫曼树的原理。对于字符串中出现频率越高的字符，应该优