《算法设计与分析》习题
第一章 引 论
习题1-1 写一个通用方法用于判定给定数组是否已排好序。 解答：
Algorithm compare(a,n) Begin J=1;
While (j While (j If j=n then return true else return false end if End if end 习题1-2 写一个算法交换两个变量的值不使用第三个变量。 解答： x=x+y; y=x-y; x=x-y; 习题1-3 已知m,n为自然数，其上限为k（由键盘输入，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 log3n 。 解答： 3n2+10n=O（n2）， n2/10+2n=O（2n）， 21+1/n=O（1）， logn3=O（log n），10 log3n=O（n）。 习题2-2 说明O(1)和 O(2)的区别。 习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!， 4n,logn,3,20n,2,n2n2/3。 n 2解答：照渐进阶从低到高的顺序为：n!、 3、 4n、n3、20n、logn、2 习题2-4 2（1） 假设某算法在输入规模为n时的计算时间为T(n)?3?2n。在某台计算机 上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？ （2） 若上述算法的计算时间改进为T(n)?n2，其余条件不变，则在新机器上用 t秒时间能解输入规模多大的问题？ （3） 若上述算法的计算时间进一步改进为T(n)?8,其余条件不变，那么在新机 器上用t秒时间能解输入规模多大的问题？ 解答： （1） 设新机器用同一算法在t秒内能解输入规模为n1的问题。因此有 t?3?2?3?2nn1/64，解得n1?n?6。 （2） n12?64n2??n1?8n。 （3） 由于T(n)?常数，因此算法可解任意规模的问题。 习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n2，n3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？ 解答： n??100n。 n?2?100n2??n??10n。 n?3?100n3??3100n?4.64n。 n?!?100n!??n??n?log100?n?6.64。 习题2-6对于下列各组函数f(n)和g(n)，f(n)??(g(n))或f(n)??(g(n))，并简述理由。 （1）f(n)?logn2;g(n)?logn?5。 （2）f(n)?logn2;g(n)?n。 （3）f(n)?n;g(n)?log2n。 （4）f(n)?nlogn?n;g(n)?logn。 （5）f(n)?10;g(n)?log10。 （6）f(n)?log2n;g(n)?logn。 （7）f(n)?2n;g(n)?100n2。 （8）f(n)?2n;g(n)?3n。 解答： （1）logn2??(logn?5)。 （2）logn2?O(n)。 （3）n??(log2n)。 （4）nlogn?n??(logn)。 （5）10??(log10)。 （6）log2n??(logn)。 （7）2n??(100n2)。 确定f(n)?O(g(n))或 （8）2n?O(3n)。 习题2-7 证明：如果一个算法在平均情况下的计算时间复杂性为?(f(n))，则该算法在最坏情况下所需的计算时间为?(f(n))。 证明： Tavg(N)???P(I)T(N,I)I?DN?I?DNP(I)maxT(N,I?)I??DN ?T(N,I)**?P(I)I?DN?T(N,I)?Tmax(N)因此，Tmax(N)??(Tavg(N))??(?(f(n)))??(f(n))。 习题2-7 求解下列递归方程: s0=0 sn=2sn-1+2n -1 解答： 步骤: 1应用零化子化为齐次方程， 2解此齐次方程的特征方程， 3由特征根构造一般解， 4再由初始条件确定待定系数，得到解为： sn?(n?1)2?1n 习题2-8 求解下列递归方程: h0?2??h1?8 ??h?4h?4hn?1n?2?n解 hn=2n+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 == a[middle]) return middle; if ( x> a[middle]) 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 < a[middle]) right = middle; else left = middle; } if (x == a[left]) return left; else return -1 } public 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>= a[middle]) left = middle; else right = middle; } if ( x == a[left]) return left ; else return -1; } public static int binarySearch4(int []a, int x, int n) { if (n>0 && x>= a[0]) { int left = 0; int right = n-1; while (left < right ) { int middle = (left + right )/2; if ( x < a[middle]) right = middle -1 ; else left = middle; } if ( x == a[left]) return left; } return -1; } public static int binarySearch5(int []a, int x, int n) { if ( n>0 && x >= a[0] ) { int left = 0; int right = n-1; while (left < right ) { int middle = ( left + right +1)/2; if ( x < a[middle]) right = middle -1; else left = middle ; } if ( x == a[left]) return left; } return -1; } public static int binarySearch6(int []a, int x, int n) { if ( n>0 && x>= a[0]) { int left = 0; int right = n-1; while ( left < right) { int middle = (left + right +1)/2; if (x < a[middle]) right = middle – 1; else left = middle + 1; } if ( x == a[left]) return left ; } return -1; } public static int binarySearch7(int []a, int x, int n) { if ( n>0 && x>=a[0]) { int left = 0; int right = n-1; while ( left < right) { int middle = ( left + right + 1)/2; if ( x < a[middle]) right = middle; else left = middle; } if ( x == a[left]) return left; } return -1; } 分析与解答： 算法binarySearch1数组段左右游标left和right的调整不正确，导致陷入死循环。 算法binarySearch2数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。 算法binarySearch3数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。 算法binarySearch4数组段左右游标left和right的调整不正确，导致陷入死循环。 算法binarySearch5正确，且当数组中有重复元素时，返回满足条件的最右元素。 算法binarySearch6数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。 算法binarySearch7数组段左右游标left和right的调整不正确，导致当x=a[n-1]时陷入死循环。 习题3-2 设a[0:n?1]是已排好序的数组。请改写二分搜索算法，使得当搜索元素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 == a[middle]) { ind[0]=ind[1]=middle; return true;} if (x > a[middle]) left = middle + 1; else right = middle -1; } ind[0] = right; ind[1]=left; return false; } 返回的ind[1]是小于x的最大元素位置，ind[0]是大于x的最小元素的位置。 习题3-3 设a[0:n?1]是有n个元素的数组，k(1?k?n?1)是非负整数。试设 计一个算法讲子数组a[0:k?1]与a[k:n?1]换位。要求算法在最坏情况下耗时为 O(n)，且只用到O(1)的辅助空间。 分析与解答： 算法： 三次求反法 Algorithm exchange(a, k, n); Begin Inverse(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=a[i+k]; a[i+k]=a[j-k]; a[j-k]= x end ; end 习题3-4 如果在合并排序算法的分割步中，讲数组a[0:n?1]划分为?n?个子数组，每个子数组中有O(n)个元素。然后递归地对分割后的子数组进行排序，最后将所得到的 ?n?个排好序的子数组合并成所要求的排好序的数组 a[0:n?1]。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。 分析与解答： 实现上述策略的合并排序算法如下： 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 其中，算法mergeall合并n个排好序的数组段。在最坏情况下，算法mergeall 需要O(nlogn)时间。因此上述算法所需的计算时间T(n)满足： ?O(1)T(n)???nT(n)n?1n?1 此递归式的解为：T(n)?O(nlogn)。 习题3-5 设S1,S2,...Sk是整数集合，其中每个集合Si(1?i?k)中整数取值 k范围是1~n，且?Si?n，试设计一个算法，在O(n)时间内将S1,S2,...Sk分别 i?1排序。 分析与解答： 用桶排序或基数排序算法思想可以实现整数集合排序。 习题6 设X[0:n?1]和Y[0:n?1]为两个数组，每个数组中还有n个已排好序的数。试设计一个O(logn)时间的算法，找出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[i1]?medi?aY[nj2]。同理若X[i1]?Y[j2]，则Y[j2]?median?X[i1]。 设 m1?(i1?j1)/2， m2?(i2?j2)/2， 则 m1?m2?(i1?j1)/2?(i2?j2)/2?i1?(j1?i1)/2?i2?(j2?i2)?i1?i2?(j1?i1)/2?(j2?i2)/2由于j1?i1?j2?i2，故(j1?i1)/2?(j2?i2)/2?j1?i1?j2?i2。 因此m1?m2?i1?i2?j1?i1?i2?j1?i1?i2?j2?i2?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]?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)满足递归式： ?O(1)T(2n)???T(n)?O(1)n?cn?c 解此递归方程可得：T(2n)?O(logn)。 习题3-6 Gray码是一个长度为2n的序列。序列中无相同元素，每个元素都是长度为n位的（0，1）串，相邻元素恰好只有1位不同。用分治策略设计一个算法，对任意的n构造相应的Gray码。 分析与解答： 考察n?1,2,3的简单情形。 n=1 0 n=2 00 11 n=3 000 110 001 111 011 101 010 100 01 10 1 设n位Gray码序列为G(n)以相反顺序排列的序列为G?1(n)。从上面的简单情形可以看出G(n)的构造规律：G(n?1)?0G(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) { a[1] = 0; a[2] = 1; return; } Gray(n-1); for ( int k = 1<< ( n - 1), i = k; i > 0; i--) a[2*k-i+1]=a[i] + k; } 上述算法中将n位（0，1）串看做是二进制整数，第i个串存储在a[i]中。 完成计算之后，由out输出Gray码序列。 public static void out(int n) { int m=1< 第四章 动态规划 习题4-1 设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。 分析与解答： 用数组b[0:n?1]记录以a[i],0?i?n为结尾元素的最长递增子序列的长度。序列a的最长递增子序列的长度为max{b[i]}。易知，b[i]满足最优子结构性 0?i?n质，可以递归地定义为： b[0]?1,b[i]?max{b[k]}?1 0?k?ia[k]?a[i]据此将计算b[i]转化为i个规模更小的子问题。 按此思想设计的动态规划算法描述如下： public static int LISdyna() { int i, j, k; for ( i=1, b[0]=1; i static int maxL(int n) { int temp=0; for ( int i= 0; i 上述算法LISdyna按照递归式计算出b[0:n?1]的值，然后由maxL计算出序列a的最长递增子序列的长度。从算法LISdyna的二重循环容易看出，算法所需的计算时间为O(n2)。 习题4-2 考虑下面的整数线性规划问题： nmaxn?ci?1iixi xi为非负整数，1?i?n ?ai?1xi?b试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。 分析与解答： 该问题是一般情况下的背包问题，具有最优子结构性质。 设所给背包问题的子问题： imaxi?ck?1kkxk ?ak?1xk?j的最优值为m(i,j)，即m(i,j)是背包容量为j，可选择物品为1，2，…，i时背包问题的最优值。由背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下： ?max{m(i?1,j),m(i,j?ai)?ci}m(i,j)???m(i?1,j)j?ai0?j?ai m(0,j)?m(i,0);m(i,j)???,j?0。 按此递归式计算出的m(n,b)为最优值。算法所需的计算时间为O(nb)。 习题4-3 给定一个由n行数字组成的数字三角形如图3-2所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 数字三角形 分析与解答： 记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）至该点的最大总和路径的总和值。 type node=record val, f: integer; end; var a:array [1.. maxn, 1..maxn] of node; procedure findmax; begin a [1,1]. f :=a[1,1].val; for i:=2 to n do for j:=1 to i do begin a[i,j]. f:=-1; if (j<>1) and (a [i-1,j-1].f+a[i,j].val > a [i,j].f) then a[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) then a[i,j]. f:=a[i-1,j]. f+a[i,j]. val end; max:=1; for i:=2 to n do if a[n,i]. f> a[n, max] .f then max:=i; writeln (a [n, max]. f) end; 第五章 贪心算法 习题5-1 特殊的0-1背包问题 若在0-1背包问题中，各物品依重量递增排列时，其价值恰好依递减序排列。对这个特殊的0-1背包问题，设计一个有效算法找出最优解，并说明算法的正确性。 分析与解答： 设所给的输入为W?0,?i?0,?i?0,1?i?n。不妨设0??1??2?...??n。由题意知?1??2?...??n?0。由此可知 ?i?i??i?1?i?1，1?i?n?1 贪心选择性质： 当?1?W时问题无解。 当?1?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-2 Fibonacci序列的Huffman编码 试证明：若n个字符的频率恰好是前n个Fibonacci数，用贪心法得到它们的Huffman编码树一定为一棵“偏斜树”。 分析与解答： 频率恰好是前8个Fibonacci数的哈夫曼编码树如图所示。 2 1 1 4 2 7 12 5 3 33 54 21 20 8 13 图 哈夫曼编码树 证明：n个字符的频率恰好是前n个Fibonacci数，则相应的哈夫曼编码树自底向上第 iii个内结点中的数为?fk。用数学归纳法容易证明?fk?fi?2。 k?0k?0因f1=1,f2=1,f3=2,可知i=1时，上述结论成立。 i设对i+2上述结论成立，即有?fk?fi?2， 因 k?0ii?1fi?3?fi?2?fi?1??k?1fk?fi?1??k?1fk， 说明对i+3上述结论成立. 该性质保证了频率恰好是前n个Fibonacci数的哈夫曼编码树具有“偏斜树”形状。 习题5-3 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。 分析与解答： 设所给的n个活动为1，2，…，n，它们的开始时间和结束时间分别为s[i]和f[i]， i?1~n，且f[1]?f[2]?...?f[n]。 可以将n个活动1，2，…，n看作实直线上的n个半闭活动区间[s[i],f[i]),i?1~n。所讨论的问题实际上是求这n个半闭区间的最大重叠数。因为重叠的活动区间所相应的活动是互不相容的。若这n个活动区间的最大重叠数为m，则这m个重叠区间所对应的活动互不相容，因此至少安排m个会场来容纳这m个活动。 为了有效地对这n个活动进行安排，首先将n个活动区间的2n个端点排序。然后，用扫描算法，从左到右扫描整个实直线。在每个事件点处（即活动的开始时刻或结束时刻）作会场安排。当遇到一个开始时刻s[i]，就将活动i安排在一个空闲的会场中。遇到一个结束时候f[i]，就将活动i占用的会场释放到空闲会场栈中，以备使用。经过这样一遍扫描后，最多安排了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 习题5-4 假设要在m个会场里安排一批活动，并希望使用尽可能多地安排活动。设计一个有效的贪心算法进行安排。 Algorithm greedy(s,f,m,n); Input s[1:n], f[1:n]; Output x[1:m, 1:n]; Begin 对数组s和f中的2n个元素排序存入数组y[1:2n]中； 空闲栈清空；d数组所有元素置初值0； For i=1 to 2n do 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 For i= 1 to m do For j=1 to d[j] do Output x[i,j]; End 习题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 (k>0) { } for (i=0; (i while (a.length()>1 && a.charAt(0)==?0?) a=a.Remove(0,1); System.out.println(a); 第六章 回溯法 习题6-1 子集和问题 子集和问题的一个实例?A,sum?。其中，A?{a1,a2,...,an}是一个正整数的集合，sum是一个正整数。子集和问题判定是否存在A的一个子集A1，使得?a?sum。 a?A1试设计一个解子集和问题的回溯法。 分析与解答： 设计解子集和问题的回溯法如下。 Algorithm subset-sum begin For j=1 to n do Begin sp=0; t=sum; i=j; finish=false; repeat if t>=a[i] then begin sp=sp+1；s[sp]=i; t=t-a[i]; if t=0 then i=n; end; i=i+1; while i>n do if sp>1 then begin if t=0 then out; t=t+a[s[sp]]; i=s[sp]+1; sp=sp-1 end else begin finish=true; i=1 end until finish end end 习题6-2 中国象棋的半个棋盘如图所示，马自左下角往右上角跳。规定只许向右跳，不许向左跳，计算所有的行走路线。 Algorithm chess Begin top=0; y0=0; x0=0; di=1; r=0; push; repeat pop; while di<=4 do begin g=x0+x[di]; h=y0+y[di]; if (g=8) and (h=4) then out else begin di=di+1；push; x0=g; y0=h; di=1 end end until empty end algorithm push begin top=top+1；sx[top]=x0; sy[top]=y0; d[top]=di; end algorithm pop begin x0=sx[top]; y0=sy[top]; di =d[top]; top=top－1； end 习题6-3. 在n个连成排的方格内填入R或B，但相邻连个方格内不能都填R。计算所有可能的填法。 R Algorithm Red-Black; Begin For i=1 to n do b[i]=0; T=1; Repeat b[t]=b[t]+1 ; if b[t]>2 then {回溯} begin b[t]=0 ; t=t-1 ; end else begin if b[t]=2 then a[t]= ?B? else if a[t-1]=?R? then t=t-1 else a[t]=‘R?; if t=n then output a else t=t+1 end until t=0 B B R B 第七章 分支限界法 习题7-1. 试写出采用分支界限法求解下面的0、1背包问题实例的过程： 物品的个数n=4, 背包的重量m=15, 各个物品的重量依次为2，4，6，9，各个物品的价值依次为10，10，12，18。 对于第i层上的每个节点x，其价值的上界定义为有贪心法所求出的一般背包问题的解Su(x)，下界为Sl(x)为Su(x)中减去最后放入背包的xi≠1的物品的相应部分价值。 解答： (x1x2x3x4){wx,px}[U,L]{0, 0}2{0, 0}4(00??){0, 0}{6, 12}8(000?)9(001?)[32,22](0???){4, 10}5(01??){4,10}{10,22}10(010?)11(011?){2,10}6[36,22](10??){2,10}{8,22}12(100?)13(101?){6,20}14[38,38](110?)★{15,38}29{0, 0}1[38,32](????){2,10}3[38,32](1???)n=4, m=15w={2,4,6,9}p={10,10,12,18}{6, 20}7(11??)[38,32]{12,32}15[38,32](111?){12,32}{21,50}2031{0,0}{9,18}{6,12}{15,30}{4,10}{13,28}{10,22}{19,40}{2,10}{11,28}{8,22}{17,40}{6,20}16171819202122232425262728[20,20][38,38](0000)(0001)(0010)(0011)(0100)(0101)(0110)(0111)(1000)(1001)(1010)(1011)(1100)(1101)(1110)(1111) 习题7-2. 写出用分支界限法求解下面的重排九宫问题的算法。 开始状态 目标状态 8 7 解答： 我们对九宫中的位置做如下的编号： 位置编号 1 8 2 9 3 4 1 6 5 2 3 4 1 8 7 2 6 3 4 5 7 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)?这里， 算法： ?0, y和其后继的相对位置不变?N(y)??1, y处于中心?2, 其它??N(y) ， y?x Algorithm LC(S0, S*) * Input: 初始状态向量S0 , 目标状态S； Output: 达到目标状态的状态序列； Begin S=S0; if S目标状态S* then Output(S及其所有前驱) else add (S, heap) while heap非空 do 取出堆heap顶部状态E ； for E 的每个可能的后继状态x do * if x为目标状态S then Output(x及其所有前驱); return else 计算x的启发函数H(x); add(x, heap) endif endfor endwhile end 第八章 NP完全问题 习题8-1 证明析取范式的可满足性问题属于P类。 分析与解答： ? 析取范式?是由因子之和的和式给出的。这里因子是指变量x或x，每个因子之积称为 ??一个析取式。例如 x1x2+x2x3+x1x2x3就是一个析取范式。 m? 设给定一个析取范式???i?1fi(x1,x2,...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,xj|1?j?n}。 可以设计在O(n+k)时间内确定析取式f(x1,x2,...xn)=?1?2...?k可满足性的算法。因此，析取范式的可满足性问题是多项式时间可解的，即它属于P类。 ?第九章 近似算法 习题9-1 瓶颈旅行售货员问题 瓶颈旅行售货员问题是要找出图G=(V,E)的一个哈密顿回路，且使回路中最长边的长度最小。若费用函数满足三角不等式，给出解此问题的性能比为3的近似算法。（提示：递归地证明，可以通过对G的最小生成树进行完全遍历并跳过某些项点，但不能跳过多于2个连续的中间顶点，以此方式访问最小生成树中每个顶点恰好一次。） 分析与解答： 解瓶颈旅行售货员问题的性能比为3的近似算法描述如下： Void approxTSP(Graph G) { ① 选择任一顶点 r?V； ② 找出G的一棵以r为根的最小瓶颈生成树T； ③ 选取 T的一条边（p,q）作为哈密顿回路H的一条边； ④ 遍历树T，跳过不多于两个连续的重复顶点，递归构造H的其他边； ⑤ 将所得到的哈密顿回路H作为计算结果返回. } 习题9-2 可满足问题的近似算法 问题描述 设?是一个含有n个变量和m个合取项的合取范式。关于?的最大可满足性问题要求确定?的最多个数的合取式使这些合取式可同时满足。设k是?的所有合取式中因子个数的最小值。证明下面的解最大可满足性问题的近似算法 mSAT的相对误差为 1k?1。 Set mSAT(a) {// xi, 1?i?n,是a 中n个变量；Ci ，1?i?m，是?的m个合取项。 c1= ?; left={ Ci |1?i?m}; ? lit={xi,xi|1?i?n}; while(lit含有在left的合取式中出现的因子){ 设y是lit的在left的合取式中出现次数最多的因子； 设r是left中含有因子y的所有合取式的集合； c1= c1 ?r; left=left-r; ? lit=lit-{y, y}; } return(c1); } 第十章 随机算法 习题10-1 模拟正态分布随机变量 在实际应用中，常需要模拟服从正态分布的随机变量，其密度函数为 1?(x?a)2?22?a为均值，?为标准差。 2?e，其中， 如果s和t是（-1，1）中均匀分布的随机变量，且s?t?1，令 22p?s?t,22q?(?2lnp)/p,u?sq,v?tq，则u和v是服从标准正态分布 (a?0,??1)的两个互相独立的随机变量。 （1） 利用上述事实，设计一个模拟标准正态分布随机变量的算法。 （2） 将上述算法扩展到一般的正态分布。 分析与解答： (1) 模拟标准正态分布随机变量的算法如下。 public double Norm() { } (2) 扩展到一般的正态分布的算法如下。 public double Norm(double a,double b) { double x=Norm(); } return a+b*x; double s,t,p,q; while (true) { s=2*fRandom()-1; t=2*fRandom()-1; p=s*s+t*t; if (p<1) break; } q=Math.sqrt((-2*Math.log(p))/p); return s*q; 习题10-2 整数因子分解算法 假设已有一个算法Prime(n)可用于测试整数n是否为一素数。另外还有一个算法Split(n)可实现对合数n的因子分割。试利用这两个算法设计一个对给定整数n进行因子分解的算法。 分析与解答： 因子分解算法如下。 static void fact(int n) { } if (prime(n)) {output(n); return;} int i=split(n); if (i>1) fact(i); if (n>i) fact(n/i)； 《算法设计与分析》实验题 实验题1 最大间隙问题：给定n个数x1,x2,...,xn，求这n个数在实轴上相邻2个数之间的最大差值。假设对任何实数的下取整方法耗时为O(1)，设计解最大间隙问题的线性时间算法。 分析与解答： 用鸽舍原理设计最大间隙问题的线性时间算法如下。 Public static double maxgap(int n,double []x) { double minx=x[mini(n,x)], maxx=x[maxi(n,x)]; //用n-2个等间距点分割区间[minx,maxx] //产生n-1个桶，每个桶i中用high[i]和low[i]分别存储分配给桶i的数中的最大数和最小数 int []count=new int[n+1]; double []low=new double[n+1]; double []high=new double[n+1]; //桶初始化 for (int i=1, i<=n-1; i++) { count[i]=0; low[i]=maxx; high[i]=minx; } //将n个数置于n-1个桶中 for (int i=1; i<=n; i++) { int bucket=(int)((n-1)*(x[i]-minx)/(maxx-minx))+1; count[bucket]++; if (x[i] for (int i=2; i<=n-1; i++) if (count[i]>0) { double thisgap=low[i]-left; if (thisgap>tmp) tmp=thisgap; left=high[i]; } return tmp; } 其中，mini和maxi分别计算数组中最小元素和最大元素的下标。 实验题2 设A和B是两个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括： （1） 删除一个字符； （2） 插入一个字符； （3） 将一个字符改为另一个字符； 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的两个字符串A和B，计算出它们的编辑距离d(A,B)。 分析与解答： 设所给的两个字符串为A[1:m]和B[1:n]。定义D[i,j]?d(A[1:i],B[1:j])。 单字符a，b间的距离定义为： ?0d(a,b)???1a?ba?b 考察从字符串A[1:i]到字符串B[1:j]的变换。可分以下几种情况来讨论。 （1） 字符A[i]改为字符B[i]；需要d(A[i],B[j])次操作。 （2） 删除字符A[i]；需要1次操作。 （3） 插入字符B[i]；需要1次操作。 因此D[i][j]可递归地计算如下。 D[i][j]?min{D[i?1][j?1]?d(A[i],B[j]),D[i?1][j]?1,D[i][j?1]?1} D[i][j]的初始值为：D[i][0]?i,D[0][j]?j,i?0~m,j?0~n。 据此容易设计出计算d[A,B]的动态规划算法如下： public static int dist() { int m=a.length(); int n=b.length(); int []d=new int[n+1]; for (int i = 1; i <= n; i++) d[i] = i; for (int i = 1; i <= m; i++) { int y=i-1; for ( int j=1; j<=n; j++) { int x=y; y=d[j]; int z=j>1?d[j-1]:i; int del= a.charAt (i -1) == b.charAt( j -1)?0:1; d[j] =min( x+ del, y+1, z+1); } } Return d[n]; } 实验题3 套汇问题 问题描述 套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种 货币。例如，假定1美元可以买0.7英镑，1英镑可以买9.5法郎，且1法郎可以买到0.16美元，通过货币兑换，一个商人可以从1美元开始买入，得到0.7×9.5×0.16=1.064美元，从而获得6.4%的利润。 给定n种货币c1,c2,...cn的有关兑换率，试设计一个有效算法，用以确定是否存在套汇的可能性。 分析与解答： 通过计算兑换率矩阵的传递闭包进行判断。算法主体如下。 while (true) { n=keyboard.readInt(); if (n==0) break; for (i=0; i } edges=keyboard.readInt(); for (i=0; i for (i=0; i