算法导论上机报告

算法导论上机报告班级：1313012学号：13130120123姓名：黄帮振实验编号1题目1归并排序算法实验内容描述一个运行时间为θ(nlgn)n个整数的集合S和另一个整数x该算法能确定S中是否存在两个其和刚好为x的元素。实验目的用分治思想，设计子问题，实现归并排序算法；报告正文一、算法分析1、运用归并排序算法归并排序运用的是分治思想，时间复杂度为θ(nlgn)能够满足题目要求的运行时间。归并排序的分解部分是每次将数组划分两个部分，时间复杂度为θ（1）再对已经分解的两个部分再进行分解直到将数组分解成单个元素为止。解决部分是递归求解排序子序列，合并部分是将已经排序的子序列进行合并得到所要的答案，时间复杂度为θ(lgn)。2、在已经排好序的基础上，对其运用二分查找二分查找算法的时间复杂度为θ(lgn)在题目要求的范围内，二分查找的条件为待查lowhigh指向最高元素，然后比较数组中间的元素与待查元素进行比较。如果待查元素小于中间元素，那么表明查找元素在数组的前半段，反之，如果待查元素大于中间元素，那么表明查找元素在数组的后半段。二、伪代码：MERGE(A,p,q,r)1.n1=q-p+12.n2=r-q3.LetL[1..n1+1]andR[1..n2+1]benewarrays4.Fori=1ton15.L[i]=A[p+i-1]6.Forj=1ton27.R[j]=A[q+j]8.L[n1+1]=无穷9.R[n2+1]=无穷10.I=111.J=112.Fork=ptor13.IfL[i]=R[j]14.A[k]=L[i]15.I=i+116.ElseA[k]=R[j]17.J=j+1MERGE-SORT(A,p，r)1、ifpr2、q=(p+r)/2(取下限)3、MERGE-SORT（A,p,q）4、MERGE-SORT(A,q+1,r)5、MERGE(A,p,q,r)三、实验总结在主函数中调用二分查找的时候，参数应该为BinSearch(a,j+1,n,x-a[j]）从j+1开始遍历而不是都是从第一个开始。在程序中由于程序语言规定数组的下标从0开始而算法伪代码要求从1开始，因此在定义数组大小的时候将数字加1，但是在编译运行的时候会得不到想要的结果，出现数组下标访问错误。实验编号1题目2优先队列排序实验内容实现优先队列排序算法，需要支持以下操作：INSERT(S,x):把元素x插入到集合S中MAXMUM(S):返回S中具有最大keyEXTRACT-MAX(S):去掉并返回S中的具有最大keyINCREASE-KEY(S,x,k)：将元素x的关键字值增到k。实验目的堆排序，运用堆来实现优先队列。报告正文一、算法原理1、堆排序算法是引用堆这个数据结构进行信息管理。堆排序的时间复杂度是θ(nlgn),但是与归并排序不同的是堆排序具有空间的原址性，任何时候都只需要常数个额外的元素空间存储临时数据。堆排序算法分为3个过程MAX-HEAPIEY:调整堆以满足小顶堆性质其时间复杂度为θ(lgn)；BUILD-MAXHEAP:从无序的输入数据数组中构造小顶堆，其时间复杂度为线性时间;HEAP-SORT:对数组进行原址排序，其时间复杂度为θ(nlgn)。2、在堆的基础上实现优先队列INSERT、MAXMUM、EXTRACT-MAX、INCREASE-KEY时间复杂度为θ(lgn)。二、伪代码BUILD-MAX-HEAP(A)1.A.heap-size=A.length2.Fori=A.length/2(取下限)downto13.MAX-HEAPIFY（A，i）HEAPSORT（A）1.Build-MAX-HEAP（A）2.Fori=A.lengthdownto23.ExchangeA[1]withA[i]4.A.heap-size=A.heap-size-15.MAX-HEAPIFY(A,1)HEAP-MAIMUM(A)1.returnA[1]HEAP-EXTRACT-MAX(A)1.ifA.heap-size12.Error“heapunderflow”3.Max=A[1]4.A[1]=A[A.heap-size]5.A.heap-size=A.heap-size-16.MAX-HEAPIFY(A,1)7.ReturnmaxHEAP-INCREASE-KEY(A,i,key)1.ifkeyA[i]2.Error“newkeyissmallerthancurrentkey”3.A[i]=key4.Whilei1andA[PARENT(i)]A[i]5.ExchangeA[i]withA[PARENT(i)]6.I=PARENT(i)MAX-HEAP-INSERT(A,key)1.A.heap-size=A.heap-size+12.A[A.heap-size]=负无穷3.HEAP-INCREASE-KEY(A,A.heap-size,key)三、实验总结一开始没有理解将一个序列转换成小顶堆的过程，在编写MAX-EXSTRACT函数的时候，当去掉第一个元素后，程序并没有调用MAX-HEAP进行调整堆，因此最后序列是无序状态。实验编号1题目3快速排序算法实验内容实现快速排序算法。实验目的使用Java实现插入排序算法。报告正文一、算法原理快速排序采用分治策略，时间复杂度为θ(nlgn),但是最坏情况下为θ(n2),并且快速排序算法属于原地排序，A[p..r]被划分为两个子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每个元素都小于A[q],而A[q]也小于等于A[q+1..r]中的每个元素。而在实现的过程总是选择将A[r]作为基准点进行划分A[p..r]数组。二、伪代码QUICKSORT(A，p，r)1ifpr2q=PARTITION(A，p，q)3QUICKSORT(A，p，q-1)4QUICKSORT(A，q+1，r)PARTITION(A，p，r)1x=A[r]2i=p-13forj=ptor-14ifA[j]x5i=i+16exchangeA[i]withA[j]7exchangeA[i+1]withA[r]8returni+1三、实验总结问题答案：当选取第一个或者最后一个为基准点时，当n个元素相同的时候为最坏n*(n-1)/2；快速排序比较次数最少为θ(nlgn),,最大的比较次数为θ(n2)。实验编号1题目4用分治算法实现题目要求的时间复杂度运算实验内容运用分治的策略将两个已经排好序的序列中，找出第k复杂度为θ(lgm+lgn),其中m和n分别为两个序列的长度。实验目的用分治算法实现题目要求。报告正文一、算法原理如果K是中位数，则（M＋n）是奇数还是偶数是有关系的。如果是奇数，那么中位数唯一，如果是偶数就有两个中位数，可以随便取一个。如果找到的第K大数是x，假如在A的位置是A(x)，在B中的位置是B(x)，则Ax+Bx-1=k是成立的。接下来是具体实现逻辑：1、首先假设K大数在A数组中，首先检查(m/(m+n))*(k-1)，假设其值为A1。然后检查B中(k+1-(n/(m+n))*(k-1))假设为B1，检查A1、B1是否相等，或者大于B中的第(k+1-(n/(m+n))*(k-1))，并且小于(k+1-(n/(m+n))*(k-1))+1个元素。满足条件就可以知道A1就是所求，否则看条件2。2、如果两个条件都不满足，那么需要判断第K个元素是位于A1左边还是右边。如果A1B1，那么K肯定不在A[0,(m/(m+n))*(k-1)]以及B[(k+1-(m/(m+n))*(k-1))+1,n]中；如果A1B1，那么K肯定不在A[(m/(m+n))*(k-1),m]以及B[0,(k+1-(m/(m+n))*(k-1))]中。第K个元素有可能在B中，同理可以假设在B中，再进行一次搜索。复杂度log(m)+log(n)。二、伪代码Searchkth（A,B,alow,ahigh,blow,bhigh,k）1.amid=(alow+ahigh+1)/22.bmid=(blow+bhigh+1)/23.Ifalowahigh4.returnB[blow+k-1]5.Ifblowbhigh6.returnA[alow+k-1]7.IfA[amid]=B[bmid]8.IfA[amid]=B[bmid]9.Ifk=amid-alow+bmid-blow+110.ReturnSearchkth(A,B,alow,ahigh,blow,bmid-1,k)11.Else12.ReturnSearchkth(A,B,amid+1,ahigh,blow,bhigh,k-(amid-alow)-1)13.Else14.Ifk=amid-alow+bmid-blow+115.ReturnSearchkth(A,B,alow,amid-1,blow,bhigh,k)16.Else17.ReturnSearchkth(A,B,alow,ahigh,bmid+1,bhigh,k-(bmid-blow)-1)三、实验总结理解分治策略的三个步骤：分解、解决和合并对于具体问题的具体表现，要善于根据时间复杂度与所学的算法进行结合，找出可以利用的地方。实验编号2题目1矩阵链乘实验内容用动态规划实现矩阵链乘，保证相乘的次数最少。实验目的用动态规划实现矩阵链乘报告正文一、算法原理1Ai..k与Ak+1..j则分别对Ai..k与Ak+1..j加括号的方式也一定是最优的。2m[i,j]为计算矩阵Ai..j所需标量乘法次数的最小值，对于i=j时,矩阵链乘只包含唯一的矩阵Ai,因此不需要做任何标量乘法运算，所以m[i,i]=0;当ij时利用最优子结构来计算m[i,j]。34m数组记录Ai..j最小相乘次数，s数组记录构造最优解所需要的信息，其记录的k值指出了AiAi+1Aj的最优括号化方案的分割点应在AkAk+1之间。5矩阵链乘的时间复杂度为θ(n3)二、伪代码MATRIX-CHAIN-ORDER（p）1.n=p.length-12.Letm[1..n,1..n]ands[1..n-1,2..n]benewtables3.Fori=1ton4.M[i,i]=05.forl=2ton6.Fori=1ton-l+17.J=i+l-18.M[i,j]=无穷9.Fork=itoj-110.Q=m[i,k]+m[k+1,j]+p(i-1)*p(k)*p(j)11.Ifqm[i,j]12.M[i,j]=q13.S[i,j]=kPRINT-OPTIMAL-PARENS(s,i,j)1.ifi==j2.Print“A”3.Elseprint“(”4.PRINT-OPTIMAL-PARENS(s,i,s[i,j])5.PRINT-OPTIMAL-PARENS(s,s[i,j]+1,j)6.Print“）”三、实验总结矩阵链乘主要运用动态规划的思想，这种思想的重要之处在于找到最优的子结构，并设计出最优解的形式。编程是并未遇到什么问题，过程较为顺利。实验编号2题目2最长公共子序列实验内容用动态规划求下列字符串的最长公共子序列。实验目的用动态规划实现寻找最长公共子序列算法。报告正文一、算法原理1X=x1,x2,..xm和Y=y1,y2,...,ynZ=z1,z2,...,zk为X和Y的任意LCS。如果xm=yn,则zk=xm=yn且Zk-1是Xm-1和Yn-1的一个LCS；如果xm≠yn,则zk≠xm意味着Z是Xm-1和Y的一个LCS；如果xm≠yn,则zk≠yn意味着Z是X和Yn-1的一个LCS。2b[i,j]指向表项对应计算c[i,j]时所选择的子问题最优解，过程返回表b和表c，c[m,n]保持X和Y的LCS长度。3LCS4LCS的时间复杂度为θ(m+n),b表的空间复杂度为θ(mn)。二、伪代码LCS-LENGTH（X,Y）1.m=X.length2.n=Y.length3.Letb[1..m,1..n]andc[0..m