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

市委召开了全市乡科级主要领导干部集中学习班暨“大学习、大讨论、大调研”活动启动会，根据会议安排，在镇党委统一组织学习的基础上，坚持以问题为导向，紧扣“天府六问”“果城十二问”《算法分析与设计》2012-2013-2学期期中测试（信息安全专业DQ教学班）姓名：学号：得分：1.证明OfnOgnOfngn。（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))即OfnOgnOfngn成立。2.将下列5个函数按渐近增长率由低至高进行排序，要求写出比较过程。（15分）100log2logloglog1012345()(log),()log,()log,()2,()nnnnfnnnfnnfnnnfnfnn解：100log2logloglog24()log100log,()2log,nnnfnnnfnnn(1)2()fn是对数函数的幂，5()fn是幂函数，因此25()()fnOfn;(2)49101105loglimlimlimlognnnfnnnnnfnn，因此54()()fnOfn;(3)423log1limlimlim0lognnnfnnnfnnnn，因此43()()fnOfn;(4)对1()fn和3()fn取对数，有13log()logloglogloglog,log()2loglogloglogfnnnnnnnfnnnn，因为lognOn，所以31()()fnOfn;因此，5个函数按渐近增长率由低至高排序为25431(),(),(),(),()fnfnfnfnfn。3.给定按升序排列的n个不同整数存于数组a[1:n]中，请设计logOn的算法找到下标i，1in，使得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值，结束。市委召开了全市乡科级主要领导干部集中学习班暨“大学习、大讨论、大调研”活动启动会，根据会议安排，在镇党委统一组织学习的基础上，坚持以问题为导向，紧扣“天府六问”“果城十二问”publicstaticintSearch(int[]a,intn){//在a[0]=a[1]=...=a[n-1]中搜索a[i]=i//找到a[i]=i时返回i，否则返回0intleft=0;intright=n–1;while(left=right){intmid=⌊(left+right)/2⌋;if(a[mid]==mid)returnmid;if(a[mid]mid)right=mid–1;elseleft=mid+1;}return0;//未找到a[i]=i}市委召开了全市乡科级主要领导干部集中学习班暨“大学习、大讨论、大调研”活动启动会，根据会议安排，在镇党委统一组织学习的基础上，坚持以问题为导向，紧扣“天府六问”“果城十二问”4.利用主方法给出下列递归式的渐近界，并用数学归纳法证明式(2)的渐近界。（20分）(1)42TnTnn,(2)242TnTnn,(3)342TnTnn解：(1)24,2,loglog42,baba2,if0.5,fnnOn因此，2Tnn.(2)24,2,loglog42,baba22,fnnn因此，2logTnnn.(3)24,2,loglog42,baba32,if0.5,fnnn而且3334242234,fnnnncfn其中34n，因此，3Tnn.证明：假设当kn时，2logTkckk，其中c为常数。222222224242log2log1log1logif1TnTnncnnncnnncnncncnnc因此，命题得证。5.利用直接展开法求解下列递归式的渐近界。（20分）(1)242TnTnn,(2)TnnTnn解：(1)22222222232423322loglog2222424422422442224234242log1loglogkknnTnTnnTnnnTnnTnnnTnnTnknTnnnnTnnOnn(2)TnnTnn12121414181812121111112,2kkTnnTnnTnTnnnTnnTnnTnknTk其中122kn，则12log22logloglogknknkn市委召开了全市乡科级主要领导干部集中学习班暨“大学习、大讨论、大调研”活动启动会，根据会议安排，在镇党委统一组织学习的基础上，坚持以问题为导向，紧扣“天府六问”“果城十二问”所以，2loglog1loglog2TnTnnn，即loglogTnOnn.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种商品装入购物车的最优值。Case1:不选择第i种商品则m(i,j)为当重量限制为j时，{1,…,i–1}种商品装入购物车所产生的最大价值Case2:选择第i种商品.新的重量限制为j–wim(i,j–wi)为新重量限制下，{1,…,i–1}种商品装入购物车所产生的最大价值因此，递归式如下：0if0or0,1,ifmax1,,1,otherwiseiiiijmijmijwjmijvmijw最优解：选择商品1,1’,3,即选择两个商品1,一个商品3最优值=25+25+15=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}种商品装入购物车所产生的最大价值因此，递归式如下：0if0or01,ifmax1,,1,if2,1,,1,,maxif221,2iiiiiiiiiiijmijjwmijvmijwwjwmijmijvmijwjwvmijw最优解：选择两个商品1,一个商品3最优值=25+25+15=65市委召开了全市乡科级主要领导干部集中学习班暨“大学习、大讨论、大调研”活动启动会，根据会议安排，在镇党委统一组织学习的基础上，坚持以问题为导向，紧扣“天府六问”“果城十二问”第2章作业：算法分析基础1.算法与程序的区别(1).算法特性之一是有穷性，程序不一定满足有穷性。(2).计算机程序是用来给计算机读的，而算法是给人来读的，直接将算法输入计算机是不能运行的。(3).算法是解决问题的一种方法或一个过程，而程序则是算法用某种程序设计语言的具体实现。2.将下列函数按渐进增长率由低到高排列出来。24/3loglog2log1234562,,log,(log),2,,nnnnnfnfnnfnnfnnnfnfnn令logmn，则有12113344266log,2loglog,3logloglog,log,gnfnmgnfnmgnfnmmmmngnfnm显然上述4个函数的渐近增长率排序为3146gngngngn；22255266loglog,log2,loglog,ngnfnnngnfngnfnn显然上述3个函数的渐近增长率排序为625gngngn；因此，原函数的渐近增长率排序为314625fnfnfnfnfnfn。3.已知gnOfn，证明fngnOfn。证明：因为gnOfn，存在正常数c0和自然数n0，使得对所有nn0，有0gncfn成立。令c1=c0+1，则对所有的nn0，有f(n)+g(n)f(n)+c0f(n)(1+c0)f(n)=c1f(n)即fngnOfn成立。市委召开了全市乡科级主要领导干部集中学习班暨“大学习、大讨论、大调研”活动启动会，根据会议安排，在镇党委统一组织学习的基础上，坚持以问题为导向，紧扣“天府六问”“果城十二问”第3章作业：分治递归1.画出T(n)=2T(n/2)+1的递归树，并给出其解的渐进界。然后用数学归纳法证明给出的界。11T(1)1111111111111…………………………………………T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)122223logn+1nTotal:O(n)证明：假设当kn时，12Tkckc，其中c1和c2为常数。121212222122121if1TnTncnccnccncc因此，命题得证。2.直接展开法求解递归式T(n)=T(n/2)+123log21222322log=1loglogknTnTnTnTnTnkTnnTnOn