算法导论上机报告

1、算法导论上机报告 班级： 1313012 学号：姓名： 黄帮振 实验编号1题目1归并排序算法实验内容描述一个运行时间为(nlgn)的算法给定n个整数的集合S和另一个整数x该算法能确定S中是否存在两个其和刚好为x的元素。实验目的用分治思想，设计子问题，实现归并排序算法；报 告 正 文一、算法分析1、运用归并排序算法 归并排序运用的是分治思想，时间复杂度为(nlgn)能够满足题目要求的运行时间。归并排序的分解部分是每次将数组划分两个部分，时间复杂度为（1）再对已经分解的两个部分再进行分解直到将数组分解成单个元素为止。解决部分是递归求解排序子序列，合并部分是将已经排序的子序

2、列进行合并得到所要的答案，时间复杂度为(lgn)。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

3、 n15. Li=Ap+i-16. For j=1 to n27. Rj=Aq+j8. Ln1+1=无穷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-SORT（A,p,q）4、 MERGE-SORT(A,q+1,r)5、 MERGE(A,p,q,r)3、 实验总结 在主函数中调用二分查找的时候，参数应该为BinSearch(a,j+1,n,x-aj）从j

4、+1开始遍历而不是都是从第一个开始。在程序中由于程序语言规定数组的下标从0开始而算法伪代码要求从1开始，因此在定义数组大小的时候将数字加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、堆排序算法是引用堆这个

5、数据结构进行信息管理。堆排序的时间复杂度是(nlgn),但是与归并排序不同的是堆排序具有空间的原址性，任何时候都只需要常数个额外的元素空间存储临时数据。堆排序算法分为3个过程MAX-HEAPIEY:调整堆以满足小顶堆性质 其时间复杂度为(lgn)；BUILD-MAXHEAP:从无序的输入数据数组中构造小顶堆，其时间复杂度为线性时间;HEAP-SORT:对数组进行原址排序，其时间复杂度为(nlgn)。 2、在堆的基础上实现优先队列INSERT、MAXMUM、EXTRACT-MAX、INCREASE-KEY时间复杂度为(lgn)。 2、 伪代码 BUILD-MAX-HEAP(A)1. A.heap

6、-size=A.length2. For i=A.length/2(取下限) downto 13. MAX-HEAPIFY（A，i）HEAPSORT（A）1. Build-MAX-HEAP（A）2. 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 underflow”3. Max=A14. A1=AA.

7、heap-size5. A.heap-size=A.heap-size - 16. MAX-HEAPIFY(A,1)7. Return maxHEAP-INCREASE-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) 三、实验总结 一开始没有理解将一个序列转换

8、成小顶堆的过程，在编写MAX-EXSTRACT函数的时候，当去掉第一个元素后，程序并没有调用MAX-HEAP进行调整堆，因此最后序列是无序状态。实验编号1题目3快速排序算法实验内容实现快速排序算法。实验目的使用Java实现插入排序算法。报 告 正 文一、算法原理快速排序采用分治策略，时间复杂度为(nlgn),但是最坏情况下为(n2),并且快速排序算法属于原地排序，并不需要开辟空间。快速排序复杂的步骤为其分解的步骤分解的过程数组Ap.r被划分为两个子数组Ap.q-1和Aq+1.r,使得Ap.q-1中的每个元素都小于Aq,而Aq也小于等于Aq+1.r中的每个元素。而在实现的过程总是选择将Ar作为基

9、准点进行划分Ap.r数组。 二、伪代码QUICKSORT(A，p，r)1 if p B1，那么K肯定不在A0, (m/(m + n) * (k - 1)以及B(k + 1 - (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. El

10、se 12. Return Searchkth(A,B,amid+1,ahigh,blow,bhigh,k-(amid-alow)-1)13. Else14. If k= 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、 实验总结 理解分治策略的三个步骤：分解、解决和合并对于具体问题的具体表现，要善于根据时间复杂度与所学的算法进行结合，找出可以利用的地

11、方。 实验编号2题目1矩阵链乘实验内容用动态规划实现矩阵链乘，保证相乘的次数最少。实验目的用动态规划实现矩阵链乘报 告 正 文1、 算法原理 1最优子结构为：如果最优的加括号的方式将其分解为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值指出了AiA

12、i+1Aj的最优括号化方案的分割点应在AkAk+1之间。 5 矩阵链乘的时间复杂度为(n3) 2、 伪代码MATRIX-CHAIN-ORDER（p）1.n=p.length-12.Let m1.n,1.n and 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-OPTI

13、MAL-PARENS(s,i,j)1. if i=j2. Print “A”3. Else print “(”4. PRINT-OPTIMAL-PARENS(s,i,si,j)5. PRINT-OPTIMAL-PARENS(s,si,j+1,j)6. Print “）”3、 实验总结 矩阵链乘主要运用动态规划的思想，这种思想的重要之处在于找到最优的子结构，并设计出最优解的形式。编程是并未遇到什么问题，过程较为顺利。实验编号2题目2最长公共子序列实验内容用动态规划求下列字符串的最长公共子序列。实验目的用动态规划实现寻找最长公共子序列算法。报 告 正 文1、 算法原理 1最优子结构：令X=和Y=为

14、两个序列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-1的一个LCS。 2定义一个bi,j指向表项对应计算ci,j时所选择的子问题最优解，过程返回表b和表c，cm,n保持X和Y的LCS长度。 3LCS的递归式为 4LCS的时间复杂度为(m+n),b表的空间复杂度为(mn)。 2、 伪代码LCS-LENGTH（X,Y）1. m=X.length2. n=Y.length3. Let b1.m,1.n and c0.m,0.n be ne

15、w 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. Else 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)

16、5. Print xi6. Elseif bi,j=27. PRINT-LCS(b,X,i-1,j)8.else PRINT-LCS(b,X,i,j-1)三、实验总结 用动态规划求取最长公共子序列的时候，要理解b数组的用途和使用。一开始编程时将输入的字符串转化为字符出现问题，后来使用charAt（）函数解决了问题。 实验编号2题目3最长公共子串实验内容用动态规划求取以下字符串的最长公共子串。实验目的用动态规划实现最长公共子串算法报 告 正 文一、算法原理 1最优子结构令X=和Y=为两个序列Z=为X和Y的任意最长公共子串。如果xm=yn,则zk=xm=yn且Zk-1是Xm-1和Yn-1的一个最长

17、公共子串； 如果xmyn,则zkxm意味着Z是Xm-1和Y的一个最长公共子串；如果xmyn,则zkyn意味着Z是X和Yn-1的一个最长公共子串。 2定义Li,j为以xi和yj为结尾的相同子串的最大长度，记录着X和Y的最长公共子串的最大长度。 3最长公共子串的递归式 4最长公共子串的时间复杂度为(mn)，空间复杂度为(mn)。 2、 伪代码 getLCString(str1,tr2) len1 = str1.length;len2 = str2.length;maxLen = len1 len2 ? len1 : len2;int max = new intmaxLen;int maxIndex

18、 = 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 - 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

19、 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 maxIndexj Print str1i三、实验总结 要同上述的最长公共子序列进行对比区分他们的不同之处。也要理解用动态规划求解时的相同之处和不同之处。实验编号2题目4最大子段和实验内容给定n个整数（可能为负数）组成的序列a1,a2.an,求该序列ai+ai+1.aj的子段和的最大值。 实验目的用动态规划实现数列的最大和报 告

20、正 文1、 算法原理 1 最优子结构：定义当所给整数全为负数的时候，最大子段和为0,则最大子段和为max0,ai+ai+1.+aj,1ijn 2 引入一个辅助数组b,动态规划的分解分为两步：(1)计算辅助数组的值；(2)计算辅助数组的最大值。辅助数组bj用来记录以j为尾的子段以及集合中的最大子段和。 3 最大子段和的递归式 4 最大子段和使用动态规划进行计算的时间复杂度为(n)。2、 伪代码Maxsum（A）1. sum=02. temp=03. B1.A.length=arraycopy(A)4. For i=0 to B.length5. If Bi06. Sum=Bi7. Break8.

21、for j=i+1 to B.length9. If Bj010. For a=i to j11. temp=temp+ba12. If tempsum13. sum=temp14.print max三、实验总结 对比比较了动态规划和分治法的不同，感受到用动态规划解决的便捷。 实验编号2题目5最短路径问题实验内容解决多级图中的最短路径问题实验目的用动态规划解决多级图中的最短路径问题报 告 正 文一、算法原理1可以由图可知，图中的顶点讲图划分7个阶段，分别了解每个阶段可以有几种可供选择的点，引入fk表示状态k到终点状态的最短距离。最优子结构为当前状态的fk由上个状态的fk-1和状态k-1到状态k

22、的距离决定决策：当前状态应在前一个状态的基础上获得。决策需要满足规划方程,规划方程f(k)表示状态k到终点状态的最短距离。 2多段图最短路径的递归式 2、 伪代码Shortestpathlet indexs 0.W10.length,isLabel 0.W10.lengthbe a new tablei_count = -1distance = W1start index = startpresentShortest = 0indexs+i_count = index;isLabelindex = true;while i_countW10.length min = Integer.MAX_V

23、ALUE; for i = 0 to distance.lengthif !isLabeli and distancei != -1 and i != indexif distancei distanceindex presentShortest = distanceindex;else presentShortest += W1indexsi_count - 1index; for i = 0 to distance.lengthif distancei = -1 and W1indexi != -1 distancei = presentShortest + W1indexi;else i

24、f W1indexi != -1 and presentShortest + W1indexi distancei) distancei = presentShortest + W1indexi; return distanceend - distancestart;三、实验总结 遇到的问题：无法将多段图的每个阶段点的状态表示并记录下来。并不了解如何将动态规划与贪心算法的如迪杰斯特拉算法进行对比，真正从最优子结构将最短路径表示出来。实验编号3题目1分数背包问题和0/1背包问题实验内容解决分数背包和0/1背包问题实验目的分别用贪心算法和动态规划实现分数背包问题和0/1背包问题报 告 正 文1、

25、算法原理 10-1背包问题：选择n个元素中的若干个来形成最优解，假定为k个。对于这k个元素a1, a2, .ak来说，它们组成的物品组合必然满足总重量C，循环体为将第i个物品放入背包，Xi=1;C=C-Wi;i+最后一步将结果存入到X数组中Xi=C/Wi。 3 分数背包问题采用选择单位重量价值最大的物品顺序进行挑选，其算法的时间复杂度为(nlgn)。4 背包问题的递归式:fiv=maxfi-1v,fi-1v-ci+wi二、伪代码Knapsack01（v,w,weight）1. n=w.length2. let c0.n,0.weight be a new table3. For i=0 to

26、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. For i=0 to v.length3. vwi=vi/wi4. c=weight5. sum=06. temp=07. While c08. temp=09. For i=0 to v.length10. If vwi

27、temp 11. temp=vwi12. For i=0 to i016. sum=sum+vi17. c=c-wi18. vwi=019. Else20. sum=sum+c*vwi21. c=c-c22. vwi=023. Print sum三、实验总结分数背包问题所采用的贪心策略之不能得到最优解是由于物品不允许分割，因此无法保证最终能将背包装满，部分闲置的背包容量使背包的单位重量价值降低了。实验编号3题目2简单的调度问题实验内容给予工作编号为J1、J2.Jn，已知其工作的运行时间分别为T1、T2.TN。有一个单独的处理器，为了安排这些工作以到达减少平均完成时间的最好方法是什么。假定它是一

28、个非抢占式调度，一旦工作开始，它必须运行完成。实验目的安排进程的先后次序使得等待时间最短。报 告 正 文一、算法原理 由于是非抢占式调度，所以应该尽量让时间短的工作先做，然后再让时间长的工作做。这里我们使用快速排序，快速排序的时间复杂度是O(nlgn)， 然后将前n-1项工作时间相加，计算出平均完成时间2、 伪代码 Schedule(A)1. Let time0.A.length-1 be a new table 2. Quicksort(time,0,time.length-1)3. Sum=04. For i=0 to time.length-15. Sum+=timei6. Print

29、timei and sum/(n-1)三、实验总结 注意sum除的是n-1而不是n。实验编号3题目3单源最短路径实验内容以A为源点，按照矩阵所给的长度，设计单源最短路径实验目的用Bellman-Ford实现单源最短路径问题报 告 正 文一、算法原理 Bellman-Ford算法通过对边进行松弛操作来渐近地降低从源点A到每个结点的最短路径的估计值，直到该估计值与实际的最短路径权重相同为止。该算法返回TRUE值当且仅当输入图中不包含可以从源结点到达的权重为负值的环路。 Bellman-Ford算法的执行步骤：1、初始化：将除源点外的所有顶点的最短距离估计值dv+, ds0；2、迭代求解：反复对边集

30、E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离，运行|v|-1次；3、检验负权回路，判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false表明问题无解，否则算法返回true并且从源点可达的顶点v的最短距离保存在dv中。 二、伪代码 Bellman-Ford(G,w,s)1. ds=02. Bound=正无穷3. For i=0 to G.length4. For j=0 to G0.length5. If gi,j=06. Graphi,j=bound7. Else8. Graphi,j=Gi,j9. For each vV

31、-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全结点最短路径算法实验内容利用Floyd-Warshall算法计算所给矩阵的全结点最短路径实验目的实现Floyd-War