算法设计方案书与分析报告王晓东

1、习题2-1求下列函数的渐进表达式：3nA2+10n;nA2/10+2n;21+1/n;lognA3;10 log3An 。解答：3nA2+10n=O(nA2),nA2/10+2An=O(2An),21+1/n=O(1),lognA3=O(logn), 10log3An=O(n).习题2-3照渐进阶从低到高的顺序排列以下表达式：n!, 4nA2,logn,3An,20n,2,nA2/3。解答：照渐进阶从高到低的顺序为：n!、3An、4nA2 、20n、人2/3、logn、2习题2-4(1) 假设某算法在输入规模为n时的计算时间为T(n)=3*2An。在某台计算机上实现并完成该算法的时间为t秒。现

2、有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？(2) 若上述算法的计算时间改进为T(n)=nA2 ，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？(3) 若上述算法的计算时间进一步改进为，其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答： 设能解输入规模为n1的问题，_则t=3*2An=3*2An/64, 解得n1=n+6(2)n1A2=64nA2 得到 n仁8n由于T( n)=常数，因此算法可解任意规模的问题。习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产

3、品的100倍。对于计算复杂性分别为n， nA2，nA3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为 n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？解答：n'=100nn'A2=100nA2得到 n'=10nn'A3=100nA3得到 n'=4.64nn'!=100n!得到 n'<n+log100=n+6.64习题2-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n)或f(n)= Q(g(n)或f(n)= 9 (g(n)，并简述理 由。解答：(1) f(n)=lognA2;

4、g(n)=logn+5. lognA2= 9(logn+5 )(2) f(n)=lognA2;g(n)=根号 n. lognA2=O(根号 n)(3) f(n)=n;g(n)=(logn)A2. n=(log(人2)(4) f(n)=nlogn+n;g(n)=logn. nlogn+n=(£lOgn)(5) f(n)=10;g(n)=log10. 10=9 (log10)(6) f(n)=(logn)A2;g(n)=logn. (logn)A2=(logn ) Q(7) f(n)=2An;g(n)=100nA2. 2An=(1Q0nA2 )(8) f(n)=2An;g(n)=3An.

5、 2An=O(3An)习题2-7证明：如果一个算法在平均情况下的计算时间复杂性为9 (f(n)，则该算法在最坏情况下所需的计算时间为Q (f(n)。证明：Tavg(N)=leDn XP(I)T(N,I)< leDn 刀 P(I)IeDnmaxT(N,I')=T(N,l*)leDn 刀 P(l)=T(N,l*)=Tmax(N)因此，Tmax(N)=Q(Tavg(N) ) =Q ( 9 (f(n) =Q (f(n)习题2-8求解下列递归方程：So=0;Sn=2Sn-1+2An-1.解答：1应用零化子化为齐次方程，2解此齐次方程的特征方程，3由特征根构造一般解，4再由初始条件确定待定系

6、数，得到解为：Sn=(n-1)2An+1习题2-9求解下列递归方程Ho=2;H1=8;Hn=4Hn-1-4Hn-2.解：Hn=2A(n+1)(n+1)第三章递归与分治策略习题3-1下面的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

7、 = amiddle) return middle;if ( x> 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;else left = middle;if (x = aleft

8、) 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;else right = middle;if ( x = aleft) return left ;else return -1;public static int binarySearch4(i

9、nt a, int x, int n) if (n>0 && x>= a0) int left = 0; int right = n-1;while (left < right ) int middle = (left + right )/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

10、 && 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 = middle ;if ( x = aleft) return left;return -1;public static int binarySearch6(int a, int x, int n)if ( n>0 && x>= a0) int

11、 left = 0; int right = n-1;while ( left < right) int middle = (left + right +1)/2;if (x < amiddle) right = middle -1; else left = middle + 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

12、-1;while ( left < right) int middle = ( left + right + 1)/2;if ( x < amiddle) right = middle;else left = middle;if ( x = aleft) return left;return -1;分析与解答:算法算法binarySearch1binarySearch2数组段左右游标数组段左右游标leftleftrightright算法binarySearch3数组段左右游标leftright的调整不正确,的调整不正确,的调整不正确,算法算法binarySearch4binaryS

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

14、，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 true;if (x > amiddle) left = middle + 1;else right = middle -1;indO = right;

15、 ind1=left;return false;返回的ind1是小于x的最大元素位置，indO是大于x的最小元素的位置。习题3-3设a0:n-1是有n个元素的数组，是非负整数。试设计一个算法讲子数组与换位。要求算法在最坏情况下耗时为，且只用到的辅助空间。分析与解答：算法：三次求反法Algorithm exchange(a, k, n);Beginlnverse(n,0,k-1); inverse(n,k,n-1) ； inverse ( n,0,n-1 )End.Algorithm inverse(a, i, j);Beginh=(j-i+1)/2;For k=0 to h-1 doBegin

16、 x=ai+k; ai+k=aj-k; aj-k= x end ;end习题3-4如果在合并排序算法的分割步中，讲数组a0;n-1戈卩分为根号2】个子数组，每个子数组中有个元素。然后递归地对分割后的子数组进行排序，最后将所得到的个排好序的子数组合并成所要求的排好序的数组。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。分析与解答：实现上述策略的合并排序算法如下：public static void mergesort(int a, int left ,int right)if (left < right ) int j = (int) Math.sqrt(right-eft+

17、1);if (j>1) for (int i=0; i<j; i+) mergesort(a, left+i*j,left+(i+1)*j-1);mergesort(a,left+i*j,right);mergeall(a,left,right);其中，算法mergeall合并根号n个排好序的数组段。在最坏情况下，算法mergeall需要0 (nlogn)时间< 因此上述算法所需的计算时间T(n)满足：T(n)=O(1),n<=1T(n)=根号 n*T(根号 n),n>1T(n)=O(nlogn)此递归式的解为:习题3-5 设S1,S2.Sk是整数集合，其中每个集

18、合中整数取值范围是，且，试设计一个算法，在时间内将分别排序。分析与解答：用桶排序或基数排序算法思想可以实现整数集合排序。习题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)，则中位数 median 满足 X(i)<=median<=Y(j2) 。同理若 X(i1)

19、>=Y(j2)， 则 Y(j2)v=median<=X(i1) 。设 m仁(i1+j1)/2,m2=(i2+j2)/2，贝U 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)时，设 medianl是 X(m1:j1)和 Y(j2:m2)的中位数，贝U median=median1 。当 X(m1)<Y(m2)时，设 median2是 X(i1:m

20、1)和 Y(m2:j2)的中位数，类似地有 median=median2。通过以上讨论，可以设计出找出两个子数组X(i1:j1)和Y(i2:j2)的中位数median的算法。(2) 设在最坏情况下，算法所需的计算时间为T(2n)。由算法中ml和m2的选取策略可知，在递归调用时，数组X和Y的大小都减少了一半。因此，T(2n)满足递归式：T(2n)=(1),n<=1T(2n)=T(n)+0(1),n>=c解此递归方程可得：T(2n)=O(logn)。习题3-7 Gray码是一个长度为2An的序列。序列中无相同元素，每个元素都是长度为n位的(0, 1)串，相邻元素恰好只有1位不同。用分治

21、策略设计一个算法，对任意的n构造相应的Gray码。分析与解答：考察的简单情形。n=10 1n=200 0111 10n=3000 001 011 010110 111 101 100设n位Gray码序列为G(n)以相反顺序排列的序列为GA-1(n)。从上面的简单情形可以看出G(n)的构造规律：G(n+1)=OG(n)1GA-1(n)。注意到G(n)的最后一个n位串与GA-1(n)的第1个n位串相同，可用数学归纳法证明G(n)的上述构造规律。由此规律容易设计构造G(n)的分治法如下。public static void Gray(int n) if ( n = 1) a1 = 0; a2 = 1

22、; return; Gray(n-1);for ( int k = 1<< ( n - 1), i = k; i > 0; i-) a2*k-i+1=ai + k;上述算法中将n位(0, 1)串看做是二进制整数，第i个串存储在 中。完成计算之后，由out输出Gray码序列。public static void out(int n)int m=1<<n;for (int i=1; i<=m; i+) String str=lnteger.toBinaryString(ai);int s=str.length();for ( int j=0; j<n- s

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

24、i>bk DO k:=k+1;bk:=ai;END;习题4-2考虑下面的整数线性规划问题：为非负整数，试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。分析与解答：该问题是一般情况下的背包问题，具有最优子结构性质。设所给背包问题的子问题：maX2CkXk(1.i) EAkXk<=j的最优值为m(i,j)，即m(i,j)是背包容量为j，可选择物品为1, 2，i时背包问题的最优值。由背包问题的最优子结构性质，可以建立计算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,a

25、im(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)=maxf(ui-1,j)+aij, f(ui-1,j+1)+aij(i=1,j=1,i)经过一次顺推，便可求出从顶至底n个数的n条路径(这n条路径为至底上n个数的n个最大总和的路径)求出这n个总和的最大值，即为正确答案。数

26、据结构：ai,j.val:三角形上的数字，ai,j.f:由(1， 1)至该点的最大总和路径的总和值。type node=recordval, f: integer;end;var a:array 1. maxn, 1.maxn of node;procedure findmax;begina 1,1. f :=a1,1.val;for i:=2 to n dofor j:=1 to i dobeginai,j. f:=-1;if (j<>1) and (a i-1,j-1.f+ai,j.val > a i,j.f)then ai,j. f:=a i-1,j-1. f+ai,j

27、.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 doif an,i. f> an, max .f thenmax:=i;writeln (a n, max. f)end;第五章贪心算法习题5-1特殊的0-1背包问题若在0-1背包问题中，各物品依重量递增排列时，其价值恰好依递减序排列。对这个特殊的0-1背包问题,设计一个有效算法找出最优解，并说明算法的正确性。分析与解答： 设所给的输入为 W>0 , wi&

28、gt;1,vi>0,1 <i <n不妨设0Ww1Ww2c. <wn。由题意知 v1 >v2>. >vn>C。由此 可知 vi/wi >vi+1/wi+1 , 1<i <-1.贪心选择性质：当w1>W时问题无解。当wKW时，存在0-1背包问题的一个最优解S包含 1,2,.,n 使得1 So事实上，设S包含 1,2,.,n 使0-1背包问题的一个最优解，且1不 So对任意i S,取Si=S U 1-i,则Si满足贪心选择性质的最优解。习题5-2 Fibonacci序列的Huffman编码试证明：若n个字符的频率恰好是前 n个F

29、ibonacci数，用贪心法得到它们的Huffman编码树一定为一棵 偏斜树”证明：n个字符的频率恰好是前n个Fibonacci数，则相应的哈夫曼编码树自底向上第i个内结点中的数为k=0刀if(k)用数学归纳法容易证明k=0刀ifkvfi+2。因f1=1,f2=1,f3=2, 可知i=1时，上述结论成立。设对i+2上述结论成立，即有 k=0刀i fk<fi+2，因fi+3=fi+2 + fi+1>k=1E i fk + fi+1= k=1， E i+1 fk说明对i+3上述结论成立.该性质保证了频率恰好是前n个Fibonacci数的哈夫曼编码树具有偏斜树"形状。习题5-3

30、记T为图G= (V, E)的最小生成树，同时设顶点集合 A包含V,设(u, v) E为连接A和7 的权重最小的边，证明：必有(u, v) T.证明：用反证法。因为T为图G= (V, E)的最小生成树，在连接 A和V-A的边中至少有一条属于 T中。假设(u, v)不属于T，则必有(u ' , v属于)T,这里(u ' , v也是连接A和7 的边，且(u ',的权重大于(u, v)的 权重.若将T中的(u ' , v换成(u, v)得到T',显然T'也是G的一个生成树。但由于(u ' , v的权重大于(u, v)的 权重，可知T的权重大于T&

31、#39;的权重，这与”伪图G= (V, E)的最小生成树”矛盾。习题5-4假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。分析与解答：设所给的n个活动为1，2，n，它们的开始时间和结束时间分别为si和fi，i=1n，且f1vf2v.vfn o可以将n个活动1，2，n看作实直线上的n个半闭活动区间(si,fi,i=1n)。所讨论的问题实际上 是求这n个半闭区间的最大重叠数。因为重叠的活动区间所相应的活动是互不相容的。若这n个活动区间的最大重叠数为 m，则这m个重叠区间所对应的活动互不相容，因此至少安排m个会场来容纳这 m个活动。为了有效地对这n个活动

32、进行安排，首先将 n个活动区间的2n个端点排序。然后，用扫描算法，从左到 右扫描整个实直线。在每个事件点处(即活动的开始时刻或结束时刻)作会场安排。当遇到一个开始时刻 si，就将活动i安排在一个空闲的会场中。遇到一个结束时候fi，就将活动i占用的会场释放到空闲会场栈中，以备使用。经过这样一遍扫描后，最多安排了m个会场(m是最大重叠区间数)。因此所作的会场安排是最优的。上述算法所需的计算时间主要用于对2n个区间端点的排序，这需要 O(nlogn)计算时间。具体算法描述如下。public static int greedy(point x)int sum=0, curr=0, n=xength;M

33、ergeSort.mergeSort(x);for (int i=0; i<n;i+) if (xi.leftend() curr+;else curr-;/处理xi=xi+1的情况if ( i = n-1 II 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和

34、f中的2n个元素排序存入数组y1:2n中；空闲栈清空；d数组所有元素置初值 0;For i=1 to 2n doBeginIf元素yi原属于s thenIf空闲栈不空then取出栈顶场地 j; dj=dj+1; yi存入 xj, dj;If元素yi原属于f then设其相应的s存于xj,k中，将j存入空闲栈中；EndFor i= 1 to m doFor j=1 to dj doOutput xi,j;End习题5-6删数问题问题描述给定n位正整数a，去掉其中任意个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方

35、案。分析与解答：贪心策略：最近下降点优先。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)v=a.charAt(i+1); i+)a= a.Remove(i,1); k-;while (a.length()>1 && a.charAt(O)=' 0' ) a=a.Remove(0,

36、1);System.out.println(a);第六章回溯法习题6-1子集和问题子集和问题的一个实例。其中，是一个正整数的集合，sum是一个正整数。子集和问题判定是否存在A的一个子集A1，使得。试设计一个解子集和问题的回溯法。分析与解答：设计解子集和问题的回溯法如下。Algorithm subset-sumbeginFor j=1 to n doBeginsp=0; t=sum; i=j; finish=false;repeatif t>=ai thenbeginsp=sp+1 ； ssp=i; t=t-ai; if t=0 then i=n;end;i=i+1;while i>

37、n doif sp>1 thenbeginif t=0 then out; t=t+assp; i=ssp+1; sp=sp-1endelsebegin finish=true; i=1 enduntil finishendend习题6-2中国象棋的半个棋盘如图所示，马自左下角往右上角跳。规定只许向右跳，不许向左跳，计算所有的行走路线。Algorithm chessBegintop=0; y0=0; x0=0; di=1; r=0;push;repeatpop;while di<=4 dobeging=xO+xdi; h=yO+ydi;if (g=8) and (h=4) then outelse begin di=di+1 ； push; x0=g; y0=h; di=1 end enduntil emptyendalgorithm pushbegintop=top+1 ; sxtop=x0; sytop=y0; dtop=di;end algorithm popbeginx0=sxtop; y0=sytop; di =dtop; top=top 1;end习题6-3.在n个连成排的方格内填入R或B,但相邻连个方格内不能都填R。计算所有可能的填法。R B B R BAlgorithm Red-Black;BeginFor i=1 t