算法习题

教材:[1][王]王晓东,计算机算法设计与分析(第4版),电子工业.[2][S]唐常杰等译,Sipser著,计算理论导引,机械工业.参考资料:[3][C]潘金贵等译,Cormen等著,算法导论,机械工业.[4][M]黄林鹏等译,Manber著,算法引论-一种创造性方法,电子.[5][刘]刘汝佳等,算法艺术与信息学竞赛,清华大学.[6][L]Lewis等著,计算理论基础,清华大学.计算理论与算法分析设计第一章算法分析题1-1,1-2,1-4第1章概论1-1求下列函数的渐近表达式:3n2+10n;n2/10+2n;21+1/n;logn3;10log3n.解:3n2+10n=(n2);n2/10+2n=(2n);21+1/n=(1);logn3=(logn);10log3n=(n);1-2试论O(1)与O(2)的区别.答:没有区别,因为根据定义1=O(2),2=O(1)第1章概论1-4(1)假设某算法在输入规模为n时的计算时间为T(n)=32n.在某台计算机上实现并完成该算法的时间为t秒.现有另一台计算机,其运行速度是第一台的64倍,那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题?(2)若上述算法的计算时间改进为T(n)=n2,其余条件不变,则在新机器上用t秒时间能解输入规模为多大的问题?(3)若上述算法的计算时间改进为T(n)=8,其余条件不变,那么在新机器上用t秒时间能解输入规模为多大的问题?解:设机器1上t秒能解的问题规模为n1,机器2上t秒能解的问题规模为n2.(1)由t=32n1=32n2/64知,n2=n1+6,所以规模增大6.(2)由t=n12=n22/64知,n2=8n1,所以规模增大7倍.(3)若t8则n1可以任意大,若t1/8则n2可以任意大.第2章分治2-8设n个不同的整数排好序后存于T[1:n]中.若存在一个下标i，1in,使得T[i]=i.设计一个有效算法找到这个下标.要求算法在最坏情况下的计算时间O(logn).解:不同整数意味着要么严格递增,要么严格递减若T[1:n]严格递减,则T[i]i蕴含ji(T[j]j),T[i]i蕴含ji(T[j]j)满足二分法条件,可用二分搜索若T[1:n]严格递增,T[i]i蕴含ji(T[j]j),T[i]i0蕴含ji(T[j]j)也满足二分法条件,可用二分搜索满足二分法条件也意味着至多有一个解.算法略第2章分治2.9设T[0:n-1]是n个元素的数组.对任一元素x,设S(x)={i|T[i]=x}.当|S(x)|n/2时,称x为主元素.设计一个线性时间算法,确定T[0:n-1]是否有一个主元素.算法1:性质:若数列有主元素,则中位数必为主元素.先找中位数a,即第(n+1)/2大的数,在计数a出现次数.若a出现次数大于n/2,则a即为主元素;否则无主元素.找中位数时间O(n),计数a出现次数时间O(n).算法2:性质:若数列有主元素,则去掉两个不同数,主元素不变.1.p=T[0],ct=1,i=1,//p记可能主元素,ct为计数器,2.当in,若T[i]=p,则(ct++,i++);否则(ct--,i++;若ct==0,p=T[i],i++)3.判断p是否为主元素.注1:map对应平衡二叉树每次插入删除搜索时间是O(logn)注2:有人用计数的方法,当知道数组T的取值范围时是可行的.第3章动态规划1.考虑下面的整数线性规划问题.即给定序列a1,a2,…,an,求maxc1x1+c2x2+…+cnxn,满足a1x1+a2x2+…+anxnb,xi为非负整数解:动态规划,子结构[1:i],OSP设f[i][k]为用X[1:i]组合出重量k的最大价值则f[i][k]=max{f[i-1][k],f[i][k-x[i]]+c[i]}第3章动态规划1.考虑下面的整数线性规划问题.即给定序列a1,a2,…,an,求maxc1x1+c2x2+…+cnxn,满足a1x1+a2x2+…+anxnb,xi为非负整数1.初始f[1:n]=0,f[0]=02.对i=1:k,对s=1:n,3.若sX[i]且c[i]+f[s-X[i]]f[s],则f[s]+=f[s-X[i]]+c[i]4.输出f[n]第3章动态规划2.石子合并问题问题描述:在一个圆形操场的四周摆放着n堆石子.现在要将石子有次序地合并成一堆.规定每次只能选相邻的2堆石子合并成一堆,并将新的一堆石子数记为该次合并的得分.试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分.算法设计:对于给定n堆石子,计算合并成一堆的最小得分和最大得分.数据输入:由文件input.txt提供输入数据.文件的第1行是正整数n,1n100,表示有n堆石子.第2行有n个数,分别表示n堆石子的个数.结果输出:将计算结果输出到文件output.txt,文件第1行是最小得分,第2行是最大得分.输入文件示例input.txt44459输出文件示例output.txt4354第3章动态规划先讨论直线上石子合并问题的算法•动规,子结构[i:j],OSP,类似于矩阵连乘问题•定义m[i,j]为从第i堆到第j堆的石子合并能得到的最少分数,那么m[i,j]=min{m[i,k]+m[k+1,j]+sum[i:j]|ikj}其中sum[i:j]是第i堆到第j堆石子总数•修改矩阵连乘公式可以得到下面的算法(其中s[i,j]是最佳分断点)1.对i=1到n,m[i,i]=0,2.对r=1到n-13.对i=1到n-r4.j=i+r;s[i,j]=i;5.m[i,j]=m[i,i]+m[i+1,j]+sum[i:j];6.对k=i+1到j-17.t=m[i,k]+m[k+1,j]+sum[i:j],8.若m[i,j]t,则m[i,j]=t;s[i,j]=k;输出m[1,n],合并次序Traceback(i,j,s)1.若i==j,打印a[i]2.否则打印“(”3.Traceback(i,s[i,j],s)4.打印“+”4.Traceback(s[i,j]+1,j,s)5.打印“)”第3章动态规划再讨论圆周上的石子合并问题,子结构[i:j]稍作修改•定义m[i][len]为合并第i堆到第i+len-1堆石子能得到的最少分数•当i+len-1n时,指跨过第n堆到第(i+len-1)%n堆,仅sum函数需要修改•m[i][len]=min{m[i][k]+m[i+k][len-k]+sum[i:i+len-1]|0klen}•s[i][len]记从i到i+len-1最佳分断点1.对i=1到n,m[i][1]=0,s[i][1]=i2.对len=2到n3.对i=1到n4.s[i][len]=i;j=i+len-1;5.m[i][len]=m[i][1]+m[i+1][len-1]+sum[i:j];6.对k=2到len-17.t=m[i][k]+m[i+k][len-k]+sum[i:j],8.若m[i][len]t,则m[i][len]=t;s[i][len]=k;输出min{m[i][n]|1in}类似可以•打印合并次序•由加速原理加速第3章动态规划3.数字三角形问题问题描述:给定一个有n行数字组成的数字三角形,如下图所示.试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字和最大.算法设计:对于给定的n行数字组成的三角形,计算从三角形顶至底的路径经过的数字和的最大值.数据输入:由文件input.txt提供输入数据.文件的第1行数字三角形的行数n,1n100.接下来n行是数字三角形各行中的数字.所有数字在0~99之间.结果输出:将计算结果输出到文件output.txt,文件第1行中的数是计算出的最大值.输入文件示例input.txt5738810274445265输出文件示例output.txt30738810274445265数字三角形第3章动态规划动规,两种方式,自顶向下,自底向上•自顶向下定义m[i,j]为从第1行到第i行第j列能得到的最大分数,那么m[i,j]=a[i,j]+max{m[i-1,j],m[i-1,j-1]},当ji;=0,当ji或j=0.1.m[2:n]=0,m[1]=a[1,1],m[0]=0,2.对i=2:n3.对j=i:14.若m[j-1]m[j],则m[j]=m[j-1]5.m[j]+=a[i,j]6.输出max{m[j]|1jn}第3章动态规划动规,两种方式,自顶向下,自底向上•自底向上定义m[i,j]为从第1行到第i行第j列能得到的最大分数,那么m[i,j]=a[i,j]+max{m[i+1,j],m[i+1,j+1]},当ji1.对j=1:n,m[j]=a[n,j],2.对i=n-1到13.对j=1到i4.若m[j+1]m[j],则m[j]=m[j+1]5.m[j]+=a[i,j],6.输出m[1]第四章贪心1.字符a~h出现的频率恰好是前8个Fibonacci数,它们的Huffman编码是什么?将结果推广到n个字符的频率恰好是前n个Fibonacci数的情形.解:根据a~h的频率,画出Huffman编码树如右图所以各字符编码为:h:1,g:01,f:001,e:0001,d:00001,c:000001,b:0000001,a:0000000,推广到n个符号的情形.记第i个符号为i,则f[i]=f[i-1]+f[i-2]由数学归纳法易证明sumi=1kf[i]f[k+2]从而也以类似右图的偏二叉树为其Huffman编码树于是对i=2:n,i的编码为0n-i1,1的编码是0n-1.第四章贪心2.若在0-1背包问题中,各物品依重量递增排列时,其价值恰好降序排列,对这个特殊的0-1背包问题,设计一个有效算法找出最优解,并说明算法的正确性.解:设物品1:n按照重量w[1:n]依次递增,c为容量贪心选择性质:最优解一定包含物品1证明:反证法,若不包含,则可用物品1替换任一物品得到更优解.最优子结构性质:从最优解中去掉物品1,它仍是物品2:n和容量c-w[1]的最优解证明:反证法,否则可以替换2:n的选择得到更优解.算法:按重量递增排序(O(nlogn)),依次放入背包,直到超重(O(n))第四章贪心3.将最优装载问题的贪心算法推广到2艘船的情形贪心算法还能产生最优解吗?解:不行.最优装载要求装载件数最多.其贪心算法是每次选择最轻的物品.设有物品分别重1,2,3,4,5,船1容量7,船2容量8.若按照最优装载的贪心算法,船1装1,2,3,船2装4,只能装4件物品.最优解是船1装1,2,4,船2装3,5.第五章回溯运动员最佳配对问题问题描述:羽毛球队有男女运动员各n人.给定2个nn矩阵P和Q.P[i][j]是男运动员i与女运动员j配混合双打的男运动员竞赛优势;Q[i][j]是女运动员i与男运动员j配混合双打的女运动员竞赛优势.由于技术配合和心理状态等各种因素影响,P[i][j]不一定等于Q[j][i].男运动员i和女运动员j配对的竞赛优势是P[i][j]*Q[j][i].设计一个算法,计算男女运动员最佳配对法,使得各组男女双方竞赛优势的总和达到最大.数据输入:input.txt,第1行有一个正整数n(1n20),接下来2n行是P和Q结果输出:最佳配对的各组男女双方竞赛优势总和31023234345222353451输出52输入:第五章回溯解:男运动员位置不动,女运动员全排列,回溯搜索最优值解空间是n的全排列,所以选择排列树作为解空间结构.变量设计:当前得分cs,最佳得分bests,x[1:n]女运动员的排列定义函数f(i,m,x)=maxj=m+1nP[i][x[j]]*Q[x[j]][i],其中im,是在前m位男运动员已配对的情况下,男运动员i配对其她女运动员的上界定义函数Upb(m,x)=f(m+1,m,x)+f(m+2,m,x)+…+f(n,m,x).当前m位男运动员已配对的情况下