算法设计与分析.doc

一 填空题1. 一个计算机算法的指令序列需要满足性质的是输入、输出、确定性、有限性。输入、输出、确定性、有限性2.的渐近表达式是 O(n2)3 . 下面程序段的时间复杂度是 O(n2)for (i=0; in; i+) for (j=0; jn; j+)4求两个n阶矩形的乘法C=A*B,其算法如下： #define MAX 100 voidmaxtrixmult( int n, float aMAXMAX, float cMAXMAX) int i, j, k; float x; for( i=1; i=n; i+)8 for( j=1; j=n; j+) x=0; for( k=1; k=No，有 f(n)an/2 D x=an/26当问题的规模n趋向无穷大时， B 的数量级(阶)称为算法的渐进时间复杂度。A空间复杂度 B时间复杂度 C 冗余度 D 迭代次数7实现快速排序算法如下：private static void quickSort(int p ,int r) if（p an/2，则只要在数组a的右半部继续搜索x。3、用PRIM算法求下列带权图的最小生成树，要求画出选边的具体过程。 答：最终结果为(g)或(h)都是正确的。4、用Kruskal算法求所给的下列图像的最小生成树，并画出选边的过程。答：五、问答题1、有n种不同的货物，规定每种最多只能拿一件，车容量为c，第i件货物占空间为wi(0=i=n)，价值为pi(0=i=n)，目标为装载的物品价值最大。请用下述不同的贪婪装载策略求解。1有n种不同的货物，规定每种最多只能拿一件，车容量为c，第i件货物占空间为wi(0=i=n)，价值为pi(0=i=n)，目标为装载的物品价值最大。请用下述不同的贪婪装载策略求解。1）贪婪策略1：从剩余的物品中选择价值最大的物品。设n=3, w=55,30,40, p=30,20,15, c=80；2） 贪婪策略2：从剩余的物品中选择占空间最小的物品。设n=3, w=10,20，15, p=5,25，10, c=25；3）贪婪策略3：从剩余的物品中选择价值密度最大（ pi /wi ）的物品。设n=3, w=25,15,15, p=40,25,25, c=35； 4）分析不同策略的解，它们是最优解吗？如果不是，请直接写出最优解。5）用C语言或伪代码分别描述上述三个算法。答：首先确定问题的实质，是01背包问题而不是最优装载问题。最优装载问题的前提是重量受限制，而体积不受限制。伪代码：void GreedyMethod 将问题的输入按贪心规则排序; For 每个输入Ri If Ri满足约束条件 then 加入解； Else 抛弃； End for上述三种策略，分别给出了三种对输入的排序规则：按价值最大、按占用空间最小、按价值密度最大。对于利用贪心策略解决01被包问题，很显然，只能得到局部最优解，而不能得到全局最优解。如果将问题进行以下变通，即从01背包问题变为背包问题，这样，就可以在装包的过程中，将物品i的一部分装入包中。书中第P90页给出了证明，即选择价值密度最大的贪心策略产生的解是全局最优解。因此，按此种方法产生的最优解也是01背包问题解的上界。2有n=32个硬币，其中1个是假币，且假币较重。用分而治之方法设计一个找出假币的算法。1） 请写出求解的步骤；2） 用C程序或伪代码描述算法。答：将硬币递归的分成两份，比较这两份的重量，重量重者含有假币，因此，该问题可以转化为二分搜索问题。利用分治法解决该问题的伪代码如下：/-divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for (i=1,in) output(x); else for (int i=f(n,t);i=g(n,t);i+) xt=h(i); if (d=9 or 遇到叶子节点) backtrack(t+1); 按照深度优先的策略对子集树进行遍历，在遍历过程中，如果d已经等于9，则马上回溯，返回到父节点，继续按照深度优先的策略进行遍历。（图中节点没有用字母标识，故没有写出遍历节点路径。）通过遍历得到在子集树中，有两个分枝满足条件d=9，分别是3,4,2和-,4,-,5。从子集树可以看出，它和01背包问题的解集树相同，是一棵完全二叉树，左子树为1，右子树为0。该问题可以转化为类01背包问题，即3,4,2,5四个数中选出几个数，使得和为9。2）分枝限界解法由于该问题不是求取最优解，而是搜索满足约束条件的解，因此，利用分枝限界和利用回溯法只在搜索的策略上有所区别，并没有提高搜索效率。利用分枝限界法，需要额外提供活节点表来保存待扩展的节点。该题S中的元素太多，假如S=1,2,3要求满足d=3，问题性质没变，子集树简单了一些，但同样能说明问题。伪代码：/-procedure DDif 根节点T是答案节点 then 输出T； return endifelse 初始化活节点表L，置为空 loop for E的每个子节点X DO if X是答案节点 then 输出从X到T的路径 rethrn endif call ADD(X) /新的活节点X加入L parent(X)=E /指示到根的路径 repeat if 不再有活节点 then print(no answer node); break endif repeatend LC/-ABCDEFGHIJKLMNO1232333-L=AL=B,CL=C,D,EL=D,E,F,G利用分枝限界解策略，剪枝条件d=3对活节点表起作用，在对活节点进行扩展之前，先检验其是否满足约束条件，如果满足，则对其扩展，否则杀死该节点。活节点表L按照FIFO原则进行扩展。上图被矩形框覆盖的区域是被剪枝的分枝。如L=D,E,F,G，对D进行扩展，检验d，发现其已经等于3，故杀死D，L变为E,F,G。5旅行商问题：给出一个n个顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。任何一个包含所有n个顶点的环路被称作一个旅行。在旅行商问题中，要设法找到一条最小耗费的旅行。1）对图示的例，画出旅行商问题的解空间树；2）对该树运用回溯算法，写出依回溯算法遍历节点的顺序表及节点。确定回溯算法未遍历的节点。对应的解集树如下图所示：6 子集和问题：对于集合S=1，2，5，6，8，求子集，要求该子集的元素之和d=9。a) 画出子集和问题的解空间树；b) 对该树运用回溯算法，写出依回溯算法遍历节点的顺序表及节点。确定回溯算法未遍历的节点；c) 如果S中有n个元素，指定d，用伪代码写出求解子集和问题的回溯算法。见第4题。7旅行商问题：给出一个n个顶点的网络，要求找出一个包含所有n个顶点的具有最小耗费的环路。1） 对图示的例，画出旅行商问题的解空间树；2) 对该树用FIFO分枝定界法求解，并写出依该算法遍历节点的顺序表；3) 用C语言或伪代码描述旅行商问题的FIFO分枝定界算法。8设要计算矩阵连乘积，其中各矩阵的维数分别为： 30X35 35X15 15X5 5X10 10X20 20X25利用动态规划算法计算矩阵连乘过程中，得出的计算次序如下图所示：试根据递归式 ：见教材p44。9用动态规划解下列0-1背包问题例题：n=3, w=100,14,10, p=20,18,15, c= 116。假设表示的是背包容量为，可选择物品为时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算的递归式如下： 答：1 由题意： 2利用递归式，可得： 因此最优解m(1,116 )=maxm(2,116)， m(2,116-w1)+p1=maxm(2,116), m(2,16)+20 =max33,38=38n现在计算x1值，步骤如下：若m(1,c) =m(2,c)，则