《算法分析与设计课程实验报告》由会员分享,可在线阅读,更多相关《算法分析与设计课程实验报告(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,.