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

《算法分析与设计》2012-2013-2学期期中测试（信息安全专业DQ教学班） 姓名： 学号： 得分： 1. 证明。（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)) 即成立。 2. 将下列5个函数按渐近增长率由低至高进行排序，要求写出比较过程。（15分） 解： (1) 是对数函数的幂，是幂函数，因此; (2) ，因此; (3) ，因此; (4) 对和取对数，有 ， 因为，所以; 因此，5个函数按渐近增长率由低至高排序为。 3. 给定按升序排列的n个不同整数存于数组a[1:n]中，请设计的算法找到下标i，，使得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[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) , (2) , (3) 解：(1) 因此，. (2) 因此，. (3) 而且其中， 因此，. 证明：假设当时，，其中c为常数。 因此，命题得证。  5. 利用直接展开法求解下列递归式的渐近界。（20分） (1) , (2)  解：(1) (2) 其中，则 所以，， 即. 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}种商品装入购物车所产生的最大价值 因此，递归式如下： 最优解：选择商品1,1’,3, 即选择两个商品1, 一个商品3 最优值 = 25+25+15=65  方法2 定义m(i, j)为购物车容量为j，由第1, …, i种商品装入购物车的最优值。 Case 1: 不选择第i种商品