资源描述：
《算法设计与分析王晓东》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
习题2-1 求下列函数的渐进表达式：3n^2+10n; n^2/10+2n; 21+1/n; logn^3; 10log3^n。解答：3n^2+10n=O(n^2),n^2/10+2^n=O(2^n),21+1/n=O(1),logn^3=O(logn),10log3^n=O(n).习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n^2,logn,3^n,20n,2,n^2/3。解答：照渐进阶从高到低的顺序为：n!、3^n、4n^2、20n、n^2/3、logn、2习题2-4(1)假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？(2)若上述算法的计算时间改进为T(n)=n^2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？(3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答：(1)设能解输入规模为n1的问题，则t=3*2^n=3*2^n/64,解得n1=n+6(2)n1^2=64n^2得到n1=8n(3)由于T（n)=常数，因此算法可解任意规模的问题。习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n^2，n^3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？解答：n'=100nn'^2=100n^2得到n'=10nn'^3=100n^3得到n'=4.64nn'!=100n!得到n'a[middle])left=middle; elseright=middle; return-1;}publicstaticintbinarySearch2(int[]a,intx,intn){ intleft=0;intright=n-1; while(left=a[middle])left=middle; elseright=middle; } if(x==a[left])returnleft; elsereturn-1;}publicstaticintbinarySearch4(int[]a,intx,intn){ if(n>0&&x>=a[0]){ intleft=0;intright=n-1; while(left0&&x>=a[0]){ intleft=0;intright=n-1; while(left0&&x>=a[0]){ intleft=0;intright=n-1; while(left0&&x>=a[0]){ intleft=0;intright=n-1; while(lefta[middle])left=middle+1; elseright=middle -1; } ind[0]=right;ind[1]=left; returnfalse;}返回的ind[1]是小于x的最大元素位置，ind[0]是大于x的最小元素的位置。习题3-3 设a[0:n-1]是有n个元素的数组，是非负整数。试设计一个算法讲子数组与换位。要求算法在最坏情况下耗时为，且只用到的辅助空间。分析与解答：算法：三次求反法Algorithm exchange(a,k,n);BeginInverse(n,0,k-1);inverse(n,k,n-1)；inverse（n,0,n-1）End.Algorithm inverse(a,i,j); Begin h=[(j-i+1)/2];Fork=0toh-1do Begin x=a[i+k];a[i+k]=a[j-k];a[j-k]=xend;end习题3-4 如果在合并排序算法的分割步中，讲数组a[0;n-1]划分为[根号2】个子数组，每个子数组中有个元素。然后递归地对分割后的子数组进行排序，最后将所得到的个排好序的子数组合并成所要求的排好序的数组。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。分析与解答：实现上述策略的合并排序算法如下：publicstaticvoidmergesort(int[]a,intleft,intright){ if(left1){ for(inti=0;i1T(n)=O(nlogn) 此递归式的解为：。 习题3-5 设S1,S2...Sk是整数集合，其中每个集合中整数取值范围是，且，试设计一个算法，在时间内将分别排序。分析与解答：用桶排序或基数排序算法思想可以实现整数集合排序。习题3-6 设X[0:n-1]和Y[0:n-1]为两个数组，每个数组中还有n个已排好序的数。试设计一个时间的算法，找出X和Y的2n个数的中位数。分析与解答：（1） 算法设计思想考虑稍一般的问题：设X[i1:j1]和y[i2;j2]是X和Y的排序好的子数组，且长度相同，即j1-i1=j2-i2。找出这两个数组中2(i1-j1+1)个数的中位数。首先注意到，若X(i1)<=Y(j2)，则中位数median满足X(i)<=median<=Y(j2)。同理若X(i1)>=Y(j2)，则Y(j2)<=median<=X(i1)。设m1=(i1+j1)/2,m2=(i2+j2)/2 ，则m1+m2=i1+i2+(j1-i1)/2+(j2-i2)/2由于j1-i1=j2-i2，故(j1-i1)/2+(j2-i2)/2=j2-i2。因此m1+m2=i1+j2。当X(m1)=Y(m2)时，median=X(m1)=Y(m2)。当X(m1)>Y(m2)时，设median1是X(m1:j1)和Y(j2:m2)的中位数，则median=median1。当X(m1)=c解此递归方程可得：T(2n)=O(logn)。习题3-7 Gray码是一个长度为2^n的序列。序列中无相同元素，每个元素都是长度为n位的（0，1）串，相邻元素恰好只有1位不同。用分治策略设计一个算法，对任意的n构造相应的Gray码。分析与解答：考察的简单情形。n=10 1 n=200 01 11 10 n=3000 001 011 010110 111 101 100设n位Gray码序列为G(n)以相反顺序排列的序列为G^-1(n)。从上面的简单情形可以看出G(n)的构造规律：G(n+1)=OG(n)1G^-1(n)。注意到G(n)的最后一个n位串与G^-1(n)的第1个n位串相同，可用数学归纳法证明G(n)的上述构造规律。由此规律容易设计构造G(n)的分治法如下。publicstaticvoidGray(intn){ if(n==1){a[1]=0;a[2]=1;return; } Gray(n-1); for(intk=1<<(n-1),i=k;i>0;i--)a[2*k-i+1]=a[i]+k;}上述算法中将n位（0，1）串看做是二进制整数，第i个串存储在中。完成计算之后，由out输出Gray码序列。publicstaticvoidout(intn){ intm=1<b[j] THEN BEGIN j:=j+1;b[j]:=a[i]; END ELSE BEGIN k:=1; while a[i]>b[k] DO k:=k+1; b[k]:=a[i]; END; 习题4-2考虑下面的整数线性规划问题： 为非负整数，试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。分析与解答：该问题是一般情况下的背包问题，具有最优子结构性质。设所给背包问题的子问题：max∑CkXk(1..i)∑AkXk<=j 的最优值为m(i,j)，即m(i,j)是背包容量为j，可选择物品为1，2，…，i时背包问题的最优值。由背包问题的最优子结构性质，可以建立计算m(i,j）的递归式如下：m(i,j)=max{m(i-1,j),m(i,j-ai)+ci} j>=ai,m(i,j)=m(i-1,j),0<=j,aim(0,j)=m(i,0);m(i,j)=-*,j<0 按此递归式计算出的m(n,b)为最优值。算法所需的计算时间为O(nb)。习题4-3 给定一个由n行数字组成的数字三角形如图3-2所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。分析与解答：记f(uij)为至ij元素的最大路径值,aij：元素(i,j)之值。递归式:F(uij)=max{f(ui-1,j)+aij,f(ui-1,j+1)+aij} (i=1,…n， j=1,…i)经过一次顺推，便可求出从顶至底n个数的n条路径（这n条路径为至底上n个数的n个最大总和的路径），求出这n个总和的最大值，即为正确答案。数据结构: a[i,j].val: 三角形上的数字， a[i,j].f: 由（1，1）至该点的最大总和路径的总和值。typenode=record val,f:integer; end;vara:array[1..maxn,1..maxn]ofnode;procedurefindmax;begin a[1,1].f:=a[1,1].val; fori:=2tondo forj:=1toido begin a[i,j].f:=-1;if(j<>1)and(a[i-1,j-1].f+a[i,j].val>a[i,j].f) thena[i,j].f:=a[i-1,j-1].f+a[i,j].val; if(j<>i)and(a[i-1,j].f+a[i,j].val>a[i,j].f) thena[i,j].f:=a[i-1,j].f+a[i,j].valend; max:=1; fori:=2tondo ifa[n,i].f>a[n,max].fthen max:=i; writeln(a[n,max].f)end;第五章贪心算法习题5-1 特殊的0-1背包问题若在0-1背包问题中，各物品依重量递增排列时，其价值恰好依递减序排列。对这个特殊的0-1背包问题，设计一个有效算法找出最优解，并说明算法的正确性。分析与解答：设所给的输入为W>0，wi>1,vi>0,1≤i≤n。不妨设0≤w1≤w2≤..≤wn。由题意知v1≥v2≥..≥vn>0。由此可知vi/wi≥vi+1/wi+1，1≤i≤n-1.贪心选择性质：当w1>W时问题无解。当w1≤W时，存在0-1背包问题的一个最优解S包含｛1,2,..,n｝使得1∈S。事实上，设S包含｛1,2,..,n｝使0-1背包问题的一个最优解，且1不∈S。对任意i∈S，取Si=S∪{1}-{i}，则Si满足贪心选择性质的最优解。习题5-2Fibonacci序列的Huffman编码试证明：若n个字符的频率恰好是前n个Fibonacci数，用贪心法得到它们的Huffman编码树一定为一棵“偏斜树”。证明：n个字符的频率恰好是前n个Fibonacci数，则相应的哈夫曼编码树自底向上第i个内结点中的数为k=0∑if(k)。用数学归纳法容易证明k=0∑ifkk=1∑ifk+fi+1=k=1∑i+1fk， 说明对i+3上述结论成立.该性质保证了频率恰好是前n个Fibonacci数的哈夫曼编码树具有“偏斜树”形状。习题5-3 记T为图G=(V,E)的最小生成树，同时设顶点集合A包含V，设(u,v)∈E为连接A和V–A的权重最小的边，证明：必有(u,v)∈T.证明：用反证法。因为T为图G=(V,E)的最小生成树，在连接A和V–A的边中至少有一条属于T中。假设(u,v)不属于T，则必有(u’,v’)属于T,这里(u’,v’)也是连接A和V–A的边,且(u’,v’)的权重大于(u,v)的权重.若将T中的(u’,v’)换成(u,v)得到T’,显然T’也是G的一个生成树。但由于(u’,v’)的权重大于(u,v)的权重，可知T的权重大于T’的权重，这与”T为图G=(V,E)的最小生成树”矛盾。习题5-4 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。分析与解答： 设所给的n个活动为1，2，…，n，它们的开始时间和结束时间分别为s[i]和f[i]，i=1~n，且f[1]sum)sum=curr; } returnsum;}习题5-5 假设要在m个会场里安排一批活动，并希望使用尽可能多地安排活动。设计一个有效的贪心算法进行安排。Algorithmgreedy(s,f,m,n); Inputs[1:n],f[1:n]; Outputx[1:m,1:n]; Begin 对数组s和f中的2n个元素排序存入数组y[1:2n]中； 空闲栈清空；d数组所有元素置初值0； Fori=1to2ndo Begin If元素y[i]原属于s then If空闲栈不空then 取出栈顶场地j; d[j]=d[j]+1; y[i]存入x[j,d[j]]; If元素y[i]原属于f then 设其相应的s存于x[j,k]中，将j存入空闲栈中； End Fori=1tomdo Forj=1tod[j]do Outputx[i,j]; End习题5-6删数问题问题描述给定n位正整数a，去掉其中任意个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。分析与解答：贪心策略：最近下降点优先。publicstaticvoiddelek(Stringa){ inti,m=a.length(); if(k>=m){System.out.println(0);return;} while(k>0){ for(i=0;(i1&&a.charAt(0)==’0’)a=a.Remove(0,1); System.out.println(a);}第六章回溯法习题6-1子集和问题子集和问题的一个实例。其中，是一个正整数的集合，sum是一个正整数。子集和问题判定是否存在A的一个子集A1，使得。试设计一个解子集和问题的回溯法。分析与解答：设计解子集和问题的回溯法如下。Algorithmsubset-sumbegin Forj=1tondo Begin sp=0;t=sum;i=j;finish=false; repeat ift>=a[i]thenbegin sp=sp+1；s[sp]=i;t=t-a[i]; ift=0theni=n; end; i=i+1; whilei>ndo ifsp>1then begin ift=0thenout; t=t+a[s[sp]];i=s[sp]+1;sp=sp-1 end else begin finish=true;i=1enduntilfinishendend习题6-2中国象棋的半个棋盘如图所示，马自左下角往右上角跳。规定只许向右跳，不许向左跳，计算所有的行走路线。AlgorithmchessBegin top=0;y0=0;x0=0;di=1;r=0;push;repeat pop; whiledi<=4do begin g=x0+x[di];h=y0+y[di]; if(g=8)and(h=4)thenout elsebegindi=di+1；push; x0=g;y0=h;di=1end enduntilemptyendalgorithmpushbegin top=top+1；sx[top]=x0;sy[top]=y0;d[top]=di; end algorithmpopbegin x0=sx[top];y0=sy[top];di=d[top];top=top－1；end 习题6-3. 在n个连成排的方格内填入R或B，但相邻连个方格内不能都填R。计算所有可能的填法。R B B R BAlgorithmRed-Black;Begin Fori=1tondob[i]=0; T=1;Repeat b[t]=b[t]+1; ifb[t]>2then{回溯} beginb[t]=0;t=t-1;end else begin ifb[t]=2thena[t]=‘B’ elseifa[t-1]=’R’thent=t-1elsea[t]=‘R’; ift=nthenoutputaelset=t+1 end untilt=0第七章分支限界法习题7-2.写出用分支界限法求解下面的重排九宫问题的算法。解答：我们对九宫中的位置做如下的编号：位置编号 1 2 38 9 47 6 5则初始状态用向量S0=（8，1，2，3，4，5，7，0，6）表示，目标状态用S*=（1，2，3，4，5，6，7，8，0）表示。我们使用一个堆heap,将启发函数值H(x)最小的状态x置于堆顶优先搜索。H(x)定义如下：H(x)=h1(x)+3h2(x)其中，h1(x)为状态x与目标状态不相同的数字的数目，h2（x)=y=e∑N(y)，这里，N(y)=0,y和其后继的相对位置不变N(y)=1,y处于中心N(y)=2,q其他算法：Algorithm LC(S0,S*)Input: 初始状态向量S0,目标状态S*；Output: 达到目标状态的状态序列；BeginS=S0; if S目标状态S*thenOutput(S及其所有前驱) elseadd(S,heap) whileheap非空do取出堆heap顶部状态E；forE的每个可能的后继状态xdo if x为目标状态S*thenOutput(x及其所有前驱);return else 计算x的启发函数H(x); add(x,heap) endifendfor endwhileend第八章NP完全问题习题8-1证明析取范式的可满足性问题属于P类。分析与解答： 析取范式α是由因子之和的和式给出的。这里因子是指变量x或x拔，每个因子之积称为一个析取式。例如x1x2+x2x3+ x3就是一个析取范式。 设给定一个析取范式α=i=1∑mfi(x1,x2,x3,...,xn)，其中fi(x1,x2,..,xn)是变量xj或xj拔，j=1~n的一个析取范式，i=1~m。α是可满足的，当且仅当存在i,1≤i≤m，使fi(x1,x2,..,xn)是可满足的。如果有一个多项式时间算法能判断任何一个析取式的可满足性，则用该算法对α的每个析取项逐一判断就可以在多项式时间内确定析取范式α的可满足性。因此，问题可简化为找一个确定析取式可满足性的多项式时间算法。 设析取范式f(x1,x2,..,xn)=α1α2..αk，其中αi∈{xj,｜1≤j≤n}。 可以设计在O(n+k)时间内确定析取式f(x1,x2,..,xn)=α1α2...αn可满足性的算法。因此，析取范式的可满足性问题是多项式时间可解的，即它属于P类。
