算法分析与设计课程实验报告班 级： 131213 学 号： 13121XXX 姓 名： XXX 指导老师： 邓 凡 目录算法分析与设计课程实验报告 1实验一 排序 11. 课本练习2.3-7 12. 实现优先队列 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) 问题描述描述一个运行时间为(nlgn)的算法，给定n个整数的集合S和另一个整数x,该算法能确定S中是否存在两个其和刚好是x的元素2)问题分析该问题首先要进行排序，然后用二分查找法判断S中是否存在两个其和刚好是x的元素，因为时间复杂度为(nlgn)，所以可以采用归并排序3) 算法分析 归并排序的思想是将n个元素分成各含n/2个元素的子序列，然后对两个子序列递归地进行排序，最后合并两个已排序的子序列得到排序结果。
二分查找的思想是对于集合中的每一个数字，用二分法找到x-S[i]的位置，若存在且不为其本身，则输出S中存在有两个和等于x的元素；否则，不存在4) 实验结果2. 实现优先队列(1) 问题描述实现优先队列，维护一组元素构成的集合S2) 问题分析 优先队列是基于堆排序的首先将集合S中的元素进行堆排序当进行操作时，要不断维护集合S的有序性，即要不断地调整堆3) 算法分析本程序中主要的函数有INSERT()：需要调用INCREASE_KEY()来维护堆，其时间复杂度为O（lgn），函数MAXIMUM()仅需要返回S[1]，时间复杂度为(1)，函数EXTRACT_MAX()需要调用堆排序中的MAX_HEAPIFY，时间复杂度为O(lgn)，函数INCREASE_KEY()更新结点到根结点的路径长度为O(lgn)，时间复杂度为O(lgn)3.快速排序(1) 问题描述 实现快速排序(2) 问题分析快速排序采用了分治策略数组A[p..r]被划分成两个子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每个元素都小于等于A(q)，而且，小于等于A[q+1..r]中的元素然后通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]排序。
最后将两个数组合并3) 算法分析 快速排序不需要额外的辅助空间，其时间复杂度在平均情况下为O(nlgn)，最坏情况下为O()快速排序是不稳定的排序算法4) 实验结果4. 第k大元素(1) 问题描述 给定两个大小分别为m和n的有序序列，采用分治法求解两个序列合起来的第k大元素，使得时间复杂度为O(lgm+lgn)2) 问题分析将A平均分为前后两个部分，前半部分有x个元素，后半部分有m-x个元素因为A有序，所以后半部分的所有元素均大于前半部分A[x]为后半部分的第一个元素将B也平均分为前后两个部分，前半部分有y个元素，后半部分有n-y个元素B[y]是后半部分的第一个元素3) 算法分析由于两个数组都是平均划分的，我们可以近似地认为x=m/2, y=n/2假设A[x]<=B[y],则有a.B[y]前面至少有x+y个元素，如果k<=x+y，合并后第k大元素必然在B[y]前面，所以原来B数组中的后半部分可以排除掉b.合并后A[x]后面至少有(n+m)-(x+y)个元素，如果k>x+y，合并后第k大元素必然在A[x]后面所以，原来在A数组中前半部分可以排除掉实验二 动态规划1. 矩阵链乘(1) 题目要求给定n个矩阵链，矩阵Ai的规模为pi-1*pi（1≤i≤n），求完全括号化方案，使得A1A2,...An所需标量乘法次数最小。
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的最优括号化问题），求出子问题的解，然后将子问题的最优解组合起来，同时必须保证考察了所以的可能的分割点设m[i,j]表示计算AiAi+1...Aj所需标量乘法次数的最小值，则原问题的最优解就是m[1,n]AiAi+1...Aj的最小代价括号方案的递归求解公式为：本程序的主要函数是基于上述递归式的函数MatrixChainOrder(),它采用自底向上表格法,根据输入的矩阵规模数组，计算m[i,j]，同时构造一个辅助数组s[i,j]用来记录最优值m[i,j]对应的分割点k，最后可以根据s[i,j]的值构造最优解(调用函数PrintOptimal()),该算法的时间复杂度是O(n3)。
4) 实验结果实验结果如图所示：2. 最长公共子序列(1) 问题描述用动态规划方法求两个字符序列X和Y的最长公共子序列2) 问题分析LCS问题的最优子结构是：设X=和Y=为两个序列，Z=为X与Y的任一LCSa. 如果xm=yn,则zk=xm=yn且Zk-1是Xm-1与Yn-1的一个LCSb. 如果xm≠yn,则zk≠xm意味着Z是Xm-1与Y的一个LCSc. 如果xm≠yn,则zk≠yn意味着Z是X与Yn-1的一个LCS上述最优子结构意味着在求解X与Y的一个LCS时，需要求解一个或两个子问题，如果xm=yn,求解Xm-1与Yn-1的一个LCS；如果xm≠yn,需要求解Xm-1与Y的一个LCS和X与Yn-1的一个LCS用c[i,j]表示序列X[1...i]与Y[1...j]的最长公共子序列的长度，则c[m,n]为X与Y的最长公共子序列长度根据最优子结构的性质，c[i,j]的递归式为：(3) 算法分析本程序的主要函数是基于递归式的LCSLength()，它的作用是构造c[i,j]表，用来存储LCS的长度，同时构造一个辅助数组b[i,j]存储计算c[i,j]时指向所选择的子问题最优解，用来帮助构造最优解（调用函数printLCS()），该算法的时间复杂度为O(n3).(4) 实验结果实验结果如下图所示：所遇到的问题：定义函数printLCS()时出现错误 type of formal parameter 1 is incomplete,通过在参数列表中添加二维数组的大小来解决的。
3. 最长公共子串(1) 问题描述给定两个字符串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的一个子串用c[i,j]表示字符串X[1...i]与Y[1...j]的最长公共子串的长度，则c[m,n]为X与Y的最长公共子串长度根据最优子结构的性质，c[i,j]的递归式为：(3) 算法分析本程序的主要函数是基于递归式的LCSSubLength()，它的作用是构造c[i,j]表，用来存储子串的长度，同时构造一个辅助数组b[i,j]存储计算c[i,j]时指向所选择的子问题最优解，用来帮助构造最优解（调用函数printLCS()），该算法的时间复杂度为O(n3).(4) 实验结果4. 最大和(1) 问题描述给定n个整数（可能为负数）组成的序列A=，求该序列连续的子段和的最大值。
2) 问题分析 由上述问题可以将最大字段和定义为： 设b[j]=max(sum(i,j)),即以aj为结束元素的连续数组的最大和则X=max（b[j]），则原问题所求为b[n]，b[j]的递归式为：(3) 算法分析 基于上述递归式的函数DPMaxSum()是本程序的主要函数，它用来计算最大字段和，时间复杂度为O(n).(4) 实验结果5. 最短路径(1)题目要求根据输入的带权有向图G的n*n矩阵W，求图中源点到目的顶点的最短路径 (2)题目分析 这个问题需要用动态规划来解决，可以用Floyd-Warshall算法来实现3) 算法分析首先考虑其最优子结构特性总结如下： 设G的两个不同的顶点i,j∈V={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:i∈k∈j我们将前半段i∈k记为p1,后半段k∈j记为p2,则p1是从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来表示∞本程序的主要函数是floyd()，参数为表示图的矩阵w和图的顶点个数n,该函数主要用来计算任意两点间的最短路径长度，存入数组d中，并调用了函数printAll()，其作用是打印出任意节点到其它所有节点的最短路径及其长度4) 实验结果实验结果如下图所示：实验三 贪心策略1. 背包问题 1.1分数背包 (1)题目要求 给定n种物品和一个背包物品i的重量为wi其价值为vi，背包的容量为C,求如何装载背包，使得装入背包中的物品总价值最大选择装入的物品时，可以选择物品的一部分 (2)题目分析因为物品可以分割成块，单位块的价值越大，显然总价值越大,所以它的局部最优满足全局最优，可以用贪心法来解决。
(3)算法分析 把n种物品的取舍状态用一个向量表示{x1,x2,...,xn},其中xi∈[0,1].首先，应该计算每种物品的单位价值vi/wi，然后按照单位价值从大到小进行排序，根据贪心选择策略，将尽可能多的单位价值最高的物品装入背包，如果该物品全部装入背包而没有超重时，继续装入单位价值第二大的物品，以此类推，直到达到背包容量上界C该程序的主要函数是GreedyKnapsack(),其作用是构造x[i],最后根据x[i]的状态可以确定装入背包的方案.贪心算法的时间复杂为O(nlgn).1.2 0/1背包(1) 题目要求给定n种物品和一个背包物品i的重量为wi其价值为vi，背包的容量为C,求如何装载背包，使得装入背包中的物品总价值最大选择装入的物品时，不可以选择物品的一部分2) 题目分析 把n种物品的取舍状态用一个向量表示{x1,x2,...,xn},其中xi只有两种可能取值0或1当xi=1时，表示将第i个物品装入背包，当xi=0时，表示不将第i个物品装入背包，那么这个0-1背包问题就可以形式化地描述为： maxvixi结束条件为 wixi≤C，xi∈{0,1}，1≤i≤n也就是说0-1背包问题实际上就是求这样一个向量{x1,x2,...,xn},xi∈{0,1}，1≤i≤n，使得vixi最大，同时满足 wixi≤C。
3) 算法分析 对于0-1背包问题，贪心算法不能得到最优解，无法保证最后将背包装满贪心策略中，采用多步过程来完成背包的装入，在每一步中，都是利用固定的贪心准则（从剩下物品中选择价值最大的物品）来选择物品为了求解最优解，该问题可采用动态规划方法 用c[i,j]表示背包剩余容量为j，剩余物品为i，i+1，...，n时的最优解的值，我们的目标是求解c[n,C]c[i,j]的递归式是：其最优子结构为：一，如果当前最优解包含物品n，那么剩下的选择中方案是从1,2，..，n-1，容量为C-wn；二，如果当前最优解不包含物品n，那么剩下的选择中方案是从1,2，..，n-1，容量为C该程序的主要函数是基于递归式的Knapsack01()，它的作用是填写c[i,j]，遍历所有物品，直到得到c[n,C]即为所求，它的时间复杂度为O(nC).2. 任务调度(1) 题目要求给定n个任务及每个任务的运行时间t[i]，要求按顺序执行，求一种最佳的调度方案，使平均完成时间最小2) 题目分析该题可以采用短任务优先调度算法，使用贪心策略来实现(3) 算法分析贪心算法是通过一系列选择来求出问题的最优解，每个决策点做出当前情况下的最佳选择。
贪心选择性质是指所求问题的最优解可以通过一系列局部最优的选择来到贪心算法通常以自顶向下的方式进行该题中要得到所有任务的平均最小完成时间，只需要将各个任务按运行时间从小到大排序，任务完成时间为它等待的时间与自身完成时间之和主要的调度算法包含三部分：一，排序，按照运行时间从小到大的顺序将任务排序；二，计算总的平均完成时间；三，输出调度结果4) 实验结果实验结果如下图所示：3. 单源点最短路径(1)题目要求给定带权有向图G=的权重矩阵W求从源点s到其他结点的最短路径2)题目分析这是一个求单源点最短路径问题，因为给定的权重矩阵中存在负值，即存在负权值的边，所以可以用bellman—Ford算法求解3)算法分析 最短路径的最优子结构性质是最短路径的子路径也是最短路径，如下所述：给定带权有向图G=及其权重函数w：E→R设p={1,2,...,k}为从结点1到结点k的一条最短路径，并且对于任意的i和j，1≤i≤j≤k，设pij={i，i+1，...，j}为路径p中从结点i到j的子路径，那么pij是从结点i到j的最短路径Bellman-Ford算法解决的是一般情况下的单源点最短路径问题，克服了Dijkstra算法不能处理图中存在负权值的情况。
在这里，边的权值可以为负值，给定带权有向图G=及其权重矩阵Wbellman—Ford算法返回一个布尔值，表示是否存在一个从源点可以到达的权重为负值的环路，如果存在，算法将告知我不不存在解决方案，否则，算法将给出最短路径以及它们的权重Bellman—Ford算法通过对边进行松弛操作来渐近地降低从源点s到每个结点v的最短路径的估计值d，直到该估计值与实际的最短路径权重相同该算法返回true当且仅当输入图不包含从源点到达的权重为负值的环路Bellman—Ford算法大致可以分为三个部分：一，初始化所有的点，每一个点保存一个值，表示从源点到这个点的距离，将源点的值设为0，其他值设为无穷大；二，循环，遍历所有的边，进行松弛操作；三，遍历途中所有的边，判断途中是否存在回路Bellman—Ford算法的时间复杂度是O(VE)4. 任意两点间最短路径 (1)题目要求根据输入的带权有向图G的n*n矩阵W，求图中每一个顶点到其他所有顶点的最短路径 (2)题目分析 这个问题需要用动态规划来解决，Floyd-Warshall算法来实现3)算法分析首先考虑其最优子结构特性总结如下： 设G的两个不同的顶点i,j∈V={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:i∈k∈j我们将前半段i∈k记为p1,后半段k∈j记为p2,则p1是从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来表示∞本程序的主要函数是floyd()，参数为表示图的矩阵w和图的顶点个数n,该函数主要用来计算任意两点间的最短路径长度，存入数组d中，并调用了函数printAll()，其作用是打印出任意节点到其它所有节点的最短路径及其长度。
4)实验结果实验结果如下图所示：实验四 回溯法1. 0-1背包问题(1)题目要求 给定n种物品和一个背包物品i的质量为wi，其价值为vi，背包的容量为C,求如何装载背包，使得装入背包中的物品总价值最大2)题目分析 把n种物品的取舍状态用一个向量表示{x1,x2,...,xn},其中xi只有两种可能取值0或1当xi=1时，表示将第i个物品装入背包，当xi=0时，表示不将第i个物品装入背包，那么这个0-1背包问题就可以形式化地描述为： maxvixi结束条件为 wixi≤C，xi∈{0,1}，1≤i≤n也就是说0-1背包问题实际上就是求这样一个向量{x1,x2,...,xn},xi∈{0,1}，1≤i≤n，使得vixi最大，同时满足 wixi≤C要找到这样的向量，可以应用回溯法在由0-1构成的解空间树中进行查找在搜索解空间树的过程中，只要其孩子是可行节点，搜索就进入该孩子节点继续搜索，否则通过剪枝操作减掉不可行节点以下分支为了节省空间，可以分两次回溯搜索解空间树，第一次搜索计算出背包可以装载的最大价值量，第二次搜索计算出满足这个最大价值量的全部装包方案。
3) 算法分析该算法主要的函数时knap1()和knap2(),knap1()的作用是递归地回溯搜索解空间树，计算出背包装载物品的最大价值量，其中参数n的作用是作为数组x的下标，每递归调用knap1()一次，n的值都会加1传递，通过这种方法在数组x中记录搜索的路径flag为物品的数量，当n=flag时表示找到一条可能解的路径，即找到了一种可行的背包装载方案，但不一定是最佳的参数c是装载的上界，函数isOverLoad()的作用是判断当前x中记录的搜索路径对应的物品重量是否超过装载上界c，一旦物品的当前重量超过c，则本次返回递归调用，相当于搜索二叉树的剪枝操作，这样后续的分支就不再搜索了参数*price为一个指针型变量，其返回背包可装载物品的最大值当n=flag时，表明找到一种可行的背包方案，这时调用函数getValue()获得此背包装载方案对应的物品价值总量，如果该值大于*price，则将该价值总量赋值给*price,因此*price中始终存放最大的价值总量knap2()的作用是重新遍历搜索解空间，找到并输出与最大价值量price相等的装包方案它的操作与knap1()大致一样，只是在n=flag时判断先前计算好的最大价值量price是否等于getValue()获得的装包方案对应的物品价值总量，如果相等，则找到了一种装包方案，并输出该装包方案，否则继续回溯搜索。
因为0-1背包问题可能有多个解，所以要搜索整个解空间，找出物品价值总量等于price的装包方案4) 实验结果实验结果如图所示：2. 8-Queen问题(1) 题目要求用回溯法求解如何在一个8*8的棋盘上无冲突的摆放8个皇后棋子，即任何一个皇后所在位置的水平、竖直以及对角线上都不能出现其他的皇后2) 题目分析求解八皇后问题，可以构造一颗解空间树，通过深度优先搜索这颗解空间树，得到八皇后问题的一种或几种解3) 算法分析该算法用一个二维数组Q[8][8]存放棋盘格局，Q[i][j]=0表示不放置皇后，Q[i][j]=1表示放置皇后该算法的主要函数是Queen(),参数j(0≤j＜8)表示放置皇后所在棋盘位置的列数，最开始调用Queen()时，j初始化为0，由它派生出第一颗解空间树，当j=8时表明已经得到一个八皇后问题的解，该函数调用了子函数canSet()，它的作用是判断棋盘中的位置Q[i][j]是否可以放置一个皇后，设计思想是以Q[i][j]为中心，分别判断数组Q的行、列、左上方、左下方、右上方、右下方的状态，若存在1，则Q[i][j]不能放置皇后，返回0；否则可以放置皇后，返回1.(4) 实验结果实验结果如图所示：回溯法的基本思想是在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根节点出发深度搜索解空间树。
当搜索到某一节点是，要先判断该节点是否包含问题的解，如果包含，就从该节点出发继续搜索下去；否则，跳过对以该节点为根的子树的搜索，逐层向其祖先节点回溯，这个过程也叫解空间的剪枝操作要回溯到树根，这样根节点的所有子树都被搜索到才结束。