西电软件学院算法实验报告模板2份

1、第二次试验一、问题：Matrix-chain product分析：本题是矩阵链乘问题，需要求出最优括号化方案。即在矩阵的乘法链上添加括号来改变运算顺序以使矩阵链乘法的代价降低。可以分析该链乘的一个子段总结一些结论。假设mi,j表示Ai*Aj的链成需要进行的乘法次数（假设j-i足够大），我们可以将Ai*Aj分为两段进行计算：（Ai*Ak）*（Ak+1*Aj）可以得出mi,j的递推公式可以得出，当i=j的时候，mi,j=0。当ij的时候。k的取值范围是i到j-1，对于k的每一个取值都可以得到一个mi,j的值，取出最小值即时mi,j的最优化方案。递推公式如下：可以根据上式得到一个递归算法。本题即是求

2、m1,n的值。用二维数组m存储mi,j的值，用二维数组s来储存应当分割的位置。以本题中第一个矩阵a)为例，可以得出如下矩阵：通过m数组可以得出最少的乘法次数，通过s数组可以输出最优方案。遇到的问题：在输出s数组的结果的时候仍然需要递归调用，需要合适的控制递归的条件。总结：在矩阵链乘问题中可以看出，动态规划结合递归的思想可以快捷的解决很多问题。本题中，重点是归纳出mi,j的递推公式。二、问题：Longest Common Subsequence分析：本题即是最长公共子序列问题。假设有序列Am和序列Bn，显然，对于每一个i,j，都对应着一个公共子序列的长度。假设长度为c，就可以得到一个二维数组cm

3、,n。对于ci,j，当Ai=Bj的时候，问题就转变为求A1.i-1和B1.j-1的公共子序列长度的问题，所以ci，j的长度就是ci-1，j-1 + 1;同理，当Ai != Bj的时候，ci,j应该在ci-1,j与ci,j-1中取最大值。另外，当i或者j等于0的时候，显然c的值为0。由上面所述，可以得到递推公式如下：为了解决这个问题，还如要定义另一个数组用于存放c数组中每一个元素的来源。这个来源其实就反映了公共子串。可以通过箭头表示来源，相连的箭头序列中指向左上方的箭头最多的一串对应的就是最长公共子序列。比如对于题目中给出的第一个例子X: xzyzzyx Y: zxyyzxz可以用一个矩阵表示计

4、算的过程：遇到的问题：在算法中，=是属于会给结果带来不同。在输出子序列的时候，最长公共子序列可能不止一个，但是最终未能解决还是只能输出一个。总结：最长公共子序列问题可以利用动态规划很好的解决。动态规划的思想就是根据规律获得推导公式，然后解决问题。三、问题：Longest Common Substring分析：最长公共子序列问题就是和最长公共子串问题差不多，就是当当Ai != Bj的时候，对应的ci，j置为0。推导公式如下：最终c数组的最大值max对应的就是最长公共子串，只需要将从本位置向前述max-1个的子串即是所求子串。总结：本题就是第二题的一种特殊的情况，即c数组中的值不能从左和上两个方向

5、获取，其他基本相同。在代码上，只需要修改小部分代码就可以实现该问题。四、问题：Max Sum分析：求和最大的子串。这个问题和第三题很像，不过这次不用二维数组而是使用两个标记来标志所求子串的起始位置（maxb）结束位置（maxe）。思路是，对于第i个元素，如果当前元素与目前选中的序列的sum小于0，那么这么序列不会被选择，更新sumb与sume的值；如果sum仍然大于0，则sum可以选中。比较sum与max的值，如果summax，则更新maxb与maxe的值。递推公式如下：遇到的问题：在全是负数时出现问题，后来讲max的初始值设置为第一个元素的值后就能正常了。总结：动态规划能解决很多问题，找到递

6、推公式非常重要。五、问题：Shortest path in multistage graphs. Find the shortest path from 0 to 15 for the following graph.分析：观察本题图的特点，发现可以将图分解为7个部分，以此可以计算到每一个节点的最短的路径。即可求出最终的最短路径。 总结：结合本题中的特殊情况，可以采用适当的方法来处理。第三次实验一、问题：Knapsack Problem. There are 5 items that have a value and weight list below, the knapsack can co

7、ntain at most 100 Lbs. Solve the problem both as fractional knapsack and 0/1 knapsack.分析：本题是背包问题的两个解法。对于部分背包来说比较简单，就是将单位价值大的物品优先放置到背包中，这样就能在背包中获取最大的价值。但是对于0/1背包问题来说，就相对复杂了。可以通过贪心算法解决。经过分析，我们转化这个问题为将n件物品放置到容量为w的容器中。这里，每件物品只可能有一个状态：放入/不放入，我们用0/1来对应。用vi,w来表示前i件物品选出重量不超过w的物品，并且构成的最大的价值。那么，可以分析得出vi,w的递推式

8、。如果i=0或者w=0，显然vI,w = 0;如果第i件物品的重量wiw则i不可能放入容器中；如果i能够放入容器（即wi vi-1,w时才可能会放入。关系式如下这样，我们可以认为，每一次都恰到好处的选择了放或者不放一个物品。直到最后一个物品，我们得到的一定就是最好的结果总结：背包问题是一个典型的贪心算法的例子。在解决问题的时候可以将当前步骤做到最好，然后通过推导，有可能得到一个关系式，这样就能使问题得到解决。在本题中，我们可以通过第i件物品是否应该放在容量的w的背包中进行分析，最终得到了一个递推式。二、问题：A simple scheduling problem. We are given j

9、obs j1, j2 jn, all with known running times t1, t2 tn, respectively. We have a single processor. What is the best way to schedule these jobs in order to minimize the average completion time. Assume that it is a nonpreemptive scheduling: once a job is started, it must run to completion. The following

10、 is an instance。分析：这是一个线程调度问题，通过操作系统课程的学习，我们了解到应当采用短作业优先的调度方式。可以采用快速排序对进程顺序进行排序即可得到调度时间。总结：在进程调度问题中，如果想获取最短的平均周转时间（单线程）应当使用短作业优先的算法。三、问题：单源点最短路径分析：本题中，因为路径中存在负边，所以应当使用bellman-ford算法。为了方便的使用该算法，需要首先创建合适的边的数据结构。这样，在遍历边的时候比较快捷。首先需要初始化每一个节点的d值，源点的d值为0，其他点的d值的初始值为max（一个足够大的数）。表示在初始时，源点到各点都不可达。然后，对每条边进行松弛

11、操作，进行|V|-1次松弛之后，可以得到结果。随后，检测结果，如果依然存在可松弛的节点的话，说明存在权重为负的环路。表明结果不存在。总结：该算法并没有在一开始就计算是否存在权值为负的环路。而是通过结果来分析，如果没有负环路，一定能在松弛循环结束后便不能继续被松弛。由此，可以判断是否存在最短路径。所以，该算法不仅可以判断一个图是否存在最短路径，还能得到最短路径。四、问题：All-pairs shortest paths分析：所有节点对的最短路径问题，应当使用Johnson算法。Johnson算法需要用dijkstra和bellman-ford算法作为子程序。如果图G=（V,E）中所有的边权重都为

12、非负值，可以通过在每一个节点使用dijkstra算法求出所有节点虹之间的最短路径；如果该图包含权值为负的边，但是没有权重为负的环路，那么只要计算一组新的非负权重值，然后使用同样的方法即可。总结：Johnson算法相当于是对dijkstra算法和bellman-ford算法的应用，结合这两个算法，通过使用重新赋值权重来生成非负权重，最终得到所有节点对之间的最短路径。第四次实验一、题目：0/1 Knapsack Problem. There are 5 items that have a value and weight list below, the knapsack can contain a

13、t most 100 Lbs. Solve the problem using back-tracking algorithm and try to draw the tree generated.分析：使用回溯法解决0/1背包问题。可以用一个数组来记录“选中”物品的情况。首先，选择第一件物品，如果超重的话不选择该物品；如果没有超重，继续添加下一个物品，这样选择下去，最终一定可以选择完全部的物品。计算目前选择物品的totalValue值。继续回溯，如果的到新的totalValue值，如果大于前一个值，那么更新该值，并且更新保存选择的数组中。总结：从8皇后问题可以发现回溯法的一般方法。经过代入到

14、这个问题中，发现确实可行。回溯法需要一个合理的递归函数，这个函数的终止条件也需要认真的分析。比如这一题和8皇后问题都可以使用元素的个数作为一个结束条件，另外还需要注意导致“回溯”的位置。二、题目：Solve the 8-Queen problem using back-tracking algorithm.分析：8皇后问题是回溯法的一个典型的例题。假设目前已经在奇葩的前i（i8）行放置了i和皇后并且位置合法。然后我们放置第j（j=i+1）个皇后，先将j放置在第一列，如果合法就放置第j+1个皇后；如果放置在当前列不合法，就将j皇后放置在第二列以此类推，如果全部不行，将会返回调用该函数的上一层函数

15、。如果i的值等于8，说明已经完全摆放成功，就可以输出结果，输出后返回上一层调用，继续查找其他的符合题意的皇后摆放。总结：使用回溯法，能后很好的解决8皇后问题。在使用回溯法是，应当注意如何使用递归调用，尤其是递归调用的结束条件。第2份 算法导论上机实验报告册 班级： 1313012 学号：姓名： 周家炜 教师： 张立勇 实验一 排序算法题目一： 1、题目描述：描述一个运行时间为(nlgn)的算法，给定n个整数的集合S和另一个整数x，该算法能确定S中是否存在两个其和刚好为x的元素。 2、所用算法：1、运用归并排序算法 2、在已经排好序的基础上，对其运用二分查找。 3、算法

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

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

18、述：实现优先级队列，即需要支持以下操作：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:调整堆以满足小顶堆性质，其时间复杂度

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

20、k_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作为基

21、准点进行划分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函数，将这

22、两个序列分别看成是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

23、所需标量乘法次数的最小值，对于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语言中函数的参数列表中二维数组要指明数组大小，但是还没有输入信息的时候并没有方法确定数组大小。 采取的方案：由于此

24、次的例子只有两种情况，因此对于 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。（

25、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,则

26、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,

27、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、

28、题目描述：利用动态规划求出多段图中的最短路径 2、所用策略：动态规划 3、算法分析： （1）可以由图可知，图中的顶点讲图划分7个阶段，分别了解每个阶段可以有几种可供选择的店，引入fk表示状态k到终点状态的最短距离。最优子结构为：当前状态的fk由上个状态的fk-1和状态k-1到状态k的距离决定决策：当前状态应在前一个状态的基础上获得。决策需要满足规划方程,规划方程：f(k)表示状态k到终点状态的最短距离。 （2）多段图最短路径的递归式： 4、结果截图： 无。 5、总结： （1）遇到的问题：无法将多段图的每个阶段点的状态表示并记录下来。并不了解如何将动态规划与贪心算法的如迪杰斯特拉算法进行对比，真

29、正从最优子结构将最短路径表示出来。实验三 贪心算法题目一： 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;

30、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）分数背包问题所采用的贪心策略之不能得到最优解，是由于物品不允许分割，因此，无法保证最终能将

31、背包装满，部分闲置的背包容量使背包的单位重量价值降低了。 （4）分数背包问题采用选择单位重量价值最大的物品顺序进行挑选，其算法的时间复杂度为(nlgn)。 4、结果截图： 5、总结： 使用贪心策略解决0-1背包问题得出的结果并不是最优解，这是由于所用的选择策略不同。题目二： 1、题目描述：一个简单的调度问题，给予工作编号为J1，J2.Jn，已知所以工作的运行时间分别为T1，T2.TN。有一个单独的处理器，为了安排这些工作以到达减少平均完成时间的最好方法是什么。假定它是一个非抢占式调度：一旦工作开始，它必须运行完成。 2、所用策略：贪心策略 3、算法分析： （1）由于是非抢占式调度，所以应该尽量

32、让时间短的工作先做，然后再让时间长的工作做。这里我们使用堆进行排序，建立一个小顶堆，然后每次拿出小顶堆上的最小元素，并使用sum中的公式就可以算出平均完成时间。堆排序的时间复杂度是O(nlgn)，其中BuildMinHeap的时间复杂度是O(n)，而BuildMinHeap()的时间复杂度是O(lgn)。其中HeapExtractMin(N)的时间复杂度是O(lgn)。 4、结果截图： 5、总结： 由于前面对于堆排序和优先队列的MIN-EXTRACT函数的错误没有解决，导致在调度中，需要每次去运行时间最短的工作时发生了错误。题目三： 1、题目描述:以A为源点，求出下图的单源点最短路径。 2、所

33、用算法：由于图中存在负权值，所以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的有向图)