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

《算法设计期中试卷、平时作业参考解答》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法分析与设计》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)=

2、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[m

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

4、mid]==mid)returnmid;if(a[mid]>mid)right=mid–1;elseleft=mid+1;}return0;//未找到a[i]=i}4.利用主方法给出下列递归式的渐近界，并用数学归纳法证明式(2)的渐近界。（20分）(1),(2),(3)解：(1)因此，.(2)因此，.(3)而且其中，因此，.证明：假设当时，，其中c为常数。因此，命题得证。5.利用直接展开法求解下列递归式的渐近界。（20分）(1),(2)解：(1)(2)其中，则所以，，即.6.某超市中有n种商品搞活动，每种商品i的重

5、量是wi，其价格为vi，现在给你发一个容量为C的购物车，你可以在这n种商品中选一些放入你的购物车中免费带走。但是要求所选的商品重量之和不能大于购物车容量C，而且超市中每种商品每人最多选两件。请问在这种情况下你如何选择商品使得你能带走的免费商品的价格达到最大？（20分）(a)为该问题设计一个动态规划算法，要求写出分析过程和递归式。(b)若该超市共有3种商品搞活动，商品的价值依次为v=(25,30,15)，商品的重量依次为w=(2,3,1)，购物车容量为C=5。运用自底而上的方法求解上述问题，要求画出表格，并给出最优解

6、与最优值！解：方法1²将n种商品全部复制一份得到2n种商品，这样每种商品最多只能选择1件。²定义m(i,j)为购物车容量为j，由第1,…,i种商品装入购物车的最优值。²Case1:不选择第i种商品Ø则m(i,j)为当重量限制为j时，{1,…,i–1}种商品装入购物车所产生的最大价值²Case2:选择第i种商品.Ø新的重量限制为j–wiØm(i,j–wi)为新重量限制下，{1,…,i–1}种商品装入购物车所产生的最大价值因此，递归式如下：最优解：选择商品1,1’,3,即选择两个商品1,一个商品3最优值=25+25+1

7、5=65方法2²定义m(i,j)为购物车容量为j，由第1,…,i种商品装入购物车的最优值。²Case1:不选择第i种商品Ø则m(i,j)为当重量限制为j时，{1,…,i–1}种商品装入购物车所产生的最大价值²Case2:仅选择1格第i种商品.Ø新的重量限制为j–wiØm(i,j–wi)为新重量限制下，{1,…,i–1}种商品装入购物车所产生的最大价值²Case3:选择两个第i种商品Ø新的重量限制为j–2wiØm(i,j–2wi)为新重量限制下，{1,…,i–1}种商品装入购物车所产生的最大价值因此，递归式如下：最优

8、解：选择两个商品1,一个商品3最优值=25+25+15=65第2章作业：算法分析基础1.算法与程序的区别(1).算法特性之一是有穷性，程序不一定满足有穷性。(2).计算机程序是用来给计算机读的，而算法是给人来读的，直接将算法输入计算机是不能运行的。(3).算法是解决问题的一种方法或一个过程，而程序则是算法用某种程序设计语言的具体实现。2.将下列函数按渐进增长