西电算法导论上机实验报告

《西电算法导论上机实验报告》由会员分享，可在线阅读，更多相关《西电算法导论上机实验报告（25页珍藏版）》请在金锄头文库上搜索。

1、 算法导论上机实验报告册 班级： xxxxxx 学号： xxxxxxx 姓名： xxxx 教师： xxxxxx 目 录实验一 排序算法1题目一：11、题目描述：12、所用算法：13、算法分析：14、结果截图：15、总结：2题目二：31、题目描述：32、所用算法：33、算法分析：34、结果截图：35、总结：4题目三：41、题目描述：42、所用算法：43、算法分析：54、结果截图：55、总结：5题目四：61、题目描述：62、所用策略：63、算法分析：64、 结果截图：65、 总结：7实验二 动态规划7题目一：71、题目描述：72、所用策略：73、算法分析：74、结果截图：85、总结：8题目二：91

2、、题目描述：92、所用策略：93、算法分析：94、结果截图：95、总结：10题目三：101、题目描述：102、所用策略：103、算法分析：104、结果截图：115、总结：11题目四：111、题目描述：122、所用策略：123、算法分析:124、结果截图：125、总结：13题目五：131、题目描述：132、所用策略：133、算法分析：134、结果截图：145、总结：14实验三 贪心算法14题目一：141、题目描述：142、所用策略：143、算法分析：144、结果截图：155、总结：16题目二：161、题目描述：162、所用策略：163、算法分析：164、结果截图：175、总结：17题目三：171

3、、题目描述:172、所用算法：173、算法分析：174、结果截图：185、总结：18题目四：181、题目描述：192、所用算法：193、算法分析：19实验四 回溯法19题目一：191、题目描述：192、所用策略：193、算法分析：19题目二：201、题目描述：212、所用策略：213、算法分析：21实验一 排序算法题目一： 1、题目描述：描述一个运行时间为(nlgn)的算法，给定n个整数的集合S和另一个整数x，该算法能确定S中是否存在两个其和刚好为x的元素。 2、所用算法：1、运用归并排序算法 2、在已经排好序的基础上，对其运用二分查找。 3、算法分析：（1）归并排序运用的是分治思想，时间复杂

4、度为 (nlgn)，能够满足题目要求的运行时间。归并排序的分解部分是每次将数组划分两个部分，时间复杂度为（1）；再对已经分解的两个部分再进行分解直到将数组分解成单个元素为止；解决部分是递归求解排序子序列；合并部分是将已经排序的子序列进行合并得到所要的答案，时间复杂度为(lgn)。（2）二分查找算法的时间复杂度为(lgn)在题目要求的范围内，二分查找的条件为待查的数组为有序序列。算法的主要思想为设定两个数，low指向最低元素，high指向最高元素，然后比较数组中间的元素与待查元素进行比较。如果待查元素小于中间元素，那么表明查找元素在数组的前半段；反之，如果待查元素大于中间元素，那么表明查找元素在

5、数组的后半段。 4、结果截图： 5、总结：（1）在主函数中调用二分查找的时候，参数应该为BinSearch(a,j+1,n,x-aj），从j+1开始遍历而不是都是从第一个开始。（2）遇到的困难为：由于程序语言规定数组的下标从0开始，而算法伪代码要求从1开始，因此在定义数组大小的时候将数字加1，但是在编译运行的时候会得不到想要的结果，出现数组下标访问错误。 采取的解决方案为：在开始定义数组的时候，将数组的大小定义为一个较大的数字，如1000。避免在运行时出现错误，但是造成了空间的浪费。较好的方案为使用动态数组，如malloc函数。题目二： 1、题目描述：实现优先级队列，即需要支持以下操作：INS

6、ERT(S,x):把元素x插入到集合S中；MAXMUM(S):返回S中具有最大key的元素；EXTRACT-MAX(S):去掉并返回S中的具有最大key的元素；INCREASE-KEY(S,x,k)：将元素x的关键字值增到k。 2、所用算法：堆排序，运用堆来实现优先队列。 3、算法分析： （1）堆排序算法是引用堆这个数据结构进行信息管理。堆排序的时间复杂度是(nlgn),但是与归并排序不同的是堆排序具有空间的原址性，任何时候都只需要常数个额外的元素空间存储临时数据。堆排序算法分为3个过程，MAX-HEAPIEY:调整堆以满足小顶堆性质，其时间复杂度为(lgn)；BUILD-MAXHEAP:从无

7、序的输入数据数组中构造小顶堆，其时间复杂度为线性时间;HEAP-SORT:对数组进行原址排序，其时间复杂度为(nlgn)。 （2）在堆的基础上实现优先队列INSERT、MAXMUM、EXTRACT-MAX、INCREASE-KEY，时间复杂度为(lgn)。 4、结果截图： 5、总结： 遇到的困难：没有理解将一个序列转换成小顶堆的过程，因此刚开始很难将伪代码用c语言进行实现。从结果可以看出，在编写MAX-EXSTRACT函数的时候，当去掉第一个元素后，程序没有调用MAX-HEAP进行调整堆，因此最后序列是无序状态。题目三： 1、题目描述：实现quick_sort算法，并且回答以下两个问题：（1）

8、待排数组中的元素值都相同的情况下，运用quick_sort需要进行多少次比较？（2）对于n个元素的数组，运用quick_sort举出需要进行比较次数的上限和下限是多少？ 2、所用算法：快速排序算法 3、算法分析：快速排序采用分治策略，时间复杂度为(nlgn),但是最坏情况下为(n2),并且快速排序算法属于原地排序，并不需要开辟空间。快速排序复杂的步骤为其分解的步骤，分解的过程：数组Ap.r被划分为两个子数组Ap.q-1和Aq+1.r,使得Ap.q-1中的每个元素都小于Aq,而Aq也小于等于Aq+1.r中的每个元素。而在实现的过程总是选择将Ar作为基准点进行划分Ap.r数组。 4、结果截图： 5

9、、总结： 问题答案：（1）当选取第一个或者最后一个为基准点时，当n个元素相同的时候为最坏情况，比较次数为n*(n-1)/2;(2)快速排序比较次数最少为(nlgn),最大的比较次数为(n2)。题目四： 1、题目描述：运用分治的策略将两个已经排好序的序列中，找出第k大的元素，且要求时间复杂度为(lgm+lgn),其中m和n分别为两个序列的长度。 2、所用策略：分治策略 3、算法分析： （1）分解：因为已经是两个独立的的序列，所以不用进行分解。 （2）解决：因为两个序列为已经排好的序列，因此不用分开进行排序。 （3）利用归并排序中的merge函数，将这两个序列分别看成是L和R两个数组，通过开辟一个

10、新的数组，将两个数组合并成一个新的排好序的序列，在根据要求的k值，对新的数组进行取值。4、 结果截图：5、 总结： （1）理解分治策略的三个步骤：分解、解决和合并对于具体问题的具体表现，要善于根据时间复杂度与所学的算法进行结合，找出可以利用的地方。 实验二 动态规划题目一： 1、题目描述：用动态规划实现矩阵链乘，保证相乘的次数最少。 2、所用策略：动态规划 3、算法分析： （1）最优子结构为：如果最优的加括号的方式将其分解为Ai.k与Ak+1.j的乘积，则分别对Ai.k与Ak+1.j加括号的方式也一定是最优的。 （2）定义mi,j为计算矩阵Ai.j所需标量乘法次数的最小值，对于i=j时,矩阵链

11、乘只包含唯一的矩阵Ai,因此不需要做任何标量乘法运算，所以mi,i=0;当ij时利用最优子结构来计算mi,j。 （3）矩阵链乘的递归式： （4）在算法设计的时候，需要m数组记录Ai.j最小相乘次数，s数组记录构造最优解所需要的信息，其记录的k值指出了AiAi+1Aj的最优括号化方案的分割点应在AkAk+1之间。 （5）矩阵链乘的时间复杂度为(n3) 4、结果截图： 5、总结： 遇到的问题：在构建m数组和s数组的时候需要构建二维数组，而c语言中函数的参数列表中二维数组要指明数组大小，但是还没有输入信息的时候并没有方法确定数组大小。 采取的方案：由于此次的例子只有两种情况，因此对于 MATRIX_

12、CHAIN_ORDER函数和PRINT_OPTIMAL_PARENS函数写两遍，大体的实现过程相同，只是数组的大小有所改变。并没有解决这个情况，造成代码的冗余。题目二： 1、题目描述：用动态规划求下列字符串的最长公共子序列（LCS） 2、所用策略：动态规划 3、算法分析：（1） 最优子结构：令X=和Y=为两个序列，Z=为X和Y的任意LCS。1、如果xm=yn,则zk=xm=yn且Zk-1是Xm-1和Yn-1的一个LCS.2、如果xmyn,则zkxm意味着Z是Xm-1和Y的一个LCS；3、如果xmyn,则zkyn意味着Z是X和Yn-1的一个LCS。（2） 定义一个bi,j指向表项对应计算ci,j

13、时所选择的子问题最优解，过程返回表b和表c，cm,n保持X和Y的LCS长度。（3） LCS的递归式为： （4） LCS的时间复杂度为(m+n),b表的空间复杂度为(mn)。 4、结果截图： 5、总结： 用动态规划求取最长公共子序列的时候，要理解b数组的用途和使用。 遇到的困难：编写的代码无法针对字符串大小未定情况下，进行求解LCS这导致了代码的冗余。题目三： 1、题目描述：用动态规划求取以下字符串的最长公共子串。 2、所用策略：动态规划 3、算法分析： （1）最优子结构：令X=和Y=为两个序列，Z=为X和Y的任意最长公共子串。1、如果xm=yn,则zk=xm=yn且Zk-1是Xm-1和Yn-1的一个最长公共子串.2、如果xmyn,则zkxm意味着Z是Xm-1和Y的一个最长公共子串；3、如果xmyn,则zkyn意味着Z是X和Yn-1的一个最长公共子串。 （2）定义Li,j为以xi和yj为结尾的相同子串的最大长度。记录着X和Y的最长公共子串的最大长度