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

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 、题目描述： .6.2、所用策略：.63、算法分析：.64、 结果截图：.65、 总结： .7实验二 动态规划 .7题目一： .71、题目描述：.72、所用策略：.73、算法分析

2、：.74、结果截图：.85、总结： .8题目二： .91、题目描述：.92、所用策略：.93、算法分析：.94、结果截图：.95、总结： .10题目三： .101、题目描述：.102、所用策略：.103、算法分析：.104 、结果截图： .11.5、总结： .12题目四： .121、题目描述： .122、所用策略： .123、算法分析 : .124、结果截图： .125、总结： .13题目五： .131、题目描述： .132、所用策略： .133、算法分析： .134、结果截图： .145、总结： .14实验三 贪心算法 .14题目一： .141、题目描述： .142、所用策略： .143、算

3、法分析： .144、结果截图： .155、总结： .16题目二： .161 、题目描述： .16.2、所用策略：.163、算法分析：.164、结果截图：.175、总结： .17题目三： .171、题目描述 : .172、所用算法：.183、算法分析：.184、结果截图：.185、总结： .19题目四： .191、题目描述：.192、所用算法：.193、算法分析：.19实验四 回溯法 .19题目一： .191、题目描述：.202、所用策略：.203、算法分析：.20题目二： .211、题目描述：.212 、所用策略： .21.3 、算法分析：21.实验一 排序算法题目一：1、题目描述：描述一个运

4、行时间为 (nlgn) 的算法，给定 n 个整数的集合 S 和另一个整数 x，该算法能确定 S 中是否存在两个其和刚好为 x 的元素。2、所用算法： 1、运用归并排序算法2、在已经排好序的基础上，对其运用二分查找。3、算法分析：（ 1）归并排序运用的是分治思想，时间复杂度为 (nlgn) ，能够满足题目要求的运行时间。 归并排序的分解部分是每次将数组划分两个部分，时间复杂度为（ 1 ）；再对已经分解的两个部分再进行分解直到将数组分解成单个元素为止； 解决部分是递归求解排序子序列；合并部分是将已经排序的子序列进行合并得到所要的答案， 时间复杂度为(lgn) 。（ 2）二分查找算法的时间复杂度为

5、(lgn) 在题目要求的范围内，二分查找的条件为待查的数组为有序序列。 算法的主要思想为设定两个数， low 指向最低元素， high 指向最高元素，然后比较数组中间的元素与待查元素进行比较。 如果待查元素小于中间元素， 那么表明查找元素在数组的前半段；反之，如果待查元素大于中间元素，那么表明查找元素在数组的后半段。4、结果截图：.5、总结：（1）在主函数中调用二分查找的时候，参数应该为 BinSearch(a,j+1,n,x-a j ），从 j+1 开始遍历而不是都是从第一个开始。（ 2）遇到的困难为：由于程序语言规定数组的下标从0 开始，而算法伪代码要求从1 开始，因此在定义数组大小的时候

6、将数字加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、所

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

8、X 、INCREASE-KEY，时间复杂度为 (lgn) 。4、结果截图：.5、总结：遇到的困难：没有理解将一个序列转换成小顶堆的过程，因此刚开始很难将伪代码用 c 语言进行实现。从结果可以看出，在编写 MAX-EXSTRACT 函数的时候， 当去掉第一个元素后， 程序没有调用 MAX-HEAP 进行调整堆，因此最后序列是无序状态。题目三：1、题目描述：实现 quick_sort算法，并且回答以下两个问题：（1）待排数组中的元素值都相同的情况下，运用quick_sort需要进行多少次比较？（2 ）对于 n 个元素的数组， 运用 quick_sort举出需要进行比较次数的上限和下限是多少？2、所

9、用算法：快速排序算法.3、算法分析：快速排序采用分治策略，时间复杂度为(nlgn), 但是最坏情况下为 (n 2 ),并且快速排序算法属于原地排序，并不需要开辟空间。快速排序复杂的步骤为其分解的步骤，分解的过程：数组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)快

10、速排序比较次数最少为 (nlgn), 最大的比较次数为 (n 2)。.题目四：1、题目描述：运用分治的策略将两个已经排好序的序列中，找出第 k 大的元素，且要求时间复杂度为 (lgm+lgn), 其中 m 和 n 分别为两个序列的长度。2、所用策略：分治策略3、算法分析：（1）分解：因为已经是两个独立的的序列，所以不用进行分解。（2）解决：因为两个序列为已经排好的序列，因此不用分开进行排序。（3）利用归并排序中的 merge 函数，将这两个序列分别看成是 L 和 R 两个数组，通过开辟一个新的数组， 将两个数组合并成一个新的排好序的序列，在根据要求的k 值，对新的数组进行取值。4、结果截图：.

11、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; 当 i<

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

13、L_PARENS 函数写两遍，大体的实现过程相同，只是数组的大小有所改变。并没有解决这个情况，造成代码的冗余。.题目二：1、题目描述：用动态规划求下列字符串的最长公共子序列（LCS）2、所用策略：动态规划3、算法分析：（ 1）最优子结构：令 X=<x1,x2,.xm> 和 Y=<y1,y2,.,yn> 为两个序列， Z=<z1,z2,.,zk> 为 X 和 Y 的任意 LCS。1、如果 xm=yn, 则 zk=xm=yn 且 Zk-1 是 Xm-1 和 Yn-1 的一个 LCS.2、如果 xm yn, 则 zk xm 意味着 Z 是 Xm-1 和 Y 的一个

14、 LCS；3、如果 xm yn,则 zk yn 意味着 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、

15、所用策略：动态规划3、算法分析：（1）最优子结构：令 X=<x1,x2,.xm> 和 Y=<y1,y2,.,yn> 为两个序列， Z=<z1,z2,.,zk> 为 X 和 Y 的任意最长公共子串。 1 、.如果 xm=yn, 则 zk=xm=yn 且 Zk-1 是 Xm-1 和 Yn-1 的一个最长公共子串 .2、如果 xm yn, 则 zk xm 意味着 Z 是 Xm-1 和 Y 的一个最长公共子串； 3、如果 xm yn, 则 zkyn 意味着 Z 是 X 和 Yn-1 的一个最长公共子串。（2）定义 Li,j 为以 xi 和 yj 为结尾的相同子串的最

16、大长度。记录着 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,

17、动态规划的分解分为两步： (1) 计算辅助数组的值； (2) 计算辅助数组的最大值。辅助数组bj 用来记录以 j 为尾的子段以及集合中的最大子段和。(3) 最大子段和的递归式：(4) 最大子段和使用动态规划进行计算的时间复杂度为 (n) 。4、结果截图：.5、总结：在求解集合的最大子段和的时候， 要对比不同解决方法的不同之处，感受用动态规划解决的便捷。题目五：1、题目描述：利用动态规划求出多段图中的最短路径2、所用策略：动态规划3、算法分析：（1）可以由图可知，图中的顶点讲图划分7 个阶段，分别了解每个阶段可以有几种可供选择的店，引入 fk 表示状态 k 到终点状态的最短距离。最优子结构为：当

18、前状态的 fk 由上个状态的 fk-1和状态 k-1 到状态 k 的距离决定决策：当前状态应在前一个状态的基.础上获得。决策需要满足规划方程 ,规划方程： f(k) 表示状态 k 到终点状态的最短距离。（2）多段图最短路径的递归式：4、结果截图：无。5、总结：（1）遇到的问题：无法将多段图的每个阶段点的状态表示并记录下来。并不了解如何将动态规划与贪心算法的如迪杰斯特拉算法进行对比，真正从最优子结构将最短路径表示出来。实验三 贪心算法题目一：1、题目描述：背包问题，即分别计算出在0-1 背包和分数背包情况下的计算结果。2、所用策略：动态规划和贪心策略3、算法分析：（1）0-1 背包问题： 所选择

19、的的贪心策略为按照选择单位重.量价值最大的物品顺序进行挑选。算法的步骤：设背包容量为 C，共有 n 个物品，物品重量存放在数组 Wn 中，价值存放在数组 Vn中，问题的解存放在数组 Xn 中。第一步：改变数组 W 和 V 的排列顺序，使其按单位重量价值 Vi/Wi 降序排列，并将数组 Xn 初始化为 0；第二步初始化 i=0 ，设计一个循环，循环终止条件为（Wi>C ），循环体为将第 i 个物品放入背包：Xi=1;C=C-Wi;i+；最后一步：将结果存入到X 数组中。（2）分数背包问题： 所选择的的贪心策略为按照选择单位重量价值最大的物品顺序进行挑选。算法的步骤：设背包容量为C，共有 n

20、 个物品，物品重量存放在数组 Wn 中，价值存放在数组 Vn 中，问题的解存放在数组 Xn 中。第一步：改变数组 W 和 V 的排列顺序，使其按单位重量价值 Vi/Wi 降序排列，并将数组 Xn 初始化为 0；第二步初始化 i=0 ，设计一个循环，循环终止条件为（Wi>C ），循环体为将第 i 个物品放入背包：Xi=1;C=C-Wi;i+；最后一步：将结果存入到X 数组中 Xi=C/Wi。（3 ）分数背包问题所采用的贪心策略之不能得到最优解，是由于物品不允许分割，因此，无法保证最终能将背包装满，部分闲置的背包容量使背包的单位重量价值降低了。（4 ）分数背包问题采用选择单位重量价值最大的物

21、品顺序进行挑选，其算法的时间复杂度为(nlgn) 。4 、结果截图：.5 、总结：使用贪心策略解决0-1 背包问题得出的结果并不是最优解，这是由于所用的选择策略不同。题目二：1 、题目描述：一个简单的调度问题， 给予工作编号为J1，J2.Jn，已知所以工作的运行时间分别为T1 ，T2.TN 。有一个单独的处理器，为了安排这些工作以到达减少平均完成时间的最好方法是什么。假定它是一个非抢占式调度：一旦工作开始，它必须运行完成。2 、所用策略：贪心策略3 、算法分析：（ 1）由于是非抢占式调度，所以应该尽量让时间短的工作先做，然后再让时间长的工作做。这里我们使用堆进行排序，建立一个小顶堆，然后每次拿

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

23、法使用，因此采用 Bellman-Ford算法求取图的单源点最短路径。3、算法分析：（1）Bellman-Ford算法通过对边进行松弛操作来渐近地降低从源点 A 到每个结点的最短路径的估计值，直到该估计值与实际的最短路径权重 ? (A,v) 相同为止。该算法返回 TRUE 值当且仅当输入图中不包含可以从源结点到达的权重为负值的环路。（2 ）Bellman-Ford算法的执行步骤： 1、初始化：将除源点外的所有顶点的最短距离估计值 dv + , ds 0；2 、迭代求解：反复对边集 E 中的每条边进行松弛操作，使得顶点集 V 中的每个顶点 v 的最短距离估计值逐步逼近其最短距离； （运行 |v|

24、-1 次）3、检验负权回路： 判断边集 E 中的每一条边的两个端点是否收敛。 如果存在未收敛的顶点，则算法返回 false 表明问题无解；否则算法返回，并且从源点可达的顶点 v 的最短距离保存在 dv 中。 true（3）算法适用范围和条件：1.单源最短路径 (从源点 A 到其它所有顶点v)；2.有向图 & 无向图 (无向图可以看作(u,v),(v,u) 同属于边集 E 的有向图 )；3.边权可正可负 (如有负权回路输出错误提示)。（4）Bellman-Ford算法的时间复杂度为 (VE)。4、结果截图：无.5、总结：这次的实验并没有成功，按照伪代码进行编写代码，编译通过的时候却没有办法输出结果，或者结果是错误的。题目四：1、题目描述：求题3 图中每对结点的最短路径问题2、所用算法： F