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

由天下分享时间：2025/3/21 18:39:20 加入收藏我要投稿点赞

百度文库 - 让每个人平等地提升自我

《算法分析与设计》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 int Search(int [] a, int n) {

. <= a[n-1] 中搜索 a[i] = i

利用主方法给出下列递归式的渐近界，并用数学归纳法证明式(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,

证明：假设当k?n时，T?k??ck2logk，其中cf?n??n?On2??, if ??0.5,

因此，T?n???n2. 为常数。

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

因此，T?n???n2logn.

T?n??4T?n2??n2 ?4c?n2?log?n2??n2 ?cn2?logn?1??n2 ?cn2logn??c?1?n2 ?cn2logn if c?12?????

(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.

?因此，命题得证。

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

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

解：(1)

?n??n

T?n??4T?n2??n2?44T?n22??n222?n2?42T?n22??2n2?424T?n23??n224?2n2?43T?n23??3n2??4kT?n2k??kn2??4lognT?n2logn??n2logn?n2T?1??n2logn?O?n2logn?

????14

百度文库 - 让每个人平等地提升自我 (2) T?n??nT其中2?n12k?，则 12k??logn2???2k??logn ????k??loglognT?n?T?2???loglogn???1??loglogn，所以， n2T?n???n??n nT?n??n12T?n?T?n?nn12 ? ? ? ? ? ?n14??1?1?1?1?1?1 即T?n??O?nloglogn?. T?n14?T?n18?n18Tn12n12k?k??kT?2??k?, 26. 某超市中有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