算法导论上机报告材料.doc

《算法导论上机报告材料.doc》由会员分享，可在线阅读，更多相关《算法导论上机报告材料.doc（18页珍藏版）》请在课桌文档上搜索。

1、实验编号1题目1归并排序算法实验容描述一个运行时间为(nlgn)的算法给定n个整数的集合S和另一个整数x该算法能确定S中是否存在两个其和刚好为x的元素。实验目的用分治思想，设计子问题，实现归并排序算法；报 告 正 文一、算法分析1、运用归并排序算法 归并排序运用的是分治思想，时间复杂度为(nlgn)能够满足题目要求的运行时间。归并排序的分解局部是每次将数组划分两个局部，时间复杂度为1再对已经分解的两个局部再进展分解直到将数组分解成单个元素为止。解决局部是递归求解排序子序列，合并局部是将已经排序的子序列进展合并得到所要的答案，时间复杂度为(lgn)。2、 在已经排好序的根底上，对其运用二分查找

2、二分查找算法的时间复杂度为(lgn)在题目要求的围，二分查找的条件为待查的数组为有序序列。算法的主要思想为设定两个数low指向最低元素high指向最高元素，然后比拟数组中间的元素与待查元素进展比拟。如果待查元素小于中间元素，那么明确查找元素在数组的前半段，反之，如果待查元素大于中间元素，那么明确查找元素在数组的后半段。二、伪代码：MERGE(A,p,q,r)1. n1=q-p+12. n2=r-q3. Let L1.n1+1andR1.n2+1be new arrays4. For i=1 to n15. Li=Ap+i-16. For j=1 to n27. Rj=Aq+j8. Ln1+1=

3、无穷9. Rn2+1=无穷10. I=111. J=112. For k=p to r13. If Li=Rj14. Ak=Li15. I=i+116. Else Ak=Rj17. J=j+1MERGE-SORT(A,p，r)1、 if pr2、 q=(p+r)/2(取下限)3、 MERGE-SORTA,p,q4、 MERGE-SORT(A,q+1,r)5、 MERGE(A,p,q,r)3、 实验总结在主函数中调用二分查找的时候，参数应该为BinSearch(a,j+1,n,x-aj从j+1开始遍历而不是都是从第一个开始。在程序中由于程序语言规定数组的下标从0开始而算法伪代码要求从1开始，因此

4、在定义数组大小的时候将数字加1，但是在编译运行的时候会得不到想要的结果，出现数组下标访问错误。实验编号1题目2优先队列排序实验容实现优先队列排序算法，需要支持以下操作：INSERT(S,x):把元素x插入到集合S中MAXMUM(S):返回S中具有最大key的元素EXTRACT-MAX(S):去掉并返回S中的具有最大key的元素INCREASE-KEY(S,x,k)：将元素x的关键字值增到k。 实验目的堆排序，运用堆来实现优先队列。报 告 正 文1、 算法原理1、堆排序算法是引用堆这个数据结构进展信息管理。堆排序的时间复杂度是(nlgn),但是与归并排序不同的是堆排序具有空间的原址性，任何时候都

5、只需要常数个额外的元素空间存储临时数据。堆排序算法分为3个过程MAX-HEAPIEY:调整堆以满足小顶堆性质 其时间复杂度为(lgn)；BUILD-MAXHEAP:从无序的输入数据数组中构造小顶堆，其时间复杂度为线性时间;HEAP-SORT:对数组进展原址排序，其时间复杂度为(nlgn)。 2、在堆的根底上实现优先队列INSERT、MAXMUM、EXTRACT-MAX、INCREASE-KEY时间复杂度为(lgn)。 2、 伪代码BUILD-MAX-HEAP(A)1.2. For i=A.length/2(取下限) downto 13. MAX-HEAPIFYA，iHEAPSORTA1. Bu

6、ild-MAX-HEAPA2. For i=A.length downto 23. Exchange A1 with Ai4. A.heap-size=A.heap-size - 15. MAX-HEAPIFY(A,1)HEAP-MAIMUM(A)1. return A1HEAP-EXTRACT-MAX(A)1. if A.heap-size12. Error “heap underflow3. Max=A14. A1=AA.heap-size5. A.heap-size=A.heap-size - 16. MAX-HEAPIFY(A,1)7. Return maxHEAP-INCREASE-

7、KEY(A,i,key)1. if key1 and APARENT(i)Ai5. Exchange Ai with APARENT(i)6. I=PARENT(i)MAX-HEAP-INSERT(A,key)1. A.heap-size=A.heap-size + 12. AA.heap-size=负无穷3. HEAP-INCREASE-KEY(A,A.heap-size,key) 三、实验总结 一开始没有理解将一个序列转换成小顶堆的过程，在编写MAX-EXSTRACT函数的时候，当去掉第一个元素后，程序并没有调用MAX-HEAP进展调整堆，因此最后序列是无序状态。实验编号1题目3快速排序算

8、法实验容实现快速排序算法。实验目的使用Java实现插入排序算法。报 告 正 文一、算法原理快速排序采用分治策略，时间复杂度为(nlgn),但是最坏情况下为(n2),并且快速排序算法属于原地排序，并不需要开辟空间。快速排序复杂的步骤为其分解的步骤分解的过程数组Ap.r被划分为两个子数组Ap.q-1和Aq+1.r,使得Ap.q-1中的每个元素都小于Aq,而Aq也小于等于Aq+1.r中的每个元素。而在实现的过程总是选择将Ar作为基准点进展划分Ap.r数组。 二、伪代码QUICKSORT(A，p，r)1 if p B1，那么K肯定不在A0, (m/(m + n) * (k - 1)以与B(k + 1

9、- (m/(m + n) * (k - 1)+ 1, n中；如果A1ahigh 4. return Bblow+k-15. If blowbhigh 6. return Aalow+k-17. If Aamid=Bbmid8. If Aamid=Bbmid9. If k= amid-alow+bmid-blow+110. Return Searchkth(A,B,alow,ahigh,blow,bmid-1,k)11. Else 12. Return Searchkth(A,B,amid+1,ahigh,blow,bhigh,k-(amid-alow)-1)13. Else14. If k=

10、amid-alow+bmid-blow+115. Return Searchkth(A,B,alow,amid-1,blow,bhigh,k)16. Else17. Return Searchkth(A,B,alow,ahigh,bmid+1,bhigh,k-(bmid-blow)-1) 3、 实验总结理解分治策略的三个步骤：分解、解决和合并对于具体问题的具体表现，要善于根据时间复杂度与所学的算法进展结合，找出可以利用的地方。 实验编号2题目1矩阵链乘实验容用动态规划实现矩阵链乘，保证相乘的次数最少。实验目的用动态规划实现矩阵链乘报 告 正 文1、 算法原理1最优子结构为：如果最优的加括号的方

11、式将其分解为Ai.k与Ak+1.j的乘积如此分别对Ai.k与Ak+1.j加括号的方式也一定是最优的。 2定义mi,j为计算矩阵Ai.j所需标量乘法次数的最小值，对于i=j时,矩阵链乘只包含唯一的矩阵Ai,因此不需要做任何标量乘法运算，所以mi,i=0;当ij时利用最优子结构来计算mi,j。 3矩阵链乘的递归式4在算法设计的时候需要m数组记录Ai.j最小相乘次数，s数组记录构造最优解所需要的信息，其记录的k值指出了AiAi+1Aj的最优括号化方案的分割点应在AkAk+1之间。 5 矩阵链乘的时间复杂度为(n3) 2、 伪代码MATRIX-CHAIN-ORDERp2.Let m1.n,1.n an

12、d s1.n-1,2.n be new tables3.For i=1 to n4. Mi,i=05.for l=2 to n6. For i=1 to n-l+17. J=i+l-18. Mi,j=无穷9. For k=i to j-110. Q=mi,k+mk+1,j+p(i-1)*p(k)*p(j)11. If qmi,j12. Mi,j=q13. Si,j=kPRINT-OPTIMAL-PARENS(s,i,j)1. if i=j2. Print “A3. Else print “(4. PRINT-OPTIMAL-PARENS(s,i,si,j)5. PRINT-OPTIMAL-PA

13、RENS(s,si,j+1,j)6. Print “3、 实验总结矩阵链乘主要运用动态规划的思想，这种思想的重要之处在于找到最优的子结构，并设计出最优解的形式。编程是并未遇到什么问题，过程较为顺利。实验编号2题目2最长公共子序列实验容用动态规划求如下字符串的最长公共子序列。实验目的用动态规划实现寻找最长公共子序列算法。报 告 正 文1、 算法原理 1最优子结构：令X=和Y=为两个序列Z=为X和Y的任意LCS。如果xm=yn,如此zk=xm=yn且Zk-1是Xm-1和Yn-1的一个LCS；如果xmyn,如此zkxm意味着Z是Xm-1和Y的一个LCS；如果xmyn,如此zkyn意味着Z是X和Yn-

14、1的一个LCS。 2定义一个bi,j指向表项对应计算ci,j时所选择的子问题最优解，过程返回表b和表c，cm,n保持X和Y的LCS长度。 3LCS的递归式为4LCS的时间复杂度为(m+n),b表的空间复杂度为(mn)。 2、 伪代码LCS-LENGTHX,Y1.2.3. Let b1.m,1.n and c0.m,0.n be new tables4. For i=1 to m5. ci,0=06. For j=0 to n7. c0,j=08. For i=1 to m9. For j=1 to n10. If xi=yj11. ci,j=ci-1,j-1+112. bi,j=113. El

15、se if ci-1,j=ci,j-114. ci,j=ci-1,j15. bi,j=216. Else ci,j=ci,j-117. bi,j=318.return ；PRINT-LCS(b,X,i,j)1. if i=0 or j=02. Return ;3. If bi,j=14. PRINT-LCS(b,X,i-1,j-1)5. Print xi6. Elseif bi,j=27. PRINT-LCS(b,X,i-1,j)8.else PRINT-LCS(b,X,i,j-1)三、实验总结用动态规划求取最长公共子序列的时候，要理解b数组的用途和使用。一开始编程时将输入的字符串转化为字符出

16、现问题，后来使用charAt函数解决了问题。 实验编号2题目3最长公共子串实验容用动态规划求取以下字符串的最长公共子串。实验目的用动态规划实现最长公共子串算法报 告 正 文一、算法原理 1最优子结构令X=和Y=为两个序列Z=为X和Y的任意最长公共子串。如果xm=yn,如此zk=xm=yn且Zk-1是Xm-1和Yn-1的一个最长公共子串； 如果xmyn,如此zkxm意味着Z是Xm-1和Y的一个最长公共子串；如果xmyn,如此zkyn意味着Z是X和Yn-1的一个最长公共子串。 2定义Li,j为以xi和yj为结尾的一样子串的最大长度，记录着X和Y的最长公共子串的最大长度。 3最长公共子串的递归式 4

17、最长公共子串的时间复杂度为(mn)，空间复杂度为(mn)。 2、 伪代码 getLCString(str1,tr2) len1 = str1.length;len2 = str2.length;maxLen = len1 len2 ? len1 : len2;int max = new intmaxLen;int maxIndex = new intmaxLen;int c = new intmaxLen;Let max0.maxlen-1,maxindex0.maxlen-1 and c0.maxlen-1 be new tablesFor i = 0 to len2for j = len1

18、 - 1 to 0if str2i = str1j if i = 0 or j = 0cj = 1;elsecj = cj - 1 + 1; elsecj = 0;if cj max0)max0 = cj;maxIndex0 = j;for k = 1to maxLenmaxk = 0;maxIndexk = 0; else if cj = max0 for k = 1 to maxLenif maxk = 0 maxk = cj; maxIndexk = j;for j to maxLenif maxj 0Print j + 1for i = maxIndexj - maxj + 1 to

19、maxIndexj Print str1i三、实验总结要同上述的最长公共子序列进展比照区分他们的不同之处。也要理解用动态规划求解时的一样之处和不同之处。实验编号2题目4最大子段和实验容给定n个整数可能为负数组成的序列a1,a2.an,求该序列ai+ai+1.aj的子段和的最大值。 实验目的用动态规划实现数列的最大和报 告 正 文1、 算法原理1 最优子结构：定义当所给整数全为负数的时候，最大子段和为0,如此最大子段和为max0,ai+ai+1.+aj,1ijn 2 引入一个辅助数组b,动态规划的分解分为两步：(1)计算辅助数组的值；(2)计算辅助数组的最大值。辅助数组bj用来记录以j为尾的子段

20、以与集合中的最大子段和。 3 最大子段和的递归式 4 最大子段和使用动态规划进展计算的时间复杂度为(n)。2、 伪代码MaxsumA1. sum=02. temp=03. B1.A.length=arraycopy(A)4.5. If Bi06. Sum=Bi7. Break9. If Bj010. For a=i to j11. temp=temp+ba12. If tempsum13. sum=temp14.print max三、实验总结比照比拟了动态规划和分治法的不同，感受到用动态规划解决的便捷。实验编号2题目5最短路径问题实验容解决多级图中的最短路径问题实验目的用动态规划解决多级图中的

21、最短路径问题报 告 正 文一、算法原理1可以由图可知，图中的顶点讲图划分7个阶段，分别了解每个阶段可以有几种可供选择的点，引入fk表示状态k到终点状态的最短距离。最优子结构为当前状态的fk由上个状态的fk-1和状态k-1到状态k的距离决定决策：当前状态应在前一个状态的根底上获得。决策需要满足规划方程,规划方程f(k)表示状态k到终点状态的最短距离。 2多段图最短路径的递归式2、 伪代码Shortestpathlet indexs 0.W10.length,isLabel 0.W10.lengthbe a new tablei_count = -1distance = W1startindex

22、= startpresentShortest = 0indexs+i_count = index;isLabelindex = true;while i_countW10.length min = Integer.MAX_VALUE; for i = 0 to distance.lengthif !isLabeli and distancei != -1 and i != indexif distancei distanceindex presentShortest = distanceindex;else presentShortest += W1indexsi_count - 1index

23、; for i = 0 to distance.lengthif distancei = -1 and W1indexi != -1 distancei = presentShortest + W1indexi;else if W1indexi != -1 and presentShortest + W1indexi distancei) distancei = presentShortest + W1indexi; return distanceend - distancestart;三、实验总结遇到的问题：无法将多段图的每个阶段点的状态表示并记录下来。并不了解如何将动态规划与贪心算法的如迪

24、杰斯特拉算法进展比照，真正从最优子结构将最短路径表示出来。实验编号3题目1分数背包问题和0/1背包问题实验容解决分数背包和0/1背包问题实验目的分别用贪心算法和动态规划实现分数背包问题和0/1背包问题报 告 正 文1、 算法原理 10-1背包问题：选择n个元素中的假设干个来形成最优解，假定为k个。对于这k个元素a1, a2, .ak来说，它们组成的物品组合必然满足总重量C，循环体为将第i个物品放入背包，Xi=1;C=C-Wi;i+最后一步将结果存入到X数组中Xi=C/Wi。 3 分数背包问题采用选择单位重量价值最大的物品顺序进展挑选，其算法的时间复杂度为(nlgn)。4 背包问题的递归式:fi

25、v=maxfi-1v,fi-1v-ci+wi二、伪代码Knapsack01v,w,weight1.2. let c0.n,0.weight be a new table3. For i=0 to n4. ci,0=05. For j=1 to weight 6. c0,j=07. For i=1 to n8. For j=1 to weight9. If(j(ci-1,j-wi-1+vi-1)13. ci,j=ci-1,j14. Else15. ci,j=ci-1,j-wi-1+vi-1KnapsackFra(weight,v,w)1. vw0.v.length2.3. vwi=vi/wi4.

26、 c=weight5. sum=06. temp=07. While c08. temp=09.10. If vwitemp 11. temp=vwi12.13. If temp=vwi14. Break15. If c-wi016. sum=sum+vi17. c=c-wi18. vwi=019. Else20. sum=sum+c*vwi21. c=c-c22. vwi=023. Print sum三、实验总结分数背包问题所采用的贪心策略之不能得到最优解是由于物品不允许分割，因此无法保证最终能将背包装满，局部闲置的背包容量使背包的单位重量价值降低了。实验编号3题目2简单的调度问题实验容给予

27、工作编号为J1、J2.Jn，其工作的运行时间分别为T1、T2.TN。有一个单独的处理器，为了安排这些工作以到达减少平均完成时间的最好方法是什么。假定它是一个非抢占式调度，一旦工作开始，它必须运行完成。实验目的安排进程的先后次序使得等待时间最短。报 告 正 文一、算法原理 由于是非抢占式调度，所以应该尽量让时间短的工作先做，然后再让时间长的工作做。这里我们使用快速排序，快速排序的时间复杂度是O(nlgn)， 然后将前n-1项工作时间相加，计算出平均完成时间2、 伪代码Schedule(A)1. Let time0.A.length-1 be a new table 2. Quicksort(ti

28、me,0,time.length-1)3. Sum=04.5. Sum+=timei6. Print timei and sum/(n-1)三、实验总结注意sum除的是n-1而不是n。实验编号3题目3单源最短路径实验容以A为源点，按照矩阵所给的长度，设计单源最短路径实验目的用Bellman-Ford实现单源最短路径问题报 告 正 文一、算法原理 Bellman-Ford算法通过对边进展松弛操作来渐近地降低从源点A到每个结点的最短路径的估计值，直到该估计值与实际的最短路径权重一样为止。该算法返回TRUE值当且仅当输入图中不包含可以从源结点到达的权重为负值的环路。 Bellman-Ford算法的执

29、行步骤：1、初始化：将除源点外的所有顶点的最短距离估计值dv+, ds0；2、迭代求解：反复对边集E中的每条边进展松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离，运行|v|-1次；3、检验负权回路，判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，如此算法返回false明确问题无解，否如此算法返回true并且从源点可达的顶点v的最短距离保存在dv中。二、伪代码Bellman-Ford(G,w,s)1. ds=02. Bound=正无穷3.4. For j=0 to G0.length5. If gi,j=06. Graphi,j=bound7. Else8

30、. Graphi,j=Gi,j9. For each vV-A10. If graph0,igraph0,k+graphk,i11. Graph0,i=graph0,k+graphk,i12. For each vV-A13. if Graph0,igraph0.k+graphk,i14. Retrun false15. Return true三、实验总结根本能将Bellman-Ford算法写出来，但是二维数组的行列长度的表示，还须分开，否如此会出现数组越界的问题。实现单元路径最短算法，最重要的是从一点出发经过或者不经过多个点都要遍历，进展比拟才能的出最后的结果。实验编号3题目4全结点最短路径

31、算法实验容利用Floyd-Warshall算法计算所给矩阵的全结点最短路径实验目的实现Floyd-Warshall算法报 告 正 文一、算法原理设G的顶点为V=1,2,3.n对于任意一对顶点i,j属于V，假设i到j有路径且中间节点皆属于集合1,2,3.k，P是其中的一条最小权值路径。就是i到j的最短路径P所通过的中间顶点最大不超过k。设d(k)ij为从结点i到结点j的所有中间结点全部取自结合1,2,.,k的一条最短路径的权重。D(k)ij的递归定义为 D(k)ij= wij if k=0 = min(d(k-1)ij,d(k-1)ik+d(k-1)kj) if k=1Floyd-Warshal

32、l算法的时间复杂度为(v3)。 2、 伪代码FloydWarshall(G)1. for each vV2. If i=j3. Graphi,j=04. Elseif Gi,j=05. Graphi,j=正无穷6. Else7. Graphi,j=Gi,j8.9. For each vV10. if Graphi,jgraphi,k+graphk,j11. Graphi,j=graphi,k+graphk,j3、 实验总结相比单源结点路径，全结点路径遍历的次数要倍增，但是算法实现的原理还是考察经过多个结点路径的变化。实验编号4题目1回溯法解决背包问题实验容使用回溯算法解决背包问题实验目的使用回

33、溯算法解决背包问题报 告 正 文1、 算法原理利用回溯法求解首先是要确定约束函数，根据0-1背包问题的特点，由于背包的容量是确定，因此背包问题中第k个物品的取舍要取决于放入后是否超过背包的容量。即C1.k-1+ wkbestval4. Bestval=nv5. For k=0 to n6. Bestxk=xk7. Else 8. For j=0 to 19. Xi=j10. If nw+wi*xi=weight11. Nw=nw+wi*xi12. Nv=nv+vi*xi13. BackTrace(i+1,nv,nw,v,w,weight);14. Else15. Bestval=nv16. F

34、or k=0 to i17. Bestxk=xkKnapsackBack(v,w,weight)1. let bestx0.v.length-1and X0.v.length be new tables2. Bestval=03. BackTrace(0,0,0,v,w,weight)三、实验总结 在每一次迭代时，要把每种情况都罗列出来，并将其去向用if-else语句表达出来，少写一种情况会导致最后的结果出不来或者发生错误。回溯算法最难的是迭代环节，此次编程后对于回溯算法稍有了解。实验编号4题目29-Queen问题实验容设计一个算法是的在同一棋盘上的8个皇后不发生冲突实验目的使用回溯算法设计8-Queen的算法报 告 正 文1、 算法原理 利用回溯法求解8-queen问题，即确定每个queen在每一行的位置，首先确定约束条件，要求每个queen不能