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