算法设计与分析习题与实验题(12.18)

算法设计与分析习题第一章 引 论 习题1-1 写一个通用方法用于判定给定数组是否已排好序。解答： Algorithm compare(a,n) Begin J=1; While (jn and aj=aj+1) do j=j+1; If j=n then return true Else While (j=aj+1) do j=j+1; 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-1until (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 照渐进阶从低到高的顺序排列以下表达式：，。 解答：照渐进阶从低到高的顺序为：、 3n、 、20n、logn、2习题2-4 （1） 假设某算法在输入规模为n时的计算时间为。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（2） 若上述算法的计算时间改进为，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？（3） 若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答：（1） 设新机器用同一算法在t秒内能解输入规模为的问题。因此有，解得。（2） 。（3） 由于常数，因此算法可解任意规模的问题。习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为，和的各算法，若用ABC公司的计算机能在1小时内能解输入规模为的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？ 解答：。习题2-6对于下列各组函数和，确定或或，并简述理由。（1）。（2）。（3）。（4）。（5）。（6）。（7）。（8）。解答：（1）。（2）。（3）。（4）。（5）。（6）。（7）。（8）。习题2-7 证明：如果一个算法在平均情况下的计算时间复杂性为，则该算法在最坏情况下所需的计算时间为。证明：因此，。习题2-7 求解下列递归方程: s0=0 sn=2sn-1+2n -1 解答：步骤: 1应用零化子化为齐次方程，2解此齐次方程的特征方程，3由特征根构造一般解，4再由初始条件确定待定系数，得到解为：习题2-8 求解下列递归方程: 解 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 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) left = middle;else right = middle;if ( x = aleft) return left ;else return -1;public static int binarySearch4(int a, int x, int n)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 +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) return left;return -1;分析与解答：算法binarySearch1数组段左右游标left和right的调整不正确，导致陷入死循环。算法binarySearch2数组段左右游标left和right的调整不正确，导致当x=an-1时返回错误。算法binarySearch3数组段左右游标left和right的调整不正确，导致当x=an-1时返回错误。算法binarySearch4数组段左右游标left和right的调整不正确，导致陷入死循环。算法binarySearch5正确，且当数组中有重复元素时，返回满足条件的最右元素。算法binarySearch6数组段左右游标left和right的调整不正确，导致当x=an-1时返回错误。算法binarySearch7数组段左右游标left和right的调整不正确，导致当x=an-1时陷入死循环。习题3-2 设是已排好序的数组。请改写二分搜索算法，使得当搜索元素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 amiddle) left = middle + 1;else right = middle -1;ind0 = right; ind1=left;return false;返回的ind1是小于x的最大元素位置，ind0是大于x的最小元素的位置。习题3-3 设是有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=;For k=0 to h-1 do Begin x=ai+k; ai+k=aj-k; aj-k= x end ;end习题3-4 如果在合并排序算法的分割步中，讲数组划分为个子数组，每个子数组中有个元素。然后递归地对分割后的子数组进行排序，最后将所得到的个排好序的子数组合并成所要求的排好序的数组。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。分析与解答：实现上述策略的合并排序算法如下：public static void mergesort(int a, int left ,int right) if (left 1) for (int i=0; ij; i+) mergesort(a, left+i*j,left+(i+1)*j-1);mergesort(a,left+i*j,right);mergeall(a,left,right);其中，算法mergeall合并个排好序的数组段。在最坏情况下，算法mergeall需要时间。因此上述算法所需的计算时间满足：此递归式的解为：。习题3-5 设是整数集合，其中每个集合中整数取值范围是，且，试设计一个算法，在时间内将分别排序。分析与解答：用桶排序或基数排序算法思想可以实现整数集合排序。习题6 设和为两个数组，每个数组中还有n个已排好序的数。试设计一个时间的算法，找出X和Y的2n个数的中位数。分析与解答：（1） 算法设计思想考虑稍一般的问题：设和是X和Y的排序好的子数组，且长度相同，即。找出这两个数组中个数的中位数。首先注意到，若，则中位数median满足。同理若，则。设，则由于，故。因此。当时，。当时，设是和的中位数，则。当时，设是和的中位数，类似地有。通过以上讨论，可以设计出找出两个子数组和的中位数median的算法。（2） 设在最坏情况下，算法所需的计算时间为。由算法中和的选取策略可知，在递归调用时，数组X和Y的大小都减少了一半。因此，满足递归式：解此递归方程可得：。习题3-6 Gray码是一个长度为的序列。序列中无相同元素，每个元素都是长度为n位的（0，1）串，相邻元素恰好只有1位不同。用分治策略设计一个算法，对任意的n构造相应的Gray码。分析与解答：考察的简单情形。n=101n=200011110n=3000001011010110111101100设n位Gray码序列为以相反顺序排列的序列为。从上面的简单情形可以看出的构造规律：。注意到的最后一个n位串与的第1个n位串相同，可用数学归纳法证明的上述构造规律。由此规律容易设计构造的分治法如下。public static void Gray(int n)if ( n = 1) a1 = 0; a2 = 1; return; Gray(n-1);for ( int k = 1 0; i-) a2*k-i+1=ai + k;上述算法中将n位（0，1）串看做是二进制整数，第i个串存储在中。完成计算之后，由out输出Gray码序列。public static void out(int n)int m=1n;for (int i=1; i=m; i+) String str=Integer.toBinaryString(ai);int s=str.length();for ( int j=0; jn-s; j+) System.out.print(“0”);System.out.println(Integer.toBinaryString(ai)+” ”);System.out.println();第四章 动态规划 习题4-1 设计一个时间的算法，找出由n个数组成的序列的最长单调递增子序列。分析与解答：用数组记录以为结尾元素的最长递增子序列的长度。序列a的最长递增子序列的长度为。易知，满足最优子结构性质，可以递归地定义为：据此将计算转化为i个规模更小的子问题。按此思想设计的动态规划算法描述如下：public static int LISdyna()int i, j, k;for ( i=1, b0=1; in;i+) for ( j=0, k=0; jI; j+ ) if ( aj = ai & k bj ) k=bj;bi= k+1;return maxL(n);static int maxL(int n)int temp=0;for ( int i= 0; i temp) temp=bi;return temp;上述算法LISdyna按照递归式计算出的值，然后由maxL计算出序列a的最长递增子序列的长度。从算法LISdyna的二重循环容易看出，算法所需的计算时间为。习题4-2 考虑下面的整数线性规划问题： 为非负整数，试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。分析与解答：该问题是一般情况下的背包问题，具有最优子结构性质。设所给背包问题的子问题：的最优值为，即是背包容量为j，可选择物品为1，2，i时背包问题的最优值。由背包问题的最优子结构性质，可以建立计算的递归式如下：。按此递归式计算出的为最优值。算法所需的计算时间为。习题4-3 给定一个由n行数字组成的数字三角形如图3-2所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。 7 3 88 1 0 2 7 4 4 4 5 2 6 5 数字三角形分析与解答：记f(uij)为至ij元素的最大路径值, aij ：元素(i,j)之值。递归式: 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; end;var a:array 1. maxn, 1.maxn of node;procedure findmax;begina 1,1. f :=a1,1.val; for i:=2 to n do for j:=1 to i do begin 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) 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; writeln (a n, max. f)end;第五章 贪心算法 习题5-1 特殊的0-1背包问题若在0-1背包问题中，各物品依重量递增排列时，其价值恰好依递减序排列。对这个特殊的0-1背包问题，设计一个有效算法找出最优解，并说明算法的正确性。分析与解答：设所给的输入为。不妨设。由题意知。由此可知，贪心选择性质：当时问题无解。当时，存在0-1背包问题的一个最优解使得。事实上，设使0-1背包问题的一个最优解，且。对任意，取，则满足贪心选择性质的最优解。习题5-2 Fibonacci序列的Huffman编码试证明：若n个字符的频率恰好是前n个Fibonacci数，用贪心法得到它们的Huffman编码树一定为一棵“偏斜树”。分析与解答： 频率恰好是前8个Fibonacci数的哈夫曼编码树如图所示。543321521311320127428图 哈夫曼编码树证明：n个字符的频率恰好是前n个Fibonacci数，则相应的哈夫曼编码树自底向上第i个内结点中的数为。用数学归纳法容易证明。因f1=1,f2=1,f3=2,可知i=1时，上述结论成立。设对i+2上述结论成立，即有， 因，说明对i+3上述结论成立. 该性质保证了频率恰好是前n个Fibonacci数的哈夫曼编码树具有“偏斜树”形状。习题5-3 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。分析与解答：设所给的n个活动为1，2，n，它们的开始时间和结束时间分别为和，且。可以将n个活动1，2，n看作实直线上的n个半闭活动区间。所讨论的问题实际上是求这n个半闭区间的最大重叠数。因为重叠的活动区间所相应的活动是互不相容的。若这n个活动区间的最大重叠数为m，则这m个重叠区间所对应的活动互不相容，因此至少安排m个会场来容纳这m个活动。为了有效地对这n个活动进行安排，首先将n个活动区间的2n个端点排序。然后，用扫描算法，从左到右扫描整个实直线。在每个事件点处（即活动的开始时刻或结束时刻）作会场安排。当遇到一个开始时刻，就将活动i安排在一个空闲的会场中。遇到一个结束时候，就将活动i占用的会场释放到空闲会场栈中，以备使用。经过这样一遍扫描后，最多安排了m个会场（m是最大重叠区间数）。因此所作的会场安排是最优的。上述算法所需的计算时间主要用于对2n个区间端点的排序，这需要计算时间。具体算法描述如下。public static int greedy(point x)int sum=0, curr=0, n=x.length;MergeSort.mergeSort(x);for (int i=0; in;i+) if (xi.leftend() curr+;else curr-;/处理xi=xi+1的情况if ( i = n-1xi.compareTo(xi+1)sum) sum=curr;return sum;习题5-4 假设要在m个会场里安排一批活动，并希望使用尽可能多地安排活动。设计一个有效的贪心算法进行安排。Algorithm greedy(s,f,m,n); Input s1:n, f1:n; Output x1:m, 1:n;Begin对数组s和f中的2n个元素排序存入数组y1:2n中；空闲栈清空；d数组所有元素置初值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 设其相应的s 存于xj,k 中，将j存入空闲栈中； End For i= 1 to m do For j=1 to dj do Output xi,j;End 习题5-5 删数问题 问题描述给定n位正整数a，去掉其中任意个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的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.length()-1)&(a.charAt(i)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; finish=false; repeat if t=ai then begin sp=sp+1；ssp=i; t=t-ai; if t=0 then i=n; end; i=i+1; while in do if sp1 then begin if t=0 then out; t=t+assp; i=ssp+1; sp=sp-1 end else begin finish=true; i=1 enduntil finishendend 习题6-2 中国象棋的半个棋盘如图所示，马自左下角往右上角跳。规定只许向右跳，不许向左跳，计算所有的行走路线。 Algorithm chess Begin top=0; y0=0; x0=0; di=1; r=0;push;repeat pop; while di2 then 回溯 begin bt=0; t=t-1; end else begin if bt=2 then at=B else if at-1=R then t=t-1 else at=R; if t=n then output a else t=t+1 end until t=0第七章 分支限界法习题7-1. 试写出采用分支界限法求解下面的0、1背包问题实例的过程： 物品的个数n=4, 背包的重量m=15, 各个物品的重量依次为2，4，6，9，各个物品的价值依次为10，10，12，18。 对于第i层上的每个节点x，其价值的上界定义为有贪心法所求出的一般背包问题的解Su(x)，下界为Sl(x)为Su(x)中减去最后放入背包的xi1的物品的相应部分价值。解答： 习题7-2. 写出用分支界限法求解下面的重排九宫问题的算法。开始状态 目标状态8126375412384765 解答： 我们对九宫中的位置做如下的编号：位置编号 123894765则初始状态用向量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与目标状态不相同的数字的数目， ，这里，算法： Algorithm LC(S0, S*) Input: 初始状态向量S0 , 目标状态S*；Output: 达到目标状态的状态序列；BeginS=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 endwhileend 第八章 NP完全问题习题8-1 证明析取范式的可满足性问题属于P类。分析与解答： 析取范式是由因子之和的和式给出的。这里因子是指变量x或，每个因子之积称为一个析取式。例如 x1x2+x2x3+x3就是一个析取范式。 设给定一个析取范式，其中是变量或，j=1n的一个析取范式，i=1m。是可满足的，当且仅当存在i, ，使是可满足的。如果有一个多项式时间算法能判断任何一个析取式的可满足性，则用该算法对的每个析取项逐一判断就可以在多项式时间内确定析取范式的可满足性。因此，问题可简化为找一个确定析取式可满足性的多项式时间算法。 设析取范式=，其中。 可以设计在O(n+k)时间内确定析取式=可满足性的算法。因此，析取范式的可满足性问题是多项式时间可解的，即它属于P类。 第九章 近似算法习题9-1 瓶颈旅行售货员问题瓶颈旅行售货员问题是要找出图G=(V,E)的一个哈密顿回路，且使回路中最长边的长度最小。若费用函数满足三角不等式，给出解此问题的性能比为3的近似算法。（提示：递归地证明，可以通过对G的最小生成树进行完全遍历并跳过某些项点，但不能跳过多于2个连续的中间顶点，以此方式访问最小生成树中每个顶点恰好一次。）分析与解答：解瓶颈旅行售货员问题的性能比为3的近似算法描述如下：Void approxTSP(Graph G) 选择任一顶点 rV； 找出G的一棵以r为根的最小瓶颈生成树T； 选取 T的一条边（p,q）作为哈密顿回路H的一条边； 遍历树T，跳过不多于两个连续的重复顶点，递归构造H的其他边； 将所得到的哈密顿回路H作为计算结果返回. 习题9-2 可满足问题的近似算法 问题描述 设是一个含有n个变量和m个合取项的合取范式。关于的最大可满足性问题要求确定的最多个数的合取式使这些合取式可同时满足。设k是的所有合取式中因子个数的最小值。证明下面的解最大可满足性问题的近似算法 mSAT的相对误差为。 Set mSAT(a) / , ,是a 中n个变量；Ci ，是的m个合取项。 c1= ; left= Ci |; lit=,|; while(lit含有在left的合取式中出现的因子) 设y是lit的在left的合取式中出现次数最多的因子； 设r是left中含有因子y的所有合取式的集合； c1= c1 r; left=left-r; lit=lit-y, ; return(c1); 第十章 随机算法 习题10-1 模拟正态分布随机变量在实际应用中，常需要模拟服从正态分布的随机变量，其密度函数为，其中，a为均值，为标准差。如果s和t是（-1，1）中均匀分布的随机变量，且，令，则和是服从标准正态分布的两个互相独立的随机变量。（1） 利用上述事实，设计一个模拟标准正态分布随机变量的算法。（2） 将上述算法扩展到一般的正态分布。分析与解答：(1) 模拟标准正态分布随机变量的算法如下。public double Norm()double s,t,p,q;while (true) s=2*fRandom()-1;t=2*fRandom()-1;p=s*s+t*t;if (p1) fact(i);if (ni) fact(n/i)；算法设计与分析实验题实验题1最大间隙问题：给定n个数，求这n个数在实轴上相邻2个数之间的最大差值。假设对任何实数的下取整方法耗时为，设计解最大间隙问题的线性时间算法。分析与解答：用鸽舍原理设计最大间隙问题的线性时间算法如下。Public static 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个数置于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 (int i=2; i0) double thisgap=lowi-left;if (thisgaptmp) tmp=thisgap;left=highi;return tmp;其中，mini和maxi分别计算数组中最小元素和最大元素的下标。实验题2 设A和B是两个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：（1） 删除一个字符；（2） 插入一个字符；（3） 将一个字符改为另一个字符；将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为。试设计一个有效算法，对任给的两个字符串A和B，计算出它们的编辑距离。分析与解答：设所给的两个字符串为和。定义。单字符a，b间的距离定义为：考察从字符串到字符串的变换。可分以下几种情况来讨论。（1） 字符改为字符；需要次操作。（2） 删除字符；需要1次操作。（3） 插入字符；需要1次操作。因此可递归地计算如下。的初始值为：。据此容易设计出计算的动态规划算法如下：public static int dist()int m=a.length();int n=b.length();int d=new intn+1;for (int i = 1; i = n; i+) di = i;for (int 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 =min( x+ del, y+1, z+1);Return dn;实验题3 套汇问题问题描述套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如，假定1美元可以买0.7英镑，1英镑可以买9.5法郎，且1法郎可以买到0.16美元，通过货币兑换，一个商人可以从1美元开始买入，得到0.79.50.16=1.064美元，从而获得6.4%的利润。给定n种货币的有关兑换率，试设计一个有效算法，用以确定是否存在套汇的可能性。分析与解答：通过计算兑换率矩阵的传递闭包进行判断。算法主体如下。while (true) n=keyboard.readInt();if (n=0) break;for (i=0; in; i+) namei=keyboard.readString();for (i=0; in; i+) for (j=0; jn; j+) rij=0.0;edges=keyboard.readInt();for (i=0; iedges; i+) a=keyboard.readString();x=keyboard.readDouble();b=keyboard.readString();for (j=0; a.CompareTo(namej)!=0; j+);for (k=0;b.CompareTo(namek)!=0; k+);rjk=x;for (i=0; in; i+) rii=max(1.0,rii);for (k=0; kn; k+)for (i=0; in;i+)for (j=0; jn; j+)rij= max(rij,rik*rkj);for (i=0; i1.0) break;if (in) System.out.println(“Case”+(+cases)+”Yes”);else System.out.println(“Case”+(+cases)+”No”);友情提示：部分文档来自网络整理，供您参考！文档可复制、编制，期待您的好评与关注！28 / 28