算法设计与分析

1、一填空题1. 一个计算机算法的指令序列需要满足性质的是输入、输出、确定 性、有限性。输入、输出、确定性、有限性2. 9n2 10n的渐近表达式是0( f)3 .下面程序段的时间复杂度是0( n)for (i=0; in; i+)for (j=0; j n; j+)4 求两个n阶矩形的乘法 C=A*B,其算法如下：#define MAX 100voidmaxtrixmult( 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;

2、k=No ，有 f(n) an/2D x = an/26 .当问题的规模n趋向无穷大时，B 的数量级(阶)称为算法的渐 进时间复杂度。A空间复杂度B时间复杂度C冗余度D迭代次数7 .实现快速排序算法如下：private static void quickSort( int p ,int r )i f ( p an/2，则只要在数组a的右半部继续搜索 x。3、用 PRIM 算法求下列带权图的最小生成树，要求画出选边的具体 过程。答：最终结果为 (g) 或 (h) 都是正确的。4、用 Kruskal 算法 求所给的下列图像的最小 生成树， 并画出选边的过程。答：五、问答题1、有 n 种不同的货物，

3、规定每种最多只能拿一件，车容量为 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,

4、 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语言或伪代码分别描述上述三个算法。答：首先确定问题的实质，是 0 1 背包问题而不是最优装载问题。最优装载问题的前提 是重量受限制，而体积不受限制。伪代码：void GreedyMethod将问题的输入按贪心规则排序 ;For 每个输入 RiIf Ri 满足约束条件 then 加入解；Else 抛弃；End for上述三种策略， 分别

5、给出了三种对输入的排序规则：按价值最大、 按占用空间最小、按价 值密度最大。对于利用贪心策略解决 01 被包问题，很显然，只能得到局部最优解，而不 能得到全局最优解。如果将问题进行以下变通，即从01 背包问题变为背包问题，这样，就可以在装包的过程中， 将物品 i 的一部分装入包中。 书中第 P90 页给出了证明， 即选择价 值密度最大的贪心策略产生的解是全局最优解。因此，按此种方法产生的最优解也是0 1背包问题解的上界。2.有n=32个硬币，其中1个是假币，且假币较重。用分而治之方法设计一个找出假币的算法1）请写出求解的步骤；2）用C程序或伪代码描述算法。答：将硬币递归的分成两份，比较这两份的

6、重量，重量重者含有假币，因此，该问题可以转化为二分搜索问题。利用分治法解决该问题的伪代码如下：/ divide-a nd-c onq uer(P)if ( | P | = nO) adhoc(P); /解决小规模的问题divide P into smaller sub in sta nces P1,P2,.,Pk； / 分解问题for (i=1,in) output(x);elsefor (int i=f(n,t);i=g(n,t);i+) xt=h(i);if (d=9 or遇到叶子节点 ) backtrack(t+1);按照深度优先的策略对子集树进行遍历，在遍历过程中，如果 d 已经等于

7、9，则马上回 溯，返回到父节点，继续按照深度优先的策略进行遍历。 (图中节点没有用字母标识，故没 有写出遍历节点路径。)通过遍历得到在子集树中，有两个分枝满足条件d=9,分别是3,4,2和-,4,-,5。从子集树可以看出，它和 01 背包问题的解集树相同，是一棵完全二叉树，左子树为1，右子树为 0。该问题可以转化为类 01 背包问题，即 3,4,2,5 四个数中选出几个数，使得 和为 9。2)分枝限界解法子集树简单了一些,由于该问题不是求取最优解，而是搜索满足约束条件的解，因此，利用分枝限界和利用回溯法只在搜索的策略上有所区别，并没有提高搜索效率。利用分枝限界法，需要额外提供活节点表来保存待扩

8、展的节点。 该题S中的元素太多，假如 S=1,2,3要求满足d=3，问题性质没变， 但同样能说明问题。伪代码：/procedure DD if 根节点T是答案节点then 输出T； return endif else初始化活节点表 L，置为空loopfor E的每个子节点if X 是答案节点call ADD(X) / pare nt(X)=E / repeat if 不再有活节点X DOthen 输出从 X到T的路径rethrn endif新的活节点X加入L指示到根的路径the nprin t( no an swer no de); break en dif repeat end LC在对活节

9、点进行扩展之前，先利用分枝限界解策略，剪枝条件d=3对活节点表起作用，检验其是否满足约束条件，如果满足，则对其扩展，否则杀死该节点。活节点表L按照FIFO原则进行扩展。上图被矩形框覆盖的区域是被剪枝的分枝。如L=D,E,F,G，对D进行扩展，检验d,发现其已经等于 3，故杀死D, L变为E,F,G。5. 旅行商问题：给出一个n个顶点网络(有向或无向)，要求找出一个包含所有n个顶点的具有最小耗费的环路。任何一个包含所有n 个顶点的环路被称作一个旅行。 在旅行商问题中， 要设法找到一条最 小耗费的旅行。1）对图示的例，画出旅行商问题的解空间树；2）对该树运用回溯算法， 写出依回溯算法遍历节点的顺序

10、表及节 点。确定回溯算法未遍历的节点。对应的解集树如下图所示：6子集和问题：对于集合 S=1，2，5，6，8 ，求子集，要求该子集的元素之和 d=9。a）画出子集和问题的解空间树；b）对该树运用回溯算法， 写出依回溯算法遍历节点的顺序表及节 点。确定回溯算法未遍历的节点；c）如果S中有n个元素，指定d,用伪代码写出求解子集和问题 的回溯算法。见第 4 题。7旅行商问题：给出一个 n 个顶点的网络,要求找出一个包含所有 n 个顶点的具有最小耗费的环路。1）对图示的例,画出旅行商问题的解空间树；2）对该树用FIFO分枝定界法求解，并写出依该算法遍历节点的 顺序表；3）用C语言或伪代码描述旅行商问题

11、的 FIFO分枝定界算法。 8设要计算矩阵连乘积,其中各矩阵的维数分别为：30X3535X1515X55X1010X2020X25利用动态规划算法计算矩阵连乘过程中,得出的计算次序如下图所示：试根据递归式 见教材p44。9 .用动态规划解下列0-1背包问题例题：n=3, w=100,14,10.p二20,18,15, c= 116。假设m(i,j)表示的是背包容量为j，可选择物品为i,i 1 ,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i, j)的递归式如下:答：1. 由题意：2. 利用递归式，可得：m(3, j)卩,0兰j 10因此最优解 m(1,116 )=maxm(2,116)b,0 勻 10m(2, j)二15,10 兰 j 1418,14 乞 j 2433, j _ 24m(2,116-w1)+p 1=maxm(2,116), m(2,16)+20 =max33,38=38现在计算X1值，步骤如下：若 m(1,c) =m(2, c)，则X1=