算法设计方案分析晓东

1、精选优质文档-倾情为你奉上习题2-1  求下列函数的渐进表达式：3n2+10n。  n2/10+2n。  21+1/n。  logn3。  10 log3n 。解答：3n2+10n=O(n2),n2/10+2n=O(2n),21+1/n=O(1),logn3=O(logn),10log3n=O(n).习题2-3  照渐进阶从低到高的顺序排列以下表达式：n!，4n2,logn,3n,20n,2,n2/3。 解答：照渐进阶从高到低的顺序为：n!、 3n、4n2 、20n、n2/3、logn、2习题2-4 (1)假设某算法在输入规模为n时的

2、计算时间为T(n)=3*2n。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？(2)若上述算法的计算时间改进为T(n)=n2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？(3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答：(1)设能解输入规模为n1的问题，则t=3*2n=3*2n/64,解得n1=n+6(2)n12=64n2得到n1=8n(3)由于T（n)=常数，因此算法可解任意规模的问题。习题2-5 

3、  XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n2，n3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？解答：n'=100nn'2=100n2得到n'=10nn'3=100n3得到n'=4.64nn'!=100n!得到n'<n+log100=n+6.64习题2-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n)或f(n)=(g(n)或f(n)=（g(n)

4、），并简述理由。解答：（1）f(n)=logn2。g(n)=logn+5. logn2=（logn+5）(2)f(n)=logn2。g(n)=根号n. logn2=O(根号n)(3)f(n)=n。g(n)=(logn)2. n=(（logn）2)(4)f(n)=nlogn+n。g(n)=logn. nlogn+n=（logn）(5)f(n)=10。g(n)=log10. 10=(log10)(6)f(n)=(logn)2。g(n)=logn. (logn)2=（logn）(7)f(n)=2n。g(n)=100n2. 2n=（100n2）(8)f(n)=2n。g(n)=3n. 2n=O(3n)习

5、题2-7 证明：如果一个算法在平均情况下的计算时间复杂性为（f(n)），则该算法在最坏情况下所需的计算时间为（f(n)）。证明：Tavg(N)=IeDnP(I)T(N,I)             IeDnP(I)IeDnmaxT(N,I')             =T(N,I*)IeDnP(I)    &#

6、160;        =T(N,I*)=Tmax(N)因此，Tmax(N)=（Tavg(N)）=（(f(n)）=（f(n)）习题2-8 求解下列递归方程：So=0。Sn=2Sn-1+2n-1.解答： 1应用零化子化为齐次方程， 2解此齐次方程的特征方程， 3由特征根构造一般解， 4再由初始条件确定待定系数，得到解为：Sn=(n-1)2n+1习题2-9 求解下列递归方程Ho=2。H1=8。Hn=4Hn-1-4Hn-2.解：Hn=2(n+1)(n+1)第三章 递归与分治策略习题3-1&#

7、160; 下面的7个算法都是解决二分搜索问题的算法。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算法的正确性证明。public static int binarySearch1(int a,int x,int n) int left=0。 int right =n-1。 while (left<=right)   int middle = ( left + right )/2。  if ( x = amiddle) return middle。  if ( x>

8、amiddle) left = middle。  else right = middle。 return -1。public static int binarySearch2(int a, int x, int n) int left = 0。 int right = n-1。 while ( left < right-1 )   int middle = ( left + right )/2。  if ( x < amiddle) right = middle。  els

9、e left = middle。  if (x = aleft) return left。 else return -1public static int binarySearch3(int a, int x, int n) int left = 0。 int right = n-1。 while ( left +1 != right)   int middle = ( left + right)/2。  if ( x>= amiddle) left = middle。  els

10、e right = middle。   if ( x = aleft) return left 。 else return -1。public static int binarySearch4(int a, int x, int n) if (n>0 && x>= a0)   int left = 0。 int right = n-1。  while (left < right )    int middle = (left + right

11、)/2。   if ( x < amiddle) right = middle -1 。   else left = middle。     if ( x = aleft) return left。   return -1。public static int binarySearch5(int a, int x, int n) if ( n>0 && x >= a0 )   int left

12、= 0。 int right = n-1。  while (left < right )    int middle = ( left + right +1)/2。   if ( x < amiddle) right = middle -1。   else left = middle 。     if ( x = aleft) return left。   return -1。public st

13、atic int binarySearch6(int a, int x, int n) if ( n>0 && x>= a0)   int left = 0。 int right = n-1。  while ( left < right)    int middle = (left + right +1)/2。   if (x < amiddle) right = middle 1。   else left = mi

14、ddle + 1。     if ( x = aleft) return left 。   return -1。public static int binarySearch7(int a, int x, int n) if ( n>0 && x>=a0)   int left = 0。 int right = n-1。  while ( left < right)    int middle = ( l

15、eft + right + 1)/2。   if ( x < amiddle) right = middle。   else left = middle。     if ( x = aleft) return left。   return -1。分析与解答：算法binarySearch1数组段左右游标left和right的调整不正确，导致陷入死循环。算法binarySearch2数组段左右游标left和right的调整不正确，导致当x=an-1时返回

16、错误。算法binarySearch3数组段左右游标left和right的调整不正确，导致当x=an-1时返回错误。算法binarySearch4数组段左右游标left和right的调整不正确，导致陷入死循环。算法binarySearch5正确，且当数组中有重复元素时，返回满足条件的最右元素。算法binarySearch6数组段左右游标left和right的调整不正确，导致当x=an-1时返回错误。算法binarySearch7数组段左右游标left和right的调整不正确，导致当x=an-1时陷入死循环。习题3-2  设a0:n-1 是已排好序的数组。请改写二分搜索算法，使得当搜索元

17、素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。分析与解答：改写二分搜索算法如下：public static boolean binarySearch(int a, int x, int left, int right, int ind) int middle。 while ( left <= right )   middle = (left + right)/2。  if (x = amiddle) ind0=ind1=middle。 return

18、true。  if (x > amiddle) left = middle + 1。  else right = middle -1。  ind0 = right。 ind1=left。 return false。返回的ind1是小于x的最大元素位置，ind0是大于x的最小元素的位置。习题3-3  设a0:n-1 是有n个元素的数组， 是非负整数。试设计一个算法讲子数组 与 换位。要求算法在最坏情况下耗时为 ，且只用到 的辅助空间。分析与解答：算法： 三次求反法Algorithm  exchange

19、(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 。For k=0 to h-1 do    Begin  x=ai+k。 ai+k=aj-k。 aj-k= x end 。end习题3-4  如果在合并排序算法的分割步中，讲数组a0。n-1 划分为 根号2】个子数组，每个子数组中有 个元素。然后递归地对分

20、割后的子数组进行排序，最后将所得到的 个排好序的子数组合并成所要求的排好序的数组 。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。分析与解答：实现上述策略的合并排序算法如下：public static void mergesort(int a, int left ,int right)  if (left < right )   int j = (int) Math.sqrt(right left+1)。  if (j>1)    for (int i=0。 i<j。 i+

21、) mergesort(a, left+i*j,left+(i+1)*j-1)。   mergesort(a,left+i*j,right)。    mergeall(a,left,right)。 其中，算法mergeall合并根号n 个排好序的数组段。在最坏情况下，算法mergeall需要O（nlogn) 时间。因此上述算法所需的计算时间 T(n)满足：T(n)=O(1),n<=1T(n)=根号n*T(根号n),n>1T(n)=O(nlogn) 此递归式的解为： 。习题3-5 &#

22、160; 设S1,S2.Sk 是整数集合，其中每个集合 中整数取值范围是 ，且 ，试设计一个算法，在 时间内将 分别排序。分析与解答：用桶排序或基数排序算法思想可以实现整数集合排序。习题3-6  设X0:n-1 和Y0:n-1 为两个数组，每个数组中还有n个已排好序的数。试设计一个 时间的算法，找出X和Y的2n个数的中位数。分析与解答：（1） 算法设计思想考虑稍一般的问题：设Xi1:j1 和yi2。j2 是X和Y的排序好的子数组，且长度相同，即j1-i1=j2-i2 。找出这两个数组中2(i1-j1+1) 个数的中位数。首先注意到，若X(i1)<=Y(j2) ，则中位

23、数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) 的中位数，则med

24、ian=median1 。当X(m1)<Y(m2) 时，设median2 是X(i1:m1) 和Y(m2:j2) 的中位数，类似地有median=median2 。通过以上讨论，可以设计出找出两个子数组X(i1:j1) 和Y(i2:j2) 的中位数median的算法。（2） 设在最坏情况下，算法所需的计算时间为T(2n) 。由算法中m1 和m2 的选取策略可知，在递归调用时，数组X和Y的大小都减少了一半。因此，T(2n) 满足递归式： T(2n)=(1),n<=1T(2n)=T(n)+O(1),n>=c解此递归方程可得：T(2n)=O(logn) 。习题3

25、-7    Gray码是一个长度为2n 的序列。序列中无相同元素，每个元素都是长度为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)。从上面的简单情形可以

26、看出G(n) 的构造规律：G(n+1)=OG(n)1G-1(n) 。注意到G(n) 的最后一个n位串与G-1(n) 的第1个n位串相同，可用数学归纳法证明G(n) 的上述构造规律。由此规律容易设计构造G(n) 的分治法如下。public static void Gray(int n) if ( n = 1) a1 = 0。 a2 = 1。 return。  Gray(n-1)。 for ( int k = 1<< ( n - 1), i = k。 i > 0。 i-) a2*k-i+1=ai + k。上述算法中将n位（0，1）串看做是二进制整数，

27、第i个串存储在 中。完成计算之后，由out输出Gray码序列。public static void out(int n) int m=1<<n。 for (int i=1。 i<=m。 i+)   String str=Integer.toBinaryString(ai)。  int s=str.length()。  for ( int j=0。 j<n-s。 j+) System.out.print(“0”)。  System.out.println(Integer.t

28、oBinaryString(ai)+” ”)。  System.out.println()。第四章 动态规划习题4-1  设计一个 时间的算法，找出由n个数组成的序列的最长单调递增子序列。分析与解答：引入一个数组b，使bi为已扫描部分的长度为的升序子序列的最小终值。按此思想设计的动态规划算法描述如下：j:=0。  b0:=-maxint。            FOR  i:=1  TO  n  DO  &

29、#160;             IF  ai>bj  THEN                    BEGIN  j:=j+1。 bj:=ai。  END        

30、0;       ELSE                   BEGIN     k:=1。                    

31、60;         while  ai>bk  DO  k:=k+1。                               bk:=ai。    

32、60;                 END。 习题4-2 考虑下面的整数线性规划问题：   为非负整数， 试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。分析与解答：该问题是一般情况下的背包问题，具有最优子结构性质。设所给背包问题的子问题：maxCkXk(1.i)AkXk<=j 的最优值为m(i,j) ，即 m(i,j)是背包容量为j，可选择物品为1，2，i时背包问题的最优值。

33、由背包问题的最优子结构性质，可以建立计算m(i,j） 的递归式如下：m(i,j)=maxm(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)之值。递

34、归式:F(uij)=maxf(ui-1,j)+aij, f(ui-1,j+1)+aij   (i=1,n，   j=1,i)经过一次顺推，便可求出从顶至底n个数的n条路径（这n条路径为至底上n个数的n个最大总和的路径），求出这n个总和的最大值，即为正确答案。数据结构:  ai,j.val:  三角形上的数字， ai,j.f:     由（1，1）至该点的最大总和路径的总和值。type node=record    val, f: integer。 

35、; end。var a:array 1. maxn, 1.maxn of cedure findmax。begin a 1,1. f :=a1,1.val。  for i:=2 to n do   for j:=1 to i do    begin     ai,j. f:=-1。if (j<>1) and (a i-1,j-1.f+ai,j.val > a i,j.f)    then ai,j. f

36、:=a i-1,j-1. f+ai,j.val。    if (j<>i) and(a i-1,j.f+ai,j.val > ai,j.f)     then ai,j. f:=ai-1,j. f+ai,j. valend。 max:=1。 for i:=2 to n do    if an,i. f> an, max .f then         max:=i。

37、0; writeln (a n, max. f)end。第五章 贪心算法习题5-1 特殊的0-1背包问题若在0-1背包问题中，各物品依重量递增排列时，其价值恰好依递减序排列。对这个特殊的0-1背包问题，设计一个有效算法找出最优解，并说明算法的正确性。分析与解答：设所给的输入为W>0，wi>1,vi>0,1in。不妨设0w1w2.wn。由题意知v1v2.vn>0。由此可知vi/wivi+1/wi+1，1in-1.贪心选择性质：当w1>W时问题无解。当w1W时，存在0-1背包问题的一个最优解S包含1,2,.,n使得1S。事实上，设S包含1,2,.,n使0-1

38、背包问题的一个最优解，且1不S。对任意iS，取Si=S1-i，则Si满足贪心选择性质的最优解。习题5-2 Fibonacci序列的Huffman编码试证明：若n个字符的频率恰好是前n个Fibonacci数，用贪心法得到它们的Huffman编码树一定为一棵“偏斜树”。证明：n个字符的频率恰好是前n个Fibonacci数，则相应的哈夫曼编码树自底向上第i个内结点中的数为k=0if(k)。用数学归纳法容易证明k=0ifk<fi+2。  因f1=1,f2=1,f3=2,可知i=1时，上述结论成立。  设对i+2上述结论成立，即有k=0 i fk<fi+2， 因 

39、;fi+3=fi+2 + fi+1>k=1 i fk + fi+1= k=1 i+1 fk，  说明对i+3上述结论成立. 该性质保证了频率恰好是前n个Fibonacci数的哈夫曼编码树具有“偏斜树”形状。习题5-3  记 T为图G= (V, E) 的最小生成树，同时设顶点集合A包含V，设 (u, v) E 为连接A 和 VA的权重最小的边，证明：必有(u, v) T. 证明：用反证法。因为T为图G= (V, E) 的最小生成树，在连接A 和 VA的边中至少有一条属于T中。假设(u, v) 不属于T，则必有(u, v) 属于T, 这里(u, v) 也是连接A 和 VA

40、的边, 且 (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，它们的开始时间和结束时间分别为si和fi，i=1n，且f1<f2<.<fn。  可以将n个活动1

41、，2，n看作实直线上的n个半闭活动区间(si,fi,i=1n)。所讨论的问题实际上是求这n个半闭区间的最大重叠数。因为重叠的活动区间所相应的活动是互不相容的。若这n个活动区间的最大重叠数为m，则这m个重叠区间所对应的活动互不相容，因此至少安排m个会场来容纳这m个活动。  为了有效地对这n个活动进行安排，首先将n个活动区间的2n个端点排序。然后，用扫描算法，从左到右扫描整个实直线。在每个事件点处（即活动的开始时刻或结束时刻）作会场安排。当遇到一个开始时刻si，就将活动i安排在一个空闲的会场中。遇到一个结束时候fi，就将活动i占用的会场释放到空闲会场栈中，以备使用。经过这样一遍扫描后，最

42、多安排了m个会场（m是最大重叠区间数）。因此所作的会场安排是最优的。上述算法所需的计算时间主要用于对2n个区间端点的排序，这需要O(nlogn)计算时间。 具体算法描述如下。public static int greedy(point x) int sum=0, curr=0, n=x.length。 MergeSort.mergeSort(x)。 for (int i=0。 i<n。i+)   if (xi.leftend() curr+。  else curr-。  /处理xi=xi+

43、1的情况  if ( i = pareTo(xi+1)<0)&& curr>sum) sum=curr。  return sum。习题5-5  假设要在m个会场里安排一批活动，并希望使用尽可能多地安排活动。设计一个有效的贪心算法进行安排。Algorithm greedy(s,f,m,n)。  Input s1:n, f1:n。  Output x1:m, 1:n。 Begin 对数组s和f中的2n个元素排序存入数组y1:2n中； 空闲栈清空；d数组所

44、有元素置初值0； For i=1 to 2n do    Begin     If 元素yi 原属于s  then    If 空闲栈不空then   取出栈顶场地j。  dj=dj+1。  yi 存入xj, dj 。         If 元素yi 原属于f  then        &

45、#160;    设其相应的s 存于xj,k 中，将j存入空闲栈中；        End  For i= 1 to m do   For j=1 to dj do       Output xi,j。 End习题5-6 删数问题 问题描述给定n位正整数a，去掉其中任意个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。分析

46、与解答：贪心策略：最近下降点优先。public static void delek(String a) int i,m=a.length()。 if ( k>= m) System.out.println(0)。 return。 while (k>0)   for (i=0。 (i<a.length()-1)&&(a.charAt(i)<=a.charAt(i+1)。 i+)  a= a.Remove(i,1)。 k-。  while (a.length()>

47、1 && a.charAt(0)=0) a=a.Remove(0,1)。 System.out.println(a)。第六章 回溯法习题6-1 子集和问题 子集和问题的一个实例 。其中， 是一个正整数的集合，sum是一个正整数。子集和问题判定是否存在A的一个子集A1，使得 。试设计一个解子集和问题的回溯法。分析与解答：设计解子集和问题的回溯法如下。Algorithm subset-sumbegin For j=1 to n do    Begin      sp=0。 t=sum。 i=j。 fin

48、ish=false。           repeat        if t>=ai then begin         sp=sp+1；ssp=i。 t=t-ai。  if t=0 then i=n。       end。     

49、60; i=i+1。        while i>n do          if sp>1 then            begin               if t=0 then out。  t=

50、t+assp。 i=ssp+1。 sp=sp-1           end          else   begin  finish=true。 i=1 enduntil finishendend习题6-2 中国象棋的半个棋盘如图所示，马自左下角往右上角跳。规定只许向右跳，不许向左跳，计算所有的行走路线。 Algorithm chess Begin   

51、 top=0。 y0=0。 x0=0。 di=1。 r=0。push。repeat  pop。  while di<=4 do     begin       g=x0+xdi。 h=y0+ydi。       if (g=8) and (h=4) then out          else begin di=di+1；push。  x0=g。 y0

52、=h。 di=1 end      enduntil emptyendalgorithm pushbegin  top=top+1；sxtop=x0。 sytop=y0。 dtop=di。    end          algorithm popbegin     x0=sxtop。 y0=sytop。 di =dtop。 top=top1；end 习题6-3.  在n个连成

53、排的方格内填入R或B，但相邻连个方格内不能都填R。计算所有可能的填法。R B B R BAlgorithm Red-Black。Begin  For i=1 to n do bi=0。  T=1。Repeat    bt=bt+1 。    if bt>2 then 回溯       begin bt=0 。 t=t-1 。 end      else  begin             if bt=2 then at= B