算法设计期中试卷、平时作业参考解答

《算法分析与设计》2012-2013-2学期期中测试（信息安全专业DQ教学班）

姓名：学号：得分：

1. 证明O?f?n???O?g?n???O?f?n??g?n??。（10分）

证明：对于任意f1(n) ?O(f(n))，存在正常数c1和自然数n1，使得对所有n?n1，有f1(n) ?c1f(n)成立。 类似，对于任意g1(n) ?O(g(n))，存在正常数c2和自然数n2，使得对所有n?n2，有g1(n) ?c2g(n)成立。 令c3=max{c1, c2}，n3 =max{n1, n2}，则对所有的n ?n3，有 f1(n) +g1(n) ?c1f(n) + c2g(n) ?c3f(n) + c3g(n) = c3(f(n) + g(n))

即O?f?n???O?g?n???O?f?n??g?n??成立。

2. 将下列5个函数按渐近增长率由低至高进行排序，要求写出比较过程。（15分）

f1(n)?n(logn)n,??f2(n)?logn100logn,??f3(n)?n2logn,??f4(n)?2logn?loglogn,??f5(n)?10n

解：f2(n)?logn100logn?100log2n,??f4(n)?2logn?loglogn?nlogn,?

(1) f2(n)是对数函数的幂，f5(n)是幂函数，因此f2(n)?O?f5(n)?; (2) limn??f4?n?f5?n?f4?n?f3?n??limnlogn?lim?n910logn???，因此f5(n)?O?f4(n)?; 110n??nn??nlogn1?lim?0，因此f4(n)?O?f3(n)?;

n??n2lognn??n(3) limn???lim(4) 对f1(n)和f3(n)取对数，有

logf1(n)?logn?nloglogn???nloglogn????n?,??logf3(n)?2logn?loglogn???logn?，

因为logn?O?n?，所以f3(n)?O?f1(n)?;

因此，5个函数按渐近增长率由低至高排序为f2(n),f5(n),f4(n),f3(n),f1(n)。

3. 给定按升序排列的n个不同整数存于数组a[1:n]中，请设计O?logn?的算法找到下标

i，1?i?n，使得a[i] = i，如不存在这样的下标，则返回0。（15分）

解：

令head = 1, rear = n.

(1) 当head <= rear时，令mid=?(head+rear)/2?； (2)如果a[mid] = mid，返回mid值，结束。

如果a[mid] > mid，令rear = mid – 1，返回(1)继续执行； 如果a[mid] < mid，令head = mid + 1，返回(1)继续执行； (3)返回0值，结束。

public static intSearch(int [] a, int n)

{

// 在 a[0] <= a[1] <= ... <= a[n-1] 中搜索 a[i] = i // 找到a[i] = i时返回i，否则返回0 int left = 0; int right = n – 1; while (left <= right) {

int mid = ?(left + right)/2?; if(a[mid] == mid) return mid; if (a[mid] > mid) right = mid – 1; else left = mid + 1; }

return 0; // 未找到a[i] = i }

4. 利用主方法给出下列递归式的渐近界，并用数学归纳法证明式(2)的渐近界。（20分）

(1) T?n??4T?n2??n, (2) T?n??4T?n2??n2, (3) T?n??4T?n2??n3

解：(1)a?4,b?2,logba?log24?2, f?n??n?O?n2???, if ??0.5, 因此，T?n????n2?.

证明：假设当k?n时，T?k??ck2logk，其中c为常数。

(2)a?4,b?2,logba?log24?2, f?n??n2???n2?,

因此，T?n????n2logn?.

(3)a?4,b?2,logba?log24?2, f?n??n3???n2???, if ??0.5,

3而且4f?n2??4?n2??n32?3n34?cf?n?,其中n?34，

因此，T?n????n3?.

T?n??4T?n2??n2 ?4c?n2?log?n2??n2 ?cn2?logn?1??n2 ?cn2logn??c?1?n2 ?cn2logn if c?1因此，命题得证。

25. 利用直接展开法求解下列递归式的渐近界。（20分）

(1) T?n??4T?n2??n2, (2) T?n??nT

解：(1)

?n??n

T?n??nT?n??nT?n??4T?n2??n2?44T?n22??n222?n2?42T?n22??2n2?424T?n23??n224?2n2?43T?n23??3n2???4kT?n2k??kn2???4logn??12T?n?T?n???112nn ?T?n14?nn14?1?1?1?1?1

?? ?T?n18?18

?? ?Tn12n12k?k??kT?n2logn??n2 ??logn?n2T?1??n2logn?O?n2logn?

(2) T?n??nTT?2? ??k?, 2其中2?n12，则

12k??logn2???2k??logn ????k??loglognk?T?n?T?2???loglogn???1??loglogn，所以， n2?n??n

即T?n??O?nloglogn?.

6. 某超市中有n种商品搞活动，每种商品i的重量是wi，其价格为vi，现在给你发一个容量为C的购物车，你可以在这n种商品中选一些放入你的购物车中免费带走。但是要求所选的商品重量之和不能大于购物车容量C，而且超市中每种商品每人最多选两件。请问在这种情况下你如何选择商品使得你能带走的免费商品的价格达到最大？（20分）

(a)为该问题设计一个动态规划算法，要求写出分析过程和递归式。

(b)若该超市共有3种商品搞活动，商品的价值依次为v=(25,30,15)，商品的重量依次为w=(2,3,1)，购物车容量为C=5。运用自底而上的方法求解上述问题，要求画出表格，并给出最优解与最优值！

解：

方法1

? 将n种商品全部复制一份得到2n种商品，这样每种商品最多只能选择1件。 ? 定义m(i, j)为购物车容量为j，由第1, …, i种商品装入购物车的最优值。 ? Case 1:不选择第i种商品

? 则m(i,j)为当重量限制为j时，{1, …,i–1}种商品装入购物车所产生的最大价值

? Case 2:选择第i种商品.

? 新的重量限制为j – wi

? m(i, j – wi) 为新重量限制下，{1, …, i–1}种商品装入购物车所产生的最大价值

因此，递归式如下：

?0if i?0 or j?0??m?i,j???m?i?1,j?if wi?j???max?m?i?1,j?,vi?m?i?1,j?wi??otherwise

最优解：选择商品1,1’,3, 即选择两个商品1, 一个商品3 最优值 = 25+25+15=65

方法2

? 定义m(i, j)为购物车容量为j，由第1, …, i种商品装入购物车的最优值。

? Case 1:不选择第i种商品

? 则m(i,j)为当重量限制为j时，{1, …,i–1}种商品装入购物车所产生的最大价值

? Case 2:仅选择1格第i种商品.

? 新的重量限制为j – wi

? m(i, j – wi) 为新重量限制下，{1, …, i–1}种商品装入购物车所产生的最大价值

? Case 3:选择两个第i种商品

? 新的重量限制为j – 2wi

? m(i, j – 2wi) 为新重量限制下，{1, …,i – 1}种商品装入购物车所产生的最大价值

因此，递归式如下：

?0?mi?1,j????m?i,j???max?m?i?1,j?,vi?m?i?1,j?wi??????max?m?i?1,j?,vi?m?i?1,j?wi?,????2v?mi?1,j?2w???i??i??

if i?0 or j?0if j?wiif wi

最优解：选择两个商品1, 一个商品3 最优值 = 25+25+15=65

第5章作业：贪心算法

1、请叙述分治递归、动态规划、备忘录方法和贪心算法各自的特点和基本要素，并比较它们之间的相同之处及其差异。

分治递归法所能解决的问题一般具有以下几个特征: (1) 该问题规模缩小到一定的程度就可以容易地解决；

(2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有递归子结构性质 (3) 利用该问题分解出的子问题的解可以合并为该问题的解；

(4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

动态规划与分治的比较 (1) 共同点：递归子结构

将待求解问题分解成若干个规模较小的相同类型的子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 (2) 不同点：重叠子问题

适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。 (3) 不同点：求解问题的顺序

分治递归、备忘录方法：自顶向下，动态规划：自底向上，

贪心算法的基本要素 (1) 贪心选择性质 (2) 最优子结构性质

贪心算法的特点

(1) 总是作出局部最优选择 (2) 不能保证得到全局最优解

贪心法与动态规划的比较

相同点：递推算法、最优子结构、局部最优解→全局最优解 不同点：

动态规划：自底向上，贪心算法：自顶向下

贪心算法：当前局部最优解←上一步局部最优解，动态规划：当前局部最优解←之前所有局部最优解

2、给定一个包含{b,e,f,n,o,t,y}字符集的文本文件，每个字符在文件中出现频率如下表所示，文件共有140个字符，试用huffman编码对该文本文件进行编码，要求画出编码的huffman树，给出每个字符的huffman编码，并求解编码后文件的长度。

字符 次数

b 12 e 43 f 33 n 15 o 7 t 6 y 24 0000613255814018211123300153911244317t:0000o:0001b:001f:01

n:100y:101e:11

编码后文件长度 = (6 + 7) × 4 + (12 + 15 + 24) × 3 + (33 + 43) × 2 = 357 bit

3、用Dijkstra算法求下图中顶点1到其他所有顶点的最短路径，要求给出计算过程和最优解、最优值。

解1：

迭代 初始 1 2 3 4 5 S {1} {1,3} {1,3,2} {1,3,2,4} {1,3,2,4,5} {1,3,2,4,5,6} {1,3,2,4,5,6,7} u 2 - 7 7 7 7 7 7 7 The distance from node 1 to node # 3 4 4 4 4 4 4 4 4 10 10 10 10 10 10 10 5 6 7 ? 10 10 10 10 10 10 ? ? ? 15 13 13 13 ? ? ? ? ? 15 15 解2：

迭代 初始 1 2 3 4 5

最短路径： 1→2：1,2 1→3：1,3 1→4：1,4 1→5：1,3,5 1→6：1,3,5,6 1→7：1,3,5,6,7

4、分别叙述用Prim算法和Kruskal算法求最小生成树的过程，并分别用上述两种算法求下图的最小生成树，要求给出最小生成树中边的生成顺序，画出最小生成树，并最小权重之和。（其中Prim算法从节点1开始执行）

Prim‘s 算法. 首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i?S，j?V-S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止

Kruskal‘s算法. 首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。

S {1} {1,3} {1,3,2} {1,3,2,5} {1,3,2,5,4} {1,3,2,4,5,6} {1,3,2,4,5,6,7} u - The distance from node 1 to node # 2 7 7 7 7 7 7 7 3 4 4 4 4 4 4 4 4 10 10 10 10 10 10 10 5 6 7 ? 10 10 10 10 10 10 ? ? ? 13 13 13 13 ? ? ? ? ? 15 15

Prim‘s 算法.(1,3), (3,5), (5,6), (6,7), (6,4), (4,2) Kruskal‘s算法. (6,7), (5,6), (1,3), (6,4), (4,2), (3,5)

权重之和为15。

本文来源：https://www.bwwdw.com/article/p30d.html