《算法分析与设计课程实验报告》由会员分享，可在线阅读，更多相关《算法分析与设计课程实验报告（25页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计课程实验报告算法分析与设计课程实验报告班班 级：级： 131213131213 学学 号：号： 13121XXX13121XXX 姓姓 名：名： XXXXXX 指导老师：指导老师： 邓邓 凡凡 目录目录算法分析与设计课程实验报告.1实验一 排序.11. 课本练习 2.3-7 .12. 实现优先队列.23.快速排序.24. 第 k 大元素.3实验二 动态规划.41. 矩阵链乘.42. 最长公共子序列.53. 最长公共子串.74. 最大和.95. 最短路径.10实验三 贪心策略.111. 背包问题.112. 任务调度.143. 单源点最短路径.154. 任意两点间最短路径.16实验四
2、 回溯法.181. 0-1 背包问题 .182. 8-Queen 问题 .21实验一实验一 排序排序1.1.课本练习课本练习 2.3-7(1)问题描述描述一个运行时间为 (nlgn)的算法，给定 n 个整数的集合 S 和另一个整数 x,该算法能确定 S 中是否存在两个其和刚好是 x 的元素。(2)问题分析该问题首先要进行排序，然后用二分查找法判断 S 中是否存在两个其和刚好是 x 的元素，因为时间复杂度为(nlgn)，所以可以采用归并排序。(3)算法分析归并排序的思想是将 n 个元素分成各含 n/2 个元素的子序列，然后对两个子序列递归地进行排序，最后合并两个已排序的子序列得到排序结果。二分查
3、找的思想是对于集合中的每一个数字，用二分法找到 x-Si的位置，若存在且不为其本身，则输出 S 中存在有两个和等于 x 的元素；否则，不存在。(4)实验结果2.2.实现优先队列实现优先队列(1)问题描述实现优先队列，维护一组元素构成的集合 S。(2)问题分析优先队列是基于堆排序的。首先将集合 S 中的元素进行堆排序。当进行操作时，要不断维护集合 S 的有序性，即要不断地调整堆。(3)算法分析本程序中主要的函数有 INSERT()：需要调用 INCREASE_KEY()来维护堆，其时间复杂度为 O（lgn），函数 MAXIMUM()仅需要返回S1，时间复杂度为 (1)，函数 EXTRACT_MA
4、X()需要调用堆排序中的 MAX_HEAPIFY，时间复杂度为 O(lgn)，函数 INCREASE_KEY()更新结点到根结点的路径长度为 O(lgn)，时间复杂度为 O(lgn)。3.3.快速排序快速排序(1)问题描述实现快速排序(2)问题分析快速排序采用了分治策略。数组 Ap.r被划分成两个子数组Ap.q-1和 Aq+1.r，使得 Ap.q-1中的每个元素都小于等于A(q)，而且，小于等于 Aq+1.r中的元素。然后通过递归调用快速排序，对子数组 Ap.q-1和 Aq+1.r排序。最后将两个数组合并。(3)算法分析快速排序不需要额外的辅助空间，其时间复杂度在平均情况下为O(nlgn)，最
5、坏情况下为 O()。快速排序是不稳定的排序算法。2n(4)实验结果4.第第 k k 大元素大元素(1)问题描述给定两个大小分别为 m 和 n 的有序序列，采用分治法求解两个序列合起来的第 k 大元素，使得时间复杂度为 O(lgm+lgn)。(2)问题分析将 A 平均分为前后两个部分，前半部分有 x 个元素，后半部分有 m-x 个元素。因为 A 有序，所以后半部分的所有元素均大于前半部分。Ax为后半部分的第一个元素。将 B 也平均分为前后两个部分，前半部分有 y 个元素，后半部分有 n-y 个元素。By是后半部分的第一个元素。(3)算法分析由于两个数组都是平均划分的，我们可以近似地认为 x=m/
6、2, y=n/2。假设 Axx+y，合并后第 k 大元素必然在 Ax后面。所以，原来在 A 数组中前半部分可以排除掉。实验二实验二 动态规划动态规划1.1.矩阵链乘矩阵链乘(1)题目要求给定 n 个矩阵链，矩阵 Ai的规模为 pi-1*pi（1in），求完全括号化方案，使得 A1A2,.An所需标量乘法次数最小。(2)题目分析本问题满足最优子结构性质（矩阵链乘 AiAi+1.Aj的最优化括号方案包含其子问题 AiAi+1.Ak和 Ak+1Ai+1.Aj的最优括号方案）：假设 AiAi+1,.Aj所的最优括号化方案的分割点在 Ak和 Ak+1之间。那么，继续对前缀子链 AiAi+1,.Ak优化我
7、们应该采用独立求解它时所得的最优化方案。同理，在子链 Ak+1Ak+2,.Aj进行括号化的方法，就是它自身的最优化括号方案。所以可以用动态规划来求解。(3)算法分析为了构造一个矩阵链乘问题的最优解，我们可以将问题划分为两个子问题（AiAi+1.Ak和 Ak+1Ai+1.Aj的最优括号化问题），求出子问题的解，然后将子问题的最优解组合起来，同时必须保证考察了所以的可能的分割点。设 mi,j表示计算 AiAi+1.Aj所需标量乘法次数的最小值，则原问题的最优解就是 m1,n。AiAi+1.Aj的最小代价括号方案的递归求解公式为：本程序的主要函数是基于上述递归式的函数 MatrixChainOrde
8、r(),它采用自底向上表格法,根据输入的矩阵规模数组，计算 mi,j，同时构造一个辅助数组 si,j用来记录最优值 mi,j对应的分割点k，最后可以根据 si,j的值构造最优解(调用函数 PrintOptimal(),该算法的时间复杂度是 O(n3)。(4)实验结果实验结果如图所示：2.2.最长公共子序列最长公共子序列(1)问题描述用动态规划方法求两个字符序列 X 和 Y 的最长公共子序列。(2)问题分析LCS 问题的最优子结构是：设 X=和 Y=为两个序列，Z=为 X 与 Y 的任一 LCS。a.如果 xm=yn,则 zk=xm=yn 且 Zk-1 是 Xm-1 与 Yn-1 的一个 LCS
9、。b.如果 xmyn,则 zkxm 意味着 Z 是 Xm-1 与 Y 的一个 LCS。c.如果 xmyn,则 zkyn 意味着 Z 是 X 与 Yn-1 的一个 LCS。上述最优子结构意味着在求解 X 与 Y 的一个 LCS 时，需要求解一个或两个子问题，如果 xm=yn,求解 Xm-1 与 Yn-1 的一个 LCS；如果xmyn,需要求解 Xm-1 与 Y 的一个 LCS 和 X 与 Yn-1 的一个 LCS。用 ci,j表示序列 X1.i与 Y1.j的最长公共子序列的长度，则 cm,n为 X 与 Y 的最长公共子序列长度。根据最优子结构的性质，ci,j的递归式为：(3)算法分析本程序的主要
10、函数是基于递归式的 LCSLength()，它的作用是构造 ci,j表，用来存储 LCS 的长度，同时构造一个辅助数组 bi,j存储计算 ci,j时指向所选择的子问题最优解，用来帮助构造最优解（调用函数 printLCS()），该算法的时间复杂度为 O(n3).(4)实验结果实验结果如下图所示：所遇到的问题：定义函数 printLCS()时出现错误 type of formal parameter 1 is incomplete,通过在参数列表中添加二维数组的大小来解决的。3.3.最长公共子串最长公共子串(1)问题描述给定两个字符串 X 和 Y，求 X 和 Y 的最长公共子串。(2)题目分析本
11、问题与 LCS 问题相似，不同之处在于 LCS 问题不要子序列是连续的，但子串要求是连续的。最长公共子串问题满足最优子结构性质：设 X=和 Y=为两个字符串，Z=为 X 与 Y 的任一子串。如果 xm=yn,则 zk=xm=yn且 Zk-1 是 Xm-1 与 Yn-1 的一个子串。上述最优子结构意味着在求解 X 与 Y 的一个子串时，需要求解一个：如果 xm=yn,求解 Xm-1 与 Yn-1 的一个子串。用 ci,j表示字符串 X1.i与 Y1.j的最长公共子串的长度，则 cm,n为 X 与 Y 的最长公共子串长度。根据最优子结构的性质，ci,j的递归式为：(3)算法分析本程序的主要函数是基
12、于递归式的 LCSSubLength()，它的作用是构造 ci,j表，用来存储子串的长度，同时构造一个辅助数组bi,j存储计算 ci,j时指向所选择的子问题最优解，用来帮助构造最优解（调用函数 printLCS()），该算法的时间复杂度为 O(n3).(4)实验结果4.4.最大和最大和(1)问题描述给定 n 个整数（可能为负数）组成的序列A=，求该序列连续的子段和的最大值。(2)问题分析由上述问题可以将最大字段和定义为： 设 bj=max(sum(i,j),即以 aj 为结束元素的连续数组的最大和。则 X=max（bj），则原问题所求为 bn，bj的递归式为：(3)算法分析基于上述递归式的函数
13、 DPMaxSum()是本程序的主要函数，它用来计算最大字段和，时间复杂度为 O(n).(4)实验结果5.5.最短路径最短路径(1)题目要求根据输入的带权有向图 G的 n*n 矩阵 W，求图中源点到目的顶点的最短路径。(2)题目分析这个问题需要用动态规划来解决，可以用 Floyd-Warshall 算法来实现。(3)算法分析首先考虑其最优子结构特性。总结如下：设 G的两个不同的顶点 i,jV=1,2,.,n,p 是从 i 到 j期间不经过k+1,k+2,.,n的最短路径。则有：a.若 p 不经过顶点 k，则 p 也是从 i 到达 j 期间不经过k,k+1,.,n的最短路径。b若 p 经过顶点 k，即 p:ikj。我们将前半段 ik 记为 p1,后半段 kj 记为 p2,。则 p1是从 i 到 k 期间不经过k,k+1,.,n的最短路径，p2是从 k 到 j 期间不经过k,k+1,.
