算法设计与分析习题与试验题

《算法设计与分析习题与试验题》由会员分享，可在线阅读，更多相关《算法设计与分析习题与试验题（31页珍藏版）》请在装配图网上搜索。

1、算法设计与分析习题第一章 引 论习题 1-1 写一个通用方法用于判定给定数组是否已排好序。 解答：Algorithm compare(a,n)BeginJ=1;While (jn and aj=aj+1) do j=j+1;If j=n then return trueElseWhile (j=aj+1) do j=j+1;If j=n then return true else return false end if End ifend习题 1-2 写一个算法交换两个变量的值不使用第三个变量。 解答： x=x+y; y=x-y; x=x-y;习题1-3已知m,n为自然数，其上限为k (由键盘

2、输入，1=k=109)，找出满 足条件 (n2-mn-m2)2=1 且使 n2+m2 达到最大的 m、 n。解答： m:=k; flag :=0; repeat n:=m; repeat l:=n*n-m*n-m*n ; if (l*l =1) then flag: = 1 else n:=n -1 ; until ( flag = 1 ) or (n=0) if n=0 then m:=m-1 until (flag=1) or (m=0);第二章 基础知识习题2-1求下列函数的渐进表达式：3n2+10n; n2/10+2n; 21+1/n; logn3; 10 Iog3n。解答：3n 2+

3、10 n=O (n2), n2/10+2n=O (2n), 21+1/n=O (1),logn3=O (log n), 10 Iog3n=O (n)。习题2-2 说明0(1)和0(2)的区别。习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n2 ,log n,3n,20n,2, n2/3。2解答：照渐进阶从低到高的顺序为：n!、 3n、 4n2、卍、20n、logn、2习题2-4(1) 假设某算法在输入规模为n时的计算时间为T(n) = 3 2n。在某台计算机 上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为 第一台计算机的64倍，那么在这台新机器上用同一算法在 t秒

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

5、杂性分别为n，n2，n3和n!的各算法， 若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公 司的计算机在1小时内分别能解输入规模为多大的问题？解答：n =100n。2 2n =100n n =10n。n 3 =100n3 二 3 100n = 4.64n。n ! =100n! = n ： n log 100 = n 6.64。习题2-6对于下列各 组函数f(n)和g(n),确定f(n)=O(g(n)或 f (n) - (g(n)或 f (n) - (g(n)，并简述理由。(1) f (n) = log n ； g (n) = log n 5。(2) f (n) =log

6、 n 2;g( n) n。(3) f (n)二 n； g(n) = log2 n。(4) f (n) = nlog n n; g(n) = log n。(5) f (n) =10;g(n) = log 10。(6) f (n) =log2 n;g(n) =log n。(7) f (n)=2n;g( n)=100 n2。(8) f(n)=2n;g(n) = 3n。解答：(1) log n2 -)(log n 5)。(2) log n2 = 0( n)。(3) n -门(log 2 n)。(4) n log n n = log n)。(5) 10 - log 10)。(6) log 2 n 二 1

7、1 (log n)。(7) 2n (100n2)。(8) 2n =0(3n)。习题2-7证明：如果一个算法在平均情况下的计算时间复杂性为r(f(n),则该算法在最坏情况下所需的计算时间为1 (f (n)。证明：Tavg(N) =、P(I)T(N,I)1 In一、P(I)maxT(N,I )I.DnI Dn= T(N,I*r P(I)丨田N= T(N,I*)二 Tmax(N)因此，Tmax(N):=门仃 avg(N) 3(f( n)(f( n)。习题2-7求解下列递归方程：So=O-Sn=2Sn-1+2n-1解答:步骤：1应用零化子化为齐次方程,2解此齐次方程的特征方程，3由特征根构造一般解，4

8、再由初始条件确定待定系数，得到解为:Sn =( n-1)2n 1习题2-8求解下列递归方程：ho = 2hi =8hn=2n+1( n+1)=4hnJ -4hnd解第三章递归与分治策略习题3-1下面的7个算法都是解决二分搜索问题的算法。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算法的正确性证明public static int binarySearch1(int a,int x,int n) int left=0; int right =n-1;while (left amiddle) left = middle; else right = middl

9、e;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) left = middle; else right = middle;if ( x = aleft) return left ;else return -1;public static int binarySearch4(int a, int x, int n)

10、 if (n0 & x= a0) int left = 0; int right = n-1;while (left right ) int middle = (left + right )/2; if ( x 0 & x = a0 ) int left = 0; int right = n-1;while (left right ) int middle = ( left + right +1)/2; if ( x 0 & x= a0) int left = 0; int right = n-1;while ( left right) int middle = (left + right +

11、1)/2;if (x 0 & x=a0) int left = 0; int right = n-1;while ( left right) int middle = ( left + right + 1)/2; if ( x amiddle) right = middle; else left = middle;if ( x = aleft) retur n left;return -1;分析与解答：算法binarySearchl数组段左右游标left和right的调整不正确，导致陷入死 循环。算法binarySearch2数组段左右游标left和right的调整不正确，导致当x=an-1

12、时返回错误。算法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: n1是已排好序的数组。请改写二分搜索算法，使得当搜 索元素x不

13、在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置 j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。分析与解答：改写二分搜索算法如下：public static boolea n bin arySearch(i nt a, int x, int left, int right, i nt i nd)int middle;while ( left amiddle) left = middle + 1;else right = middle -1;in d0 = right; in d1=left;return false;返回的ind1是小于x的最大元素位置，ind0是大于

14、x的最小元素的位置。习题3-3 设a0: n-1是有n个元素的数组，k(1岂k乞n-1)是非负整数。试设计一个算法讲子数组aO:k1与ak: n1换位。要求算法在最坏情况下耗时为0(n),且只用到0(1)的辅助空间。分析与解答：算法：三次求反法Algorithmexcha nge(a, k, n);Beg inInverse(n,0,k-1); inverse(n,k,n-1)；inverse( n,O,n-1)End.Algorithminv erse(a, i, j);Beg inh=j _i +1一 2For k=0 to h-1 doBegi n x=ai+k; ai+k=aj-k;

15、aj-k= x end ; end习题3-4如果在合并排序算法的分割步中，讲数组 a0: n -1划分为氐n个 子数组，每个子数组中有O(、. n)个元素。然后递归地对分割后的子数组进行排序， 最后将所得到的心n个排好序的子数组合并成所要求的排好序的数组 a0: n-1。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。 分析与解答：实现上述策略的合并排序算法如下：public static void mergesort(i nt a, int left ,i nt right) if (left 1) for (int i=0; ij; i+) mergesort(a, left+

16、i*j,left+(i+1)*j-1); mergesort(a,left+i*j,right);mergeall(a,left,right);其中，算法mergeall合并.n个排好序的数组段。在最坏情况下，算法 mergeall 需要O(nlog n)时间。因此上述算法所需的计算时间 T(n)满足:0(1)nT(n) =厂厂InT(Jn)n a 1此递归式的解为：T (n) =O(nlog n)。习题3-5 设,S2,.Sk是整数集合，其中每个集合 乜(1叮岂k)中整数取值k范围是1n，且送冋=n，试设计一个算法，在O( n)时间内将Si,S2,Sk分别i 4排序。分析与解答：用桶排序或基

17、数排序算法思想可以实现整数集合排序。习题6设X0: n 一1和Y0: n1为两个数组，每个数组中还有n个已排好序的 数。试设计一个O(log n)时间的算法，找出X和Y的2n个数的中位数。分析与解答：(1)算法设计思想考虑稍一般的问题：设Xi1 : jj和Yi2 : j2是X和Y的排序好的子数组， 且长度相同，即j1 -h二j2 “2。找出这两个数组中2(h-j1 T)个数的中 位数。首先注意到，若Xi1H： Y j2，贝U中位数 median满足XhMm e d 芒创免。同理若 Xi1pYj2，则 Yj2兰 media Xi1。设m1 =(h jJ/2，m2 =仏 j2)/2，则m1 m2

18、=(ijJ/2 (i2 j2)/2 7 (h -iJ/2 i? j 讥)二h i2 (j1-iJ/2 厲“由于 j1 -i j2 -i2，故(j1 -h)/2 (j2 7)/2 二 j1 -h = j2 7。因此匕 m1 m2 = i1 i2 ji 二屛=i2 j i1 i2 j2 _ i2 = h j2。当 Xm1Ym2时，median = Xm1 = Ym2。当 Xlm ：Ym2】时，设 median 是 Xm1 : j1和 Y j2 : m2的中位数，则median = medianj。当Xmi Ym2】时，设media七是Xii：mi和Ym2 : j2的中位数，类似地有 median

19、二 median2。通过以上讨论，可以设计出找出两个子数组Xii : j和丫亚:j2的中位数media n的算法。(2)设在最坏情况下，算法所需的计算时间为 T (2n)。由算法中mi和m2的选取策略可知，在递归调用时，数组X和Y的大小都减少了一半。因此，T(2n)满足递归式:T(2 n)=丿01)T(n)+O(1)n ： c n _ c习题3-6解此递归方程可得：T(2n) =O(log n)Gray码是一个长度为2n的序列。序列中无相同元素，每个元素1位不同。用分治策略设计都是长度为n位的(0，1 )串，相邻元素恰好只有 个算法，对任意的n构造相应的Gray码。分析与解答：考察n =1,2

20、,3的简单情形n=101n=200011110n=3000001011010110111101100设n位Gray码序列为G(n)以相反顺序排列的序列为G *(n)。从上面的简单情形可以看出G(n)的构造规律：G(n 1) = 0G(n) 1G(n)注意到G(n)的最后一个n位串与G (n)的第1个n位串相同，可用数学归纳法证明G(n)的上述构造规律。由此规律容易设计构造G(n)的分治法如下。public static void Gray(i nt n)if ( n = 1) a1 = 0; a2 = 1; return; Gray( n-1);for ( int k = 1 0; i-) a

21、2*k-i+1=ai + k;上述算法中将门位(0，1)串看做是二进制整数，第i个串存储在ai中 完成计算之后，由out输出Gray码序列。public static void out(i nt n)int m=1 n;for (i nt i=1; i=m; i+) String str=Integer.toBinaryString(ai);int s=str.le ngth();for ( int j=0; jn-s; j+) System.out.print( 0”；System.out.println(Integer.toBinaryString(ai)+ ” ”)；System.out

22、.pri ntl n();第四章动态规划习题4-1设计一个O(n?)时间的算法，找出由n个数组成的序列的最长单调 递增子序列。分析与解答：用数组b0: n -1记录以ai,0 _ i ： n为结尾元素的最长递增子序列的长度。序列a的最长递增子序列的长度为maxbi。o_i:n易知，bi满足最优子结构性质，可以递归地定义为：b0 = 1,bi =max bk 1akkai据此将计算bi转化为i个规模更小的子问题按此思想设计的动态规划算法描述如下: public static int LISd yn a()int i, j, k;for ( i=1, b0=1; in;i+) for ( j=0,

23、 k=0; jvl; j+ ) if ( aj = ai & k bj ) k=bj; bi= k+1;return maxL( n);static int maxL(i nt n)int temp=0;for ( int i= 0; i temp) temp=bi; return temp;上述算法LISdyna按照递归式计算出b0: n 一1的值，然后由maxL计算出序 列a的最长递增子序列的长度。从算法LISdyna的二重循环容易看出，算法所需 的计算时间为0(n2)。习题4-2考虑下面的整数线性规划问题：nmax cixin 7Xi为非负整数，1M兰n aixbi =1试设计一个解此问

24、题的动态规划算法，并分析算法的计算复杂性。分析与解答：该问题是一般情况下的背包问题，具有最优子结构性质。设所给背包问题的子问题：imax CkXkk=1i akXk - j的最优值为m(i,j)，即m(i,j)是背包容量为j，可选择物品为1，2，i时背包问题的最优值。由背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下：；maxm(i 1, j),m(i, j aj+gj 兰 am(i, j)=丿Lm(i -1, j)0 兰 jym(0, j) =m(i,O); m(i, j) = 7j :：: 0。按此递归式计算出的m(n,b)为最优值。算法所需的计算时间为 O(nb)习题4-3

25、给定一个由n行数字组成的数字三角形如图 3-2所示。试设计个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。738810274445265数字三角形分析与解答： 记f(uj)为至ij元素的最大路径值，aj ：元素(i,j)之值。递归式：F(uij)=maxf(ui-i,j)+aij, f(ui-i,j+i)+aij(i=1,j=1,i)经过一次顺推，便可求出从顶至底n个数的n条路径(这n条路径为至底上n个数的n个最大总和的路径)，求出这n个总和的最大值，即为正确答案。数据结构：ai,j.val:三角形上的数字， ai,j.f:由(1，1)至该点的最大总和路径的总和值。typ

26、e no de=recordval, f: in teger;end;var a:array 1. maxn, 1.max n of no de; procedure fin dmax;begi na 1,1. f :=a1,1.val;for i:=2 to n dofor j:=1 to i do beg in ai,j. f:=-1;if (j1) 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.val;if (ji) an d(a i-1,j.f+ai,j.val ai,j.f)then ai,j. f

27、:=ai-1,j. f+ai,j. valend;max:=1;for i:=2 to n doif an,i. f an, max .f then max:=i;writeln (a n, max. f) end;第五章贪心算法习题5-1特殊的0-1背包问题若在0-1背包问题中，各物品依重量递增排列时，其价值恰好依递减序排列。对这个特殊的0-1背包问题，设计一个有效算法找出最优解，并说明算法的正确性。分析与解答：设所给的输入为 W 0,.0i . 0,1叮乞n。不妨设0 - -2. - -n。由题意知_；2 -_；n 0。由此可知 丄一1，1 乞n -1 贪心选择性质：当1 W时问题无解。当

28、.W时，存在0-1背包问题的一个最优解S 1,2,., n使得1 S。事实上，设 S 1,2,., n使0-1背包问题的一个最优解，且V S。对任意S，取S二S 一1 -i，则&满足贪心选择性质的最优解。习题5-2 Fibonacci序列的Huffman编码试证明：若n个字符的频率恰好是前n个Fibonacci数，用贪心法得到它们的Hufman编码树一定为一棵“偏斜树”。图哈夫曼编码树证明：n个字符的频率恰好是前n个Fib on acci数，则相应的哈夫曼编码树自底向上第iii个内结点中的数为V fk。用数学归纳法容易证明V fk：fi2。k 30k 30因fl = 1,f2=1,f3=2,可

29、知i = 1时，上述结论成立。i设对i+2上述结论成立，即有 7 fk2，因k卫ii -1fifi 2 fifk fi .1 - 7 fk，k吕k=1说明对i+3上述结论成立.该性质保证了频率恰好是前n个Fib on acci数的哈夫曼编码树具有“偏斜树”形状。习题5-3假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。分析与解答：设所给的n个活动为1, 2,，n,它们的开始时间和结束时间分别为si和fi,i =1 n，且 f1 ： f2:：f n。可以将n个活动1, 2,，n看作实直线上的n个半闭活动区间si, f i), i =1n。所讨论的问题

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

31、述算法所需的计算时间主要用于对2n个区间端点的排序，这需要 O(n log n)计算时间。具体算法描述如下。public static int greedy(po in t x)int sum=O, curr=O, n=x.len gth;MergeSort.mergeSort(x);for (i nt i=0; in ;i+) if (xi.leftend() curr+;else curr-;处理xi=xi+1的情况if ( i = n-1 II pareTo(xi+1)sum) sum=curr; return sum;习题5-4假设要在m个会场里安排一批活动，并希望使用尽可能多地安排活

32、动。设计 个有效的贪心算法进行安排。Algorithm greedy(s,f, m,n);Input s1: n, f1: n;Output x1:m, 1: n;Beg in对数组s和f中的2n个元素排序存入数组y1:2n中； 空闲栈清空；d数组所有元素置初值0；For i=1 to 2n doBegi nIf元素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

33、习题5-5删数问题问题描述给定n位正整数a，去掉其中任意k岂n个数字后，剩下的数字按原次序排列组成一个新的 正整数。对于给定的 n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小 的删数方案。分析与解答：贪心策略：最近下降点优先。public static void delek(String a)int i,m=a.length();if ( k= m) System.out.println(0); return;while (k0) for (i=0; (ia.le ngth()-1)&(a.charAt(i)1 & a.charAt(0)= a=a.Remove(0,1); S

34、ystem.out.pri ntl n( a);习题6-1子集和冋题子集和问题的一个实例:A, sum .。其中，A = 知a2,，an是一个正整数的集合，sum是一个正整数。子集和问题判定是否存在A的一个子集A1,使得a = sum。试设计一个解子集和问题的回溯法。分析与解答：设计解子集和问题的回溯法如下。Algorithm subset-sum beginFor j=1 to n doBegi nsp=0; t=sum; i=j; fini sh=false; repeatif t=ai the nbeginsp=sp+1 ； ssp=i; t=t-ai; if t=0 then i=n;

35、en d;i=i+1;while in doif sp1 the nbeginif t=0 the n out; t=t+assp; i=ssp+1; sp=sp-1endelsebegi n fini sh=true; i=1 end un til finishend end习题6-2中国象棋的半个棋盘如图所示，马自左下角往右上角跳。规定只许向右跳，不许 向左跳，计算所有的行走路线。Algorithm chessBegintop=0; y0=0; x0=0; di=1; r=0;push;repeatpop;while di2 then 回溯 begin bt=0 ; t=t-1 ; end

36、 else beg inif bt=2 then at= B else if at-1= Rthen t=t-1 else at= R;if t=n the n output a else t=t+1 endun til t=0第七章分支限界法习题7-1.试写出采用分支界限法求解下面的0、1背包问题实例的过程：物品的个数n=4,背包的重量m=15,各个物品的重量依次为 2，4，6，9，各个物品的价 值依次为10，10，12，18。对于第i层上的每个节点 X，其价值的上界定义为有贪心法所求出的一般背包问题的解 Su(X)，下界为S|(X)为Su(X)中减去最后放入背包的Xi* 1的物品的相应部分

37、价值。解答：(X1X2X3X4) wx,px U,L0, 0(00?)0, 08(000?)0, 01 0, 0 /(?)38,322,1032,22.38,32n=4, m=15 w=2,4,6,9 p=10,10,12,184, 106, 2075(01?)2,106,206, 129) (001?)4,1010(010?)(011?)10,2236,22 (10?)2,1012(100?)8,22(101?)(110?)38,32 /(11?)12,32153,3838,32(111?)0,09,186,1215,304,1013,28X10,22X19,402,1011,288,221

38、7,406,2015,382?_12,32X21,50一 20 3121(0000(0001X0010)(0011)(0100)(0101)(0110) (0111)(1000)(1001)(1010)(1011)(110(520,20(1101)38,381110) (1111)习题7-2.写出用分支界限法求解下面的重排九宫问题的算法。81263754开始状态12384765目标状态解答：我们对九宫中的位置做如下的编号:位置编号123894765则初始状态用向量 So=( 8，1，2，3，4，5，7, 0，6)表示，目标状态用 S*=( 1，2，3, 4， 5， 6， 7， 8， 0)表示。

39、我们使用一个堆heap,将启发函数值 H(x)最小的状态x置于堆顶优先搜索。H(x)定义如 下：H(x)=h i(x)+3h 2(x)其中，hi(x)为状态x与目标状态不相同的数字的数目，h2(x)=v N(y)，y这里，0,1y和其后继的相对位置不变N(y)二 1,2,y处于中心其它算法：AlgorithmLC(So, S )In put:初始状态向量 S0 ,目标状态S ；Output:达到目标状态的状态序列；Beg inS=S。；if S 目标状态 S then Output(S 及其所有前驱)else add (S, heap) while heap 非空 do取出堆heap顶部状态E

40、 ;for E的每个可能的后继状态x doif x为目标状态 S then Output(x及其所有前驱);returnelse计算x的启发函数H(x);add(x, heap)en difen dforen dwhileend第八章NP完全问题习题8-1证明析取范式的可满足性问题属于P类。分析与解答：析取范式是由因子之和的和式给出的。这里因子是指变量x或x，每个因子之积称为个析取式。例如x1x2+x2x3+ x1 X2X3就是个析取范式。m_设给定一个析取范式- -fi(x1,x2,.xn)，其中fi(x1,x2,.xn)是变量 为或X，j=1ni 1的一个析取范式，i=1m。：是可满足的，

41、当且仅当存在i, 1二i二m，使fi(X1, X2,.xn)是可满足的。如果有一个多项式时间算法能判断任何一个析取式的可满足性，则用该算法对:的每个析取项逐一判断就可以在多项式时间内确定析取范式:的可满足性。因此，问题可简化为找一个确定析取式可满足性的多项式时间算法。设析取范式 f(X1, X2,.Xn)=-:九沢-汀，其中xj, xj |1 一 j _ n。可以设计在 0(n+k)时间内确定析取式 f (X1, X2,.Xn)v 2.J k可满足性的算法。因此，析取范式的可满足性问题是多项式时间可解的，即它属于P类。第九章近似算法习题9-1瓶颈旅行售货员冋题瓶颈旅行售货员问题是要找出图G=(

42、V,E)的一个哈密顿回路，且使回路中最长边的长度最小。若费用函数满足三角不等式，给出解此问题的性能比为3的近似算法。(提示：递归地证明，可以通过对 G的最小生成树进行完全遍历并跳过某些项点，但不能跳过多于2个连续的中间顶点，以此方式访问最小生成树中每个顶点恰好一次。)分析与解答：解瓶颈旅行售货员问题的性能比为3的近似算法描述如下：Void approxTSP(Graph G) 选择任一顶点r V ； 找出G的一棵以r为根的最小瓶颈生成树 T ； 选取T的一条边(p,q)作为哈密顿回路 H的一条边； 遍历树T,跳过不多于两个连续的重复顶点，递归构造H的其他边; 将所得到的哈密顿回路H作为计算结果

43、返回.习题9-2可满足问题的近似算法 问题描述设是一个含有n个变量和m个合取项的合取范式。关于:的最大可满足性问题要求确定的最多个数的合取式使这些合取式可同时满足。设k是的所有合取式中因子个1数的最小值。证明下面的解最大可满足性问题的近似算法mSAT的相对误差为。k + 1Set mSAT(a)/ xi, 1 H： n ,是a中n个变量；Ci ，1 m，是的m个合取项。c1= I;left= Ci | 1 _ i _ m；lit=刃，为|1乞i巴n ;while(lit含有在left的合取式中出现的因子)设y是lit的在left的合取式中出现次数最多的因子; 设r是left中含有因子y的所有合

44、取式的集合；c仁 c1J r;left=left-r;lit=lit-y, y;return(c1);第十章随机算法习题10-1模拟正态分布随机变量1(x-a)2在实际应用中，常需要模拟服从正态分布的随机变量，其密度函数为 e云厂，其中，2 二a为均值，二为标准差。如果s和t是(-1，1)中均匀分布的随机变量，且s2 t2 1 ，令p = s t2, q= (-21 np)/p,u = sq, v=tq，则u和v是服从标准正态分布(a =0,-1)的两个互相独立的随机变量。(1) 利用上述事实，设计一个模拟标准正态分布随机变量的算法。(2) 将上述算法扩展到一般的正态分布。 分析与解答：(1)

45、 模拟标准正态分布随机变量的算法如下。public double Norm()double s,t,p,q;while (true) s=2*fRa ndom()-1;t=2*fRa ndom()-1;p=s*s+t*t; if (p1) fact(i);if (ni) fact(n/i)；算法设计与分析实验题实验题 1最大间隙问题：给定 n 个数 x1 , x2 ,., x n ，求这 n 个数在实轴上相邻 2 个数之 间的最大差值。假设对任何实数的下取整方法耗时为 O(1) ，设计解最大间隙问题 的线性时间算法。分析与解答： 用鸽舍原理设计最大间隙问题的线性时间算法如下。Public st

46、atic double maxgap(int n,double x)double minx=xmini(n,x), maxx=xmaxi(n,x);/用 n-2 个等间距点分割区间 minx,maxx/产生 n-1 个桶，每个桶 i 中用 highi 和 lowi 分别存储分配给桶 i 的数中的 最大数和最小数int count=new intn+1;double low=new doublen+1;double high=new doublen+1;/桶初始化for (int i=1, i=n-1; i+) counti=0; lowi=maxx; highi=minx;/将 n 个数置于

47、n-1 个桶中for (int i=1; i=n; i+) int bucket=(int)(n-1)*(xi-minx)/(maxx-minx)+1; countbucket+;if (xihighbucket) highbucket=xi;/此时，除了 maxx 和 minx 外的 n-2 个数被置于 n-1 个桶中/由鸽舍原理即知，至少有一个桶式空的/这意味着最大间隙不会出现在同一桶中的两个数之间/对每一个桶作一次线性扫描即可找出最大间隙double tmp=0, left=high1;for (i nt i=2; i0) double thisgap=lowi-left;if (thi

48、sgaptmp) tmp=thisgap; left=highi;return tmp;其中，mini和maxi分别计算数组中最小元素和最大元素的下标实验题2设A和B是两个字符串。要用最少的字符操作将字符串 A转换为字符串B。 这里所说的字符操作包括：(1) 删除一个字符；(2) 插入一个字符；(3) 将一个字符改为另一个字符；对任给的两个字符串A和B，计定义 Di, jHd(A1:i, B1: j)a =ba b将字符串A变换为字符串B所用的最少字符操作数称为字符串 A到B的编辑距离，记为d(A, B)。试设计一个有效算法算出它们的编辑距离d(A, B)。分析与解答：设所给的两个字符串为A1

49、: m和B1 : n单字符a，b间的距离定义为：0 d(a,b)=考察从字符串A1:i到字符串B1: j的变换。可分以下几种情况来讨论(1) 字符Ai改为字符Bi;需要d(Ai, Bj)次操作。(2) 删除字符Hi;需要1次操作。(3) 插入字符Bi;需要1次操作。因此Di j可递归地计算如下Di j二 minDi -1 j -1 d(Ai, Bj), Di 1j 1,Di j -1 1Di j的初始值为： DiO =i, D0 j二 j,i = 0 m, j = 0 n。据此容易设计出计算dA, B的动态规划算法如下：public static int dist()int m=a.len g

50、th();int n=b.len gth();in t d=new in t n+1;for (i nt i = 1; i = n; i+) di = i;for (i nt i = 1; i = m; i+) int y=i-1;for ( int j=1; j1?dj-1:i;int del= a.charAt (i -1) = b.charAt( j -1)?0:1;dj =mi n( x+ del, y+1, z+1);Retur n dn;实验题3套汇问题问题描述套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如，假定 1美元可以买0.7英镑，1英镑可

51、以买9.5法郎，且1法郎可以买到0.16 美元，通过货币兑换，一个商人可以从1美元开始买入，得到 0.7X 9.5X 0.16=1.064美元，从而获得6.4%的利润。给定n种货币c1,c2,的有关兑换率，试设计一个有效算法，用以确定是否存在套汇的可能性。分析与解答：通过计算兑换率矩阵的传递闭包进行判断。算法主体如下。while (true) n=keyboard.readl nt();if (n=0) break;for (i=0; in; i+) namei=keyboard.readString();for (i=0; in; i+)for (j=0; j n; j+) rij=0.0;edges=keyboard.readInt();for