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

算法导论上机实验报告册 班级： 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、题目描述：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、题目描述: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）归并排序运用的是分治思想，时间复杂度为 (nlgn)，能够满足题目要求的运行时间。归并排序的分解部分是每次将数组划分两个部分，时间复杂度为（1）；再对已经分解的两个部分再进行分解直到将数组分解成单个元素为止；解决部分是递归求解排序子序列；合并部分是将已经排序的子序列进行合并得到所要的答案，时间复杂度为(lgn)。（2）二分查找算法的时间复杂度为(lgn)在题目要求的范围内，二分查找的条件为待查的数组为有序序列。算法的主要思想为设定两个数，low指向最低元素，high指向最高元素，然后比较数组中间的元素与待查元素进行比较。如果待查元素小于中间元素，那么表明查找元素在数组的前半段；反之，如果待查元素大于中间元素，那么表明查找元素在数组的后半段。 4、结果截图： 5、总结：（1）在主函数中调用二分查找的时候，参数应该为BinSearch(a,j+1,n,x-aj），从j+1开始遍历而不是都是从第一个开始。（2）遇到的困难为：由于程序语言规定数组的下标从0开始，而算法伪代码要求从1开始，因此在定义数组大小的时候将数字加1，但是在编译运行的时候会得不到想要的结果，出现数组下标访问错误。 采取的解决方案为：在开始定义数组的时候，将数组的大小定义为一个较大的数字，如1000。避免在运行时出现错误，但是造成了空间的浪费。较好的方案为使用动态数组，如malloc函数。题目二： 1、题目描述：实现优先级队列，即需要支持以下操作：INSERT(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:从无序的输入数据数组中构造小顶堆，其时间复杂度为线性时间;HEAP-SORT:对数组进行原址排序，其时间复杂度为(nlgn)。 （2）在堆的基础上实现优先队列INSERT、MAXMUM、EXTRACT-MAX、INCREASE-KEY，时间复杂度为(lgn)。 4、结果截图： 5、总结： 遇到的困难：没有理解将一个序列转换成小顶堆的过程，因此刚开始很难将伪代码用c语言进行实现。从结果可以看出，在编写MAX-EXSTRACT函数的时候，当去掉第一个元素后，程序没有调用MAX-HEAP进行调整堆，因此最后序列是无序状态。题目三： 1、题目描述：实现quick_sort算法，并且回答以下两个问题：（1）待排数组中的元素值都相同的情况下，运用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、总结： 问题答案：（1）当选取第一个或者最后一个为基准点时，当n个元素相同的时候为最坏情况，比较次数为n*(n-1)/2;(2)快速排序比较次数最少为(nlgn),最大的比较次数为(n2)。题目四： 1、题目描述：运用分治的策略将两个已经排好序的序列中，找出第k大的元素，且要求时间复杂度为(lgm+lgn),其中m和n分别为两个序列的长度。 2、所用策略：分治策略 3、算法分析： （1）分解：因为已经是两个独立的的序列，所以不用进行分解。 （2）解决：因为两个序列为已经排好的序列，因此不用分开进行排序。 （3）利用归并排序中的merge函数，将这两个序列分别看成是L和R两个数组，通过开辟一个新的数组，将两个数组合并成一个新的排好序的序列，在根据要求的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时,矩阵链乘只包含唯一的矩阵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_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时所选择的子问题最优解，过程返回表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的最长公共子串的最大长度。 （3）最长公共子串的递归式： （4）最长公共子串的时间复杂度为(mn)，空间复杂度为(mn)。 4、结果截图： 5、总结： 要同上述的最长公共子序列进行对比，区分他们的不同之处。也要理解用动态规划求解时的相同之处和不同之处。题目四： 1、题目描述：给定n个整数（可能为负数）组成的序列，a1,a2.an,求该序列ai+ai+1.aj的子段和的最大值。 2、所用策略：动态规划 3、算法分析: (1)最优子结构：定义当所给整数全为负数的时候，最大子段和为0,则最大子段和为max0,ai+ai+1.+aj,1ijn (2)引入一个辅助数组b,动态规划的分解分为两步：(1)计算辅助数组的值；(2)计算辅助数组的最大值。辅助数组bj用来记录以j为尾的子段以及集合中的最大子段和。 (3)最大子段和的递归式： (4)最大子段和使用动态规划进行计算的时间复杂度为(n)。 4、结果截图： 5、总结： 在求解集合的最大子段和的时候，要对比不同解决方法的不同之处，感受用动态规划解决的便捷。题目五： 1、题目描述：利用动态规划求出多段图中的最短路径 2、所用策略：动态规划 3、算法分析： （1）可以由图可知，图中的顶点讲图划分7个阶段，分别了解每个阶段可以有几种可供选择的店，引入fk表示状态k到终点状态的最短距离。最优子结构为：当前状态的fk由上个状态的fk-1和状态k-1到状态k的距离决定决策：当前状态应在前一个状态的基础上获得。决策需要满足规划方程,规划方程：f(k)表示状态k到终点状态的最短距离。 （2）多段图最短路径的递归式： 4、结果截图： 无。 5、总结： （1）遇到的问题：无法将多段图的每个阶段点的状态表示并记录下来。并不了解如何将动态规划与贪心算法的如迪杰斯特拉算法进行对比，真正从最优子结构将最短路径表示出来。实验三 贪心算法题目一： 1、题目描述：背包问题，即分别计算出在0-1背包和分数背包情况下的计算结果。 2、所用策略：动态规划和贪心策略 3、算法分析： （1）0-1背包问题：所选择的的贪心策略为按照选择单位重量价值最大的物品顺序进行挑选。算法的步骤：设背包容量为C，共有n个物品，物品重量存放在数组Wn中，价值存放在数组Vn中，问题的解存放在数组Xn中。第一步：改变数组W和V的排列顺序，使其按单位重量价值Vi/Wi降序排列，并将数组Xn初始化为0；第二步初始化i=0，设计一个循环，循环终止条件为（WiC），循环体为将第i个物品放入背包：Xi=1;C=C-Wi;i+；最后一步：将结果存入到X数组中。 （2）分数背包问题：所选择的的贪心策略为按照选择单位重量价值最大的物品顺序进行挑选。算法的步骤：设背包容量为C，共有n个物品，物品重量存放在数组Wn中，价值存放在数组Vn中，问题的解存放在数组Xn中。第一步：改变数组W和V的排列顺序，使其按单位重量价值Vi/Wi降序排列，并将数组Xn初始化为0；第二步初始化i=0，设计一个循环，循环终止条件为（WiC），循环体为将第i个物品放入背包：Xi=1;C=C-Wi;i+；最后一步：将结果存入到X数组中Xi=C/Wi。 （3）分数背包问题所采用的贪心策略之不能得到最优解，是由于物品不允许分割，因此，无法保证最终能将背包装满，部分闲置的背包容量使背包的单位重量价值降低了。 （4）分数背包问题采用选择单位重量价值最大的物品顺序进行挑选，其算法的时间复杂度为(nlgn)。 4、结果截图： 5、总结： 使用贪心策略解决0-1背包问题得出的结果并不是最优解，这是由于所用的选择策略不同。题目二： 1、题目描述：一个简单的调度问题，给予工作编号为J1，J2.Jn，已知所以工作的运行时间分别为T1，T2.TN。有一个单独的处理器，为了安排这些工作以到达减少平均完成时间的最好方法是什么。假定它是一个非抢占式调度：一旦工作开始，它必须运行完成。 2、所用策略：贪心策略 3、算法分析： （1）由于是非抢占式调度，所以应该尽量让时间短的工作先做，然后再让时间长的工作做。这里我们使用堆进行排序，建立一个小顶堆，然后每次拿出小顶堆上的最小元素，并使用sum中的公式就可以算出平均完成时间。堆排序的时间复杂度是O(nlgn)，其中BuildMinHeap的时间复杂度是O(n)，而BuildMinHeap()的时间复杂度是O(lgn)。其中HeapExtractMin(N)的时间复杂度是O(lgn)。 4、结果截图： 5、总结： 由于前面对于堆排序和优先队列的MIN-EXTRACT函数的错误没有解决，导致在调度中，需要每次去运行时间最短的工作时发生了错误。题目三： 1、题目描述:以A为源点，求出下图的单源点最短路径。 2、所用算法：由于图中存在负权值，所以Dijkstra算法无法使用，因此采用Bellman-Ford算法求取图的单源点最短路径。 3、算法分析： （1）Bellman-Ford算法通过对边进行松弛操作来渐近地降低从源点A到每个结点的最短路径的估计值，直到该估计值与实际的最短路径权重(A,v)相同为止。该算法返回TRUE值当且仅当输入图中不包含可以从源结点到达的权重为负值的环路。 （2）Bellman-Ford算法的执行步骤：1、初始化：将除源点外的所有顶点的最短距离估计值dv+, ds0；2、迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）3、检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在dv中。 （3）算法适用范围和条件： 1.单源最短路径(从源点A到其它所有顶点v)； 2.有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)； 3.边权可正可负(如有负权回路输出错误提示)。 （4）Bellman-Ford算法的时间复杂度为(VE)。 4、结果截图： 无 5、总结： 这次的实验并没有成功，按照伪代码进行编写代码，编译通过的时候却没有办法输出结果，或者结果是错误的。题目四： 1、题目描述：求题3图中每对结点的最短路径问题 2、所用算法：Floyd-Warshall算法。 3、算法分析： （1）设G的顶点为V=1,2,3.n，对于任意一对顶点i,j属于V，假设i到j有路径且中间节点皆属于集合1,2,3.k，P是其中的一条最小权值路径。就是i到j的最短路径P所通过的中间顶点最大不超过k。 （2）设d(k)ij为从结点i到结点j的所有中间结点全部取自结合1,2,.,k的一条最短路径的权重。d(k)ij的递归定义为 （3）Floyd-Warsha