算法设计与分析基础习题参考答案

1习题 1.1 5证明等式 gcd(m,n)=gcd(n,m mod n)对每一对正整数 m,n 都成立.Hint:根据除法的定义不难证明: 如果 d 整除 u 和 v, 那么 d 一定能整除 uv; 如果 d 整除 u,那么 d 也能够整除 u 的任何整数倍 ku.对于任意一对正整数 m,n,若 d 能整除 m 和 n,那么 d 一定能整除 n 和 r=m mod n=m-qn；显然，若d 能整除 n 和 r，也一定能整除 m=r+qn 和 n。数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故 gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如 00temp2*ax1(-b+sqrt(D)/tempx2(-b-sqrt(D)/tempreturn x1,x2else if D=0 return b/(2*a)else return “no real roots”else /a=0if b0 return c/belse /a=b=0if c=0 return “no real numbers”else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法 输入：一个正整数 n输出：正整数 n 相应的二进制数第一步：用 n 除以 2，余数赋给 Ki(i=0,1,2.)，商赋给 n第二步：如果 n=0，则到第三步，否则重复第一步第三步：将 Ki 按照 i 从高到低的顺序输出b.伪代码 算法 DectoBin(n)/将十进制整数 n 转换为二进制整数的算法/输入：正整数 n/输出：该正整数相应的二进制数，该数存放于数组 Bin1.n中i=1while n!=0 do Bini=n%2;n=(int)n/2;i+;while i!=0 doprint Bini;i-;9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进.算法 MinDistance(A0n-1)3/输入:数组 A0n-1/输出:the smallest distance d between two of its elements习题 1.3 考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:4b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间 for S and Count4.(古老的七桥问题)习题 1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度.a.删除数组的第 i 个元素(1b=1(若 a=2), 显然, 若算法需要 n 次模运算, 则有un=gcd(a, b), un+1=0. 我们比较数列un和菲波那契数列Fn, F0=1=uk+1+uk+2, 由数学归纳法容易得到 uk=Fn-k, 于是得到 a=u0=Fn, b=u0=Fn-1. 也就是说如果欧几里得算法需要做 n 次模运算, 则 b 必定不小于 Fn-1. 换句话说, 若 b(1.618)n/sqrt(5), 即 b(1.618)n/sqrt(5), 所以模运算的次数为 O(lgb)-以 b 为底数 = O(lg(2)b)-以 2 为底数，输入规模也可以看作是 b 的 bit 位数。习题 2.27.对下列断言进行证明:(如果是错误的,请举例)a. 如果 t(n)O(g(n),则 g(n)(t(n)b.0 时,( g(n)= (g(n)解:a. 这个断言是正确的。它指出如果 t(n)的增长率小于或等于 g(n)的增长率，那么 g(n)的增长率大于或等于 t(n)的增长率由 t(n)c g(n) for all nn0, where c0则：)()1(gtfor all nn0b. 这个断言是正确的。只需证明 )()(),()( ngng。设 f(n) (g(n),则有：)ngcffor all n=n0, c0(1for all n=n0, c1=c0即：f(n) (g(n)又设 f(n)(g(n),则有： )(ncgf for all n=n0,c0)()()(1cngffor all n=n0,c1=c/0即：f(n) ( g(n)8证明本节定理对于下列符号也成立：a. 符号b. 符号证明：a。we need to proof that if t1(n)(g1(n) and t2(n)(g2(n), then t1(n)+ t2(n)(maxg1(n), g2(n)。由 t1(n)(g1(n) ，t1(n)c1g1(n) for all n=n1, where c106由 t2(n)(g2(n) ，T2(n)c2g2(n) for all n=n2, where c20那么，取 c=minc1,c2,当 n=maxn1,n2时：t1(n)+ t2(n)c1g1(n)+ c2g2(n)c g1(n)+c g2(n)cg1(n)+ g2(n)cmax g1(n), g2(n)所以以命题成立。b. t1(n)+t2(n) ( )(2,1maxng证明：由大的定义知，必须确定常数 c1、c2 和 n0，使得对于所有 n=n0，有：)(2,1max()(21)(,( ngntc 由 t1(n)(g1(n)知，存在非负整数 a1,a2 和 n1 使：a1*g1(n)0，g1(n)+g2(n)g1(n),即 g1+g2max(g1,g2)。则（3）式转换为：C1*max(g1,g2) =n0 时上述不等式成立。证毕。10. 切忌算法走的步数和人真实走的步数的区别，算法是不需要走回头路的。习题 2.4解下列递推关系 （做 a,b）a.解：0)1(5)xn当 n1 时7b.解：对于计算 n!的递归算法 F(n)，建立其递归调用次数的递推关系并求解。解：考虑下列递归算法，该算法用来计算前 n 个立方的和：S(n)=13+23+n3 。算法 S(n)/输入：正整数 n /输出：前 n 个立方的和if n=1 return 1else return S(n-1)+n*n*na. 建立该算法的基本操作次数的递推关系并求解b. 如果将这个算法和直截了当的非递归算法比，你做何评价？解：a.4)1()3xn当 n1 时86. 汉诺塔的非递归问题请见 F:work继续教育 算法设计与分析基础7. a. 请基于公式 2n=2n-1+2n-1，设计一个递归算法。当 n 是任意非负整数的时候，该算法能够计算 2n 的值。b. 建立该算法所做的加法运算次数的递推关系并求解c. 为该算法构造一棵递归调用树，然后计算它所做的递归调用次数。d. 对于该问题的求解来说，这是一个好的算法吗？解:a.算法 power(n)/基于公式 2n=2n-1+2n-1,计算 2n/输入:非负整数 n/输出: 2n 的值If n=0 return 1Else return power(n-1)+ power(n-1)c.9ninC012)(8.考虑下面的算法算法 Min1(A0n-1)/输入:包含 n 个实数的数组 A0n-1If n=1 return A0Else tempMin1(A0n-2)If tempAn-1 return tempElse return An-1a.该算法计算的是什么?b.建立该算法所做的基本操作次数的递推关系并求解解:a.计算的给定数组的最小值b. 01)()nC9.考虑用于解决第 8 题问题的另一个算法,该算法递归地将数组分成两半.我们将它称为Min2(A0n-1)算法 Min(Arl)If l=r return AlElse temp1Min2(Al(l+r)/2)Temp2Min2(Al(l+r)/2+1r)If temp1temp2 return temp1Else return temp2a.建立该算法所做的的操作次数的递推关系并求解b.算法 Min1 和 Min2 哪个更快?有其他更好的算法吗?解:a.for all n1n=110习题 2.54.假设 n 格梯子有 f(n)种方法。 则： f(1) = 1 f(2) = 2 对 n2，有： f(n) = （先上一格，再上 n-1 格的方法数） + （先上两格，再上 n-2 格的方法数） 即 f(n) = f(n-1) + f(n-2) 所以 f(n)是 Fibonacci 数列的第 n+1 项？ #include long fib(int n) if (n = 1 | n = 2) return 1; return fib(n - 1) + fib(n - 2); main() int n; scanf(“%d“, printf(“%ldn“, fib(n+1); return 0; 习题 2.6考虑下面的排序算法,其中插入了一个计数器来对关键比较次数进行计数.算法 SortAnalysis(A0n-1)/input:包含 n 个可排序元素的一个数组 A0n-1/output:所做的关键比较的总次数count0for i1 to n-1 do vAiji-111while j0 and Ajv do countcount+1Aj+1Ajjj+1Aj+1vreturn count比较计数器是否插在了正确的位置?如果不对,请改正.解:应改为:算法 SortAnalysis(A0n-1)/input:包含 n 个可排序元素的一个数组 A0n-1/output:所做的关键比较的总次数count0for i1 to n-1 do vAiji-1while j=0 and Ajv do countcount+1Aj+1Ajjj-1if j=0 count=count+1Aj+1vreturn count7. b gcd（m,n）算法性能最坏情况下为两个整数为斐波那锲数列,即 k 时间最长时，最小的整数对必定为斐波那锲数列。9. 我认为埃拉托色尼筛的效率为根号 n。10. gcd(a,b)复杂性估计c = a % b ; c acenter_index。如果 i 和 j 都走不动了， i j。 交换 aj和 acenter_index，完成一趟快速排序。在中枢元素和 aj交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素 5 和 3(第 5 个元素，下标从1 开始计)交换就会把元素 3 的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和 aj交换的时刻。 (5)归并排序归并排序是把序列递归地分成短序列，递归出口是短序列只有 1 个元素(认为直接有序) 或者 2个序列(1 次比较和交换),然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在 1 个或 2 个元素时，1 个元素不会交换，2 个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。 (6)基数排序基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高14位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。 (7)希尔排序(shell)希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比 o(n2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以 shell 排序是不稳定的。 (8)堆排序我们知道堆的结构是节点 i 的孩子为 2*i 和 2*i+1 节点，大顶堆要求父节点大于等于其 2 个子节点，小顶堆要求父节点小于等于其 2 个子节点。在一个长为 n 的序列，堆排序的过程是从第n/2 开始和其子节点共 3 个值选择最大 (大顶堆)或者最小(小顶堆),这 3 个元素之间的选择当然不会破坏稳定性。但当为 n/2-1, n/2-2, .1 这些个父节点选择元素时，就会破坏稳定性。有可能第 n/2个父节点交换把后面一个元素交换过去了，而第 n/2-1 个父节点把后面一个相同的元素没有交换，那么这 2 个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。 7.用链表实现选择排序的话,能不能获得和数组版相同的 (n2)效率?Yes.Both operationfinding the smallest element and swapping it can be done as efficiently with the linked list as with an array. 9.a.请证明,如果对列表比较一遍之后没有交换元素的位置,那么这个表已经排好序了,算法可以停止了.b.结合所做的改进,为冒泡排序写一段伪代码.c.请证明改进的算法最差效率也是平方级的.Hints:第 i 趟冒泡可以表示为:如果没有发生交换位置,那么:b.Algorithms BetterBubblesort(A0n-1)/用改进的冒泡算法对数组 A0n-1排序/输入:数组 A0n-1/输出:升序排列的数组 A0n-1countn-1 /进行比较的相邻元素对的数目flagtrue /交换标志while flag doflagfalsefor i=0 to count-1 do if Ai+1 等分段求最小值：这种算法先假设把大楼分成等高的 x 段，这样在最差的情况下，要确定临界段，我们需要投掷 100/x-1 次，确定了临界段之后要确定临界层，我们需要再投掷 x-1 次。这样，问题就成了求函数 f(x)=(100/x-1)+(x-1) 的最小值问题。由于 f(x) 存在最小值且只有一个驻点，所以当 x=10 时 f(x) 取得最小值，最小值为 18。 假设投掷次数是均匀分布的，那么为了使最坏情况的投掷数最小，我们希望无论临界段在哪里，总的投掷数都不变（也就是说将投掷数均匀分布） 。这样我们就可以假设第一次投掷的层数是 f，转化成数学模型，可以得到如下方程式 f+(f-1)+.+2+1=99，即 f(f+1)/2=99 的最小整数解，解出结果等于 14。程序算法如下： 按结果分析看来，方法一的最小值的确比较小（10）但是问题是最大值无法确定（比如假设临界层在第 99 层则需要仍 19 下） ；而方法二的算法好在能得出一个固定的临界层值，这样便于一些问题的处理。总的来说，石头认为两种方法各有所长，虽然方法二看起来的确更接近出题者的本意，但是如果将棋子本身破碎的概率也考虑进去就不一定了（当然，一般来说层数越高破碎的概率应该越大，但是我们试想一下如果假设棋子破碎的几率是和层数成反比，那么使用方法一是否会有更好的效果呢？） 。然而不管出题者的意图是什么，我觉得这个题目所引出的数学模型还是很有实用意义的，特别在一些数据挖掘应用中。我猜想这些算法是不是与 Google 数据库的技术内幕有什么联系呢 . 前几天和一个业内的前辈谈起下一代互联网的技术趋势，说到了所谓的“算法时代” 的话题，看来关注一些有趣的算法也不错呢 . 不知不觉时间又晚了，还是先休息吧 ：）6.给出一个长度为 n 的文本和长度为 m 的模式构成的实例,它是蛮力字符串匹配算法的一个最差输入.并指出,对于这样的输入需要做多少次字符比较运算.Hints:文本:由 n 个 0 组成的文本模式:前 m-1 个是 0,最后一个字符是 116比较次数: m(n-m+1)7.为蛮力字符匹配算法写一个伪代码,对于给定的模式,它能够返回给定的文本中所有匹配子串的数量.Algorithms BFStringmatch(T0n-1,P0m-1)/蛮力字符匹配/输入:数组 T0n-1长度为 n 的文本,数组 P0m-1长度为 m 的模式/输出:在文本中匹配成功的子串数量count0for i0 to n-m do j0while jp）枚举所有的排列，看看是否有序。(1)穷举法：枚举所有的幻方组合，看看是否满足条件(2)网上幻方制作方法：（Magic_Square.pdf）（1）穷举所有的对应表，按对应表把算式进行对应，如果的确相等，即该算数对应正确。题中字母共有 8 个，即所有情况为从 10 个字母中选出 8 个，同时 S M不能为 0，即取时的方法共为 9（s 不能为 0）*8（m 不能为 0）*8!种。（2）见 /wiki/Verbal_arithmetic。The solution to this puzzle is O = 0, M = 1, Y = 2, E = 5, N = 6, D = 7, R = 8, and S = 9用回溯法豪无疑问，M 肯定为 1，而 S 必定为 9，或者 8，S 为 9 时，推出 o 必定为 0，就这样一步步推下去，不行就回溯。20习题 4.11.a.为一个分治算法编写伪代码,该算法求一个 n 个元素数组中最大元素的位置.b.如果数组中的若干个元素都具有最大值,该算法的输出是怎样的呢?c.建立该算法的键值比较次数的递推关系式并求解.d.请拿该算法与解同样问题的蛮力算法做一个比较解:a.Algorithms MaxIndex(Alr)Input:A portion of array A0n-1 between indices l and r(lr)Output: The index of the largest element in Alrif l=r return lelse temp1MaxIndex(Al(l+r)/2)temp2MaxIndex(A(l+r)/2r)if Atemp1Atemp2 return temp1else return temp2b.返回数组中位于最左边的最大元素的序号.c.键值比较次数的递推关系式:C(n)=C( n/2 )+C( n/2 )+1 for n1C(1)=0 设 n=2k，C(2k)=2C(2k-1)+1=22 C(2k-2)+1+1=22C(2k-2)+2+1=222C(2k-3)+1+2+1=23C(2k-3)+ 22+2+1=.=2iC(2k-i)+ 2i-1+2 i-2 +.+2+1=.=2kC(2k-k)+ 2k-1+2 k-2 +.+2+1=2k1=n-1可以证明 C(n)=n-1 对所有 n1 的情况都成立（n 是偶数或奇数）d.比较的次数相同，但蛮力算法不用递归调用。2、a.为一个分治算法编写伪代码，该算法同时求出一个 n 元数组的最大元素和最小元素的值。b.请拿该算法与解同样问题的蛮力算法做一个比较。c.请拿该算法与解同样问题的蛮力算法做一个比较。解答：a.同时求出最大值和最小值，只需要将原数组一分为二，再使用相同的方法找出这两个部分中的最大值和最小值，然后经过比较就可以得到整个问题的最大值和最小值。 算法 MaxMin(Alr,Max,Min)/该算法利用分治技术得到数组 A 中的最大值和最小值/输入：数值数组 Alr/输出：最大值 Max 和最小值 Minif(r=l) MaxAl；MinAl; /只有一个元素时elseif rl=1 /有两个元素时if AlArMaxAr; MinAl21elseMaxAl; MinArelse /rl1MaxMin(Al,(l+r)/2,Max1,Min1); /递归解决前一部分MaxMin(A(l+r/)2r,Max2,Min2); /递归解决后一部分if Max1Max2 Max= Max2 /从两部分的两个最大值中选择大值if Min22C(1)=0, C(2)=1C(n)=C(2k)=2C(2k-1)+2=22C(2k-2)+2+2=22C(2k-2)+22+2=222C(2k-3)+2+22+2=23C(2k-3)+23+22+2.=2k-1C(2)+2k-1+2k-2+.+2 /C(2)=1=2k-1+2k-1+2k-2+.+2 /后面部分为等比数列求和=2k-1+2k-2 /2(k-1)=n/2,2k=n=n/2+n-2=3n/22b.蛮力法的算法如下： 算法 simpleMaxMin(Alr)/用蛮力法得到数组 A 的最大值和最小值/输入：数值数组 Alr/输出：最大值 Max 和最小值 MinMax=Min=Al;for i=l+1 to r do if AiMax MaxAi;else if Aibd，由于底决定 n 的次方，所以不能略。6.应用合并排序对序列 E,X,A,M,P,L,E 按字母顺序排序.238.a.对合并排序的最差键值比较次数的递推关系式求解.(for n=2k)b.建立合并排序的最优键值比较次数的递推关系式求解.(for n=2k)c.对于 4.1 节给出的合并排序算法,建立它的键值移动次数的递推关系式.考虑了该算法的键值移动次数之后,是否会影响它的效率类型呢?解:递推关系式见 4.1 节.最好情况(列表升序或降序)下:Cbest(n)=2Cbest(n/2)+n/2 for n1 (n=2k)Cbest(1)=012324键值比较次数 M(n)M(n)=2M(n/2)+2n for n1M(1)=09 修改合并排序，在、C 两个数组合并时，一但比较时发现的元素小于 C，站在 C 的角度考虑，C 后面的元素都大于 B,假设前面的元素都考虑过了，则此处没有导致情况，假设 B 的元素大于 C，则必定对于 C 这个元素来说， B 前面的所有元素都比 C 中那个元素小，不形成对置，B 后面的所有元素都大于 C，则 B 后面的所有元素与 C 中被比较的那个元素形成倒置，这些对置形成了包含 C 中那个元素的所有对置，当 B 元素和 C 比较后，C 元素指针变为下一个元素，这样，包含 C 当前指针前面的所有元素的倒置都考虑过了，我们只要考虑 C 元素后面的情况就可以了，由于对于。举个例子。一次合并过程中，现在数组 B 元素为 2 3 8 9 , C 元素为 1 4 5 7。这样假设 B 和 C 本身中所含的倒置为 b 和 c，则合并后的 C 数组的导致为:s 初始为 b+c2 3 8 9 1 4 5 7(1) 21 时 倒置为(2 1) (3 1) (8 1) (9 1) S=S+4(2) 84 时 倒置为(8 4) (9 4) S=S+2(3) 85 时 倒置为(8 5) (9 5) S=S+2;(4) 87 时 倒置为(8 7) (9 7) S=S+2;则 s=b+c+1010/mathdemos/tromino/tromino.html当 n=1 时，很显然是成立的，当 n=2 时，即为 4*4 的期盘，可以分成 4 个 2*2 的期盘，可以分成两种情况，第一种情况：已填充块在中间（黄色）25第二种情况：已填充块在边上很显然，n=2 时，4*4 的块可以分成 4 个 2*2 的块，而已填充的那 1 块必落在 4 个 2*2 的某 1 块中，设该块为 A，填充的第一步就是在其他三个不包含 A 块的 2*2 块中各选 1 块，形成 L 型，如上图第 1 种情况的的红色部分或第二种情况的蓝色部分，显然，剩下的部分都能给 L 填满。假设 n=2K 时，含有 1 块填充的 2k*2k 期盘能够被填满，则含有 n=2（k+1）必定得棋盘能够分成 4 个 2K*2k，1 块已填充部分落在 4 块其中的 1 块，则选择其他三块形成一个 L 型，则 4块期盘分别变成 n=2k 的问题。由于 n=2K 结论成立，则已有 1 个填充块的 2(k+1)*2(k+1)的期盘必定能够被的 L 型填满。所以给定该题用分治法解决如下：如果 n=2;即为 2*2 的已填充 1 个方格的方块，显然，剩余的部分形成 L 型。否则（2）设 n=k (k2) 把 2k*2k 的方块分成 4 块，分别靠紧填充不含已填充方格的 L 型，递归解决 n=k-1 的问题习题 4.21.应用快速排序对序列 E,X,A,M,P,L,E 按字母顺序排序264 请举一个 n 个元素数组的例子,使得我们有必须对它使用本节提到的”限位器”.限位器的值应是多少年来?为什么一个限位器就能满足所有的输入呢?Hints:27With the pivot being the leftmost element, the left-to-right scan will get out of bounds if and only if the pivot is larger than the other elements.Appending a sentinel(限位器) of value equal A0(or larger than A0) after the arrays last element , the quicksort algorithms will stop the index of the left-to-right scan of A0n-1 from going beyond position n.8.设计一个算法对 n 个实数组成的数组进行重新排列,使得其中所有的负元素都位于正元素之前.这个算法需要兼顾空间和时间效率.Algorithms netbeforepos(A0n-1)/使所有负元素位于