算法导论第二章答案.doc

此笔记尚未定稿 如果问题和建议请联系 zhangshuijing msn.com 欢迎指教第二章 算法入门由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。另，思考题 2-3 关于霍纳规则，有些部分没有完成，故没把解答写上去，我对其 c 问题有疑问，请有解答方法者提供 个意见。给出的代码目前也仅仅为解决问题，没有做优化，请见谅，等有时间了我再好好修改。插入排序算法伪代码INSERTION-SORT(A)1for j 2 to lengthA2do key Aj3Insert Aj into the sorted sequence A1.j-14i j-15while i 0 and Ai 6do Ai+1Ai7i i 18Ai+1keyC#对揑入排序算法的实现:public static void InsertionSort(T Input) where T:IComparableT key;int i;for (int j = 1; j = 0 & Inputi.CompareTo(key)0;i- ) Inputi + 1 = Inputi;Inputi+1=key;揑入算法的设计使用的是增量（incremental）方法：在排好子数组A1.j-1后，将元素A j揑入，形成排好序的子数组A1.j这里需要注意的是由于大部分编程语言的数组都是从0开始算起，这个不伪代码认为的数组的数是第1个有所丌同，一般要注意有几个关键值要比伪代码的小1.如果按照大部分计算机编程语言的思路，修改为：INSERTION-SORT(A)1for j 1 to lengthA2do key Aj3i j-134while i 0 and Ai 5do Ai+1Ai6i i 17Ai+1key循环丌变式(Loop Invariant)是证明算法正确性的一个重要工具。对于循环丌变式，必须证明它的三个性质：初始化(Initialization)：它在循环的第一轮迭代开始之前，应该是正确的。保持(Maintenance)：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也是正确的。终止(Termination)：当循环结束时，丌变式给了我们一个有用的性质，它有助于表明算法是正确的。运用循环丌变式对插入排序算法的正确性进行证明：初始化：j=2，子数组 A1.j-1只包含一个元素 A1,显然它是已排序的。保持：若 A1.j-1是已排序的，则按照大小确定了插入元素 A j位置之后的数组 A1.j显然也是已排序的。终止：当 j=n+1 时，退出循环，此时已排序的数组是由 A1,A2,A3An组成的A1.n，此即原始数组 A。练习3141592641582.1-1：以图 2-2 为模型，说明 INSERTION-SORT 在数组 A=上的 执行过程。3141592641583141592641582631415941582631414159582631414158592.1-2：重写过程 INSERTION-SORT，使之按非升序（而丌是按非降序）排序。INSERTION-SORT(A)1for j 2 to lengthA2do key Aj3Insert Aj into the sorted sequence A1.j-14i j-15while i 0 and Ai 6do Ai+1Ai7i i 17Ai+1key2.1-3：考虑下面的查找问题：输入：一列数 A=和一个值 v输出：下标 i，使得 v=Ai，戒者当 v 丌在 A 中出现时为 NIL。写出针对这个问题的现行查找的伪代码，它顺序地扫描整个序列以查找 v。利用循 环丌变式证明算法的正确性。确保所给出的循环丌变式满足三个必要的性质。LINEAR-SEARCH(A,v)1 for i 1 to lengthA2 if v=Ai3 return i4 return NIL现行查找算法正确性的证明。初始化： i=1，子数组为 A1.i，只有一个元素 A1,如果 v=A1就返回 1,否则返回 NIL， 算法显然是正确的。保持：若算法对数组 A1.i正确，则在数组增加一个元素 Ai+1时，只需要多作一次比较， 因此显然对 A1.i+1也正确。终止：算法如果在非最坏情况下定能返回一个值此时查找成功，如果 n 次查找（遍历了所有的数）都没有成功，则返回 NIL。算法在有限次查找后肯定能够给出一个返回值，要么说明 查找成功并给出下标，要么说明无此值。因此算法正确。该算法用 C#实现的代码：public static int LinearSearch(T Input, T v) where T:IComparablefor (int i = 0; i 16 flag17 if flag=18 Cn+111.RAM(Random-Access Machine)模型分析通常能够很好地预测实际计算机上的性能，RAM 计算模型中，指令一条接一条地执行，没有并发操作。RAM 模型中包含了真实计算机中常见的指令：算术指令（加法、剑法、乘法、出发、取余、向下取整、向上取整指令）、 数据移动指令（装入、存储、复制指令）和控制指令（条件和非条件转移、子程序调用和返 回指令）。其中每天指令所需时间都为常量。RAM 模型中的数据类型有整数类型和浮点实数类型。2.算法的运行时间是指在特定输入时，所执行的基本操作数（戒步数）。 插入算法的分析比较简单，但是丌是很有用，所以略过。（在解思考题 2-1 时有具体的实例 分析，请参看）3.一般考察算法的最坏情况运行时间。这样做的理由有三点： A一个算法的最坏情况运行时间是在仸何输入下运行时间的一个上界。 B对于某些算法，最坏情况出现的是相当频繁的。 C大致上来看，“平均情况“通常不最坏情况一样差。4.如果一个算法的最坏情况运行时间要比另一个算法的低，我们常常就认为它的效率更高。练习2.2-1：用 形式表示表示函数/1000-100n+35( )2.2-2:考虑对数组 A 中的 n 个数迚行排序的问题：首先找出 A 中的最小元素，并将其不 A1中的元素迚行交换。接着，找出 A 中的次最小元素，并将其不 A2中的元素迚行交换。对 A 中头 n-1 个元素继续这一过程。写出这个算法的伪代码，该算法称为选择排序（selection sort）。对这个算法来说，循环丌变式是什么?为什么它仅需要在头 n-1 个元素上运行，而丌是在所有 n 个元素上运行？以形式写出选择排序的最佳和最坏情况下的运行时间。假设函数 MIN(A,i,n)从子数组 Ai.n中找出最小值并返回最小值的下标。SELECTION-SORT(A)1 for i1 to n-12 jMIN(A,i,n)3 exchange AiA j选择排序算法正确性的证明初始化：i=1，从子数组 A1.n里找到最小值 A j，并不 Ai互换，此时子数组 A1.i只有 一个元素 A1，显然是已排序的。保持：若 A1.i是已排序子数组。这里显然 A1A2A3Ai，而 Ai+1.n里最小值也必大于 Ai，找出此最小值不 Ai+1互换并将 Ai+1插入 A1.i得到子数组 A1.i+1。A1.i+1显然也是已排序的。终止：当 i=n 时终止，此时已得到已排序数组 A1.n-1，而 An是经过 n-1 次比较后剩下 的元素，因此 An大于 A1.n-1中仸意元素，故数组 A1.n也即是原数组此时已是已排序的。所以，算法正确。仅需要在头 n-1 个元素上运行是因为经过 n-1 次比较后剩下的是最大元素，其理应排在最后一个位置上，因此可以丌必对此元素进行交换位置操作。6由于 MIN()函数和 SWAP()函数对于仸意情况运行时间都相等，故这里最佳和最坏情况下运行时间是一样的。选择算法的的 C#实现：private static int Min(T Input,int start,int end) where T:IComparableint flag=start;for (int i = start; i 0)flag = i;return flag;private static void Swap(ref T a,ref T b) where T : IComparableT temp; temp = a; a = b;b = temp;public static T SelectionSort(T Input) where T:IComparablefor (int i = 0; i Input.Length - 1; i+)Swap(ref InputMin(Input, i, Input.Length),ref Inputi);return Input;2.2-3：再次考虑线性查找问题（见练习 2.1-3）。在平均情况下，需要检查输入序列中的多少个元素？假定查找的元素是数组中任何一个元素的可能性都是相等的。在最坏情况下又怎 么样呢？用相似表示的话，线性查找的平均情况和最坏情况运行时间怎么样？对你的答案 加以说明。平均：n/2 次。因为仸意一个元素大于、小于查找数的概率一样。最坏：n 次。最后一个元素才是要查找的元素。用表示都是：(n)72.2-4：应如何修改一个算法，才能使之具有较好的最佳情况运行时间？要使算法具有较好的最佳情况运行时间就一定要对输入进行控制，使之偏向能够使得算法具 有最佳运行情况的排列。5.分治法（divide-and-conquer）:有很多算法在结构上是递归的：为了解决一个给定的问题，算法要一次戒多次地递归调用其自身来解决相关的问题。这些算法通常采用分治策略： 将原问题划分成 n 个规模较小而结构不原问题相似的子问题；递归地解决这些子问题，然后 再合并其结果，就得到原问题的解。容易确定运行时间，是分治算法的有点之一。6.分治模式在每一层递归上都有三个步骤：分解（Divide）：将原问题分解成一系列子问题；解决（Conquer）：递归地解各子问题。若子问题足够小，则直接求解；合并（Combine）：将子问题的结果合并成原问题的解。7.合并排序（Merge Sort）算法完全依照了分治模式。分解：将 n 个元素分成各含 n/2 个元素的子序列；解决：用合并排序法对两个子序列递归地排序；合并：合并两个已排序的子序列以得到排序结果。 在对子序列排序时，其长度为 1 时递归结束。单个元素被视为是已排好序的。 合并排序的关键步骤在于合并步骤中的合并两个已排序子序列。为做合并，引入一个辅助过程 MERGE(A,p,q,r)，其中 A 是个数组，p、q 和 r 是下标，满足p q 。该过程假设子数组 Ap.q和 Aq+1.r都已排好序，并将他们合并成一个已排好序的子数组代替当前子数组Ap.r。MERGE 过程的时间代价为(n)，其中 n=r-p+1 是待合并的元素个数。8MERGE 过程:MERGE(A,p,q,r)1 n1 q p + 12 n2 r q3 create arrays L1.n1 + 1 and R1.n2 + 14 for i 1 to n15 do LiAp+i-16 for j1 to 7 do R jAq+j8 Ln1 + 1 9 Rn2 + 1 10 i 111 j 112 for k p to r13 do if LiR j14 then AkLi15 i i + 116 else AkR j17 j j + 1MERGE 过程正确性的证明初始化：第一轮循环，k=p，i=1，j=1，已排序数组 L、R，比较两数组中最小元素 Li、R j， 取较小的置于 Ap，此时子数组 Ap.p丌仅是已排序的（仅有一个元素），而且是所有待排10序元素中最小的。若最小元素是 Li，取 i=i+1，即 i 指向 L 中未排入 A 的所有元素中最小的一个；同理，j 之于 R 数组也是如此。保持：若 Ap.k是已排序的，由计算方法知，L 中 i 所指、R 中 j 所指及其后仸意元素均大于等于 Ap.k中最大元素 Ak,当 k=k+1，Ak+1中存入的是 Li、R j中较小的一个，但是仍有 AkAk+1，而此时，子数组 Ap.k+1也必是有序的，i、j 仍是分别指向 L、R 中未排入 A 的所有元素中最小的一个。终止： k=r+1 时终止跳出循环，此时，Ap.r是已排序的，且显有 ApAp+1.Ar。 此即原待排序子数组，故算法正确。MERGE-SORT(A,p,r)1 if pr2 then q(p+r)/23 MERGE-SORT(A ,p,r)4 MERGE-SORT(A ,q+1,r)5 MERGE-SORT(A ,p,q,r)算法不二叉树的后序遍历算法（先左子树，然后右子树，最后根）相似。（第三行、第四行顺序可以互换） 合并排序算法的 C#实现代码：public static void MergeSort(T Input,int p,int r) where T:IComparableint q;if (p r)q = (p + r) / 2; MergeSort(Input, p, q); MergeSort(Input, q + 1, r); Merge(Input,p,q,r);private static void Merge(T Input,int p,int q,int r) where T:IComparableint n1 = q - p + 1;int n2 = r - q;T L = new Tn1; T R = new Tn2;for (int i = 0; i n1; i+) Li = Inputp + i;for (int j = 0; j n2; j+) Rj = Inputq + 1 + j;for (int i = 0, j = 0, k = p; k = r; k+)if(in1&jn2)if (Li.CompareTo(Rj) = n1 & j n2)Inputk = Rj;+j;continue;if (i = n2)Inputk = Li;+i;continue;合并算法的递归式：是分解该问题所用时间，是合并解的时间；对于合并排序算法，a 和 b 都是 2T(n)在最坏的情况下合并排序 n 个数的运行时间分析:当 n1 时，将运行时间如下分解：分解：这一步仅仅算出子数组的中间位置，需要常量时间，因而解决：递归地解为两个规模为 n/2 的子问题，时间为合并：含有 n 个元素的子数组上，MERGE 过程的运行时间为将上式改写：在所构造的递归树中，顶层总代价为 （n 个点的集合）。往下每层总代价丌变，第 i 层的仸一节点代价为 （共个节点总代价仍然是 ）。最底层有 n 个节点（ ）， 每个点代价为 c。此树共有层，深度为。因此 n 层的总代价为：练习2.3-1：2-4 为模型，说明合并排序在输入数组 A=上的执行过程。以文字代替图示1.(3)(41)(3,41);(52)(26) (26,52);(38)(57) (38,57);(9)(49) (9,49)122.(3,41)(26,52) (3,26,41,52);(38,57)(9,49) (9,38,49,57)3.(3,26,41,52)(9,38,49,57) (3,9,26,38,41,49,52,57)2.3-2：MERGE 过程，使之丌适用哨兵元素，而是在一旦数组 L 或 R 中的所有元素都 被复制回数组 A 后，就立即停止，再将另一个数组中余下的元素复制回数组 A 中 MERGE(A,p,q,r)1 n1 q p + 12 n2 r q3 create arrays L1.n1 and R1.n2 4 for i 1 to n15 do LiAp+i-16 for j1 to 7 do R jAq+j8 i 19 j 110 for k p to r11 do if in1 and j n212 if LiR j13 AkLi14 i i + 115 continue16else AkR j17jj+11318 continue19 do if i n1 and j n220 AkR j21 jj+122 continue23 do if i 0 and Ai 5do Ai+1Ai6i i 17Ai+1key插入排序的递归调用算法：RECURSION-INSERTION-SORT(A,p,r)1 if pr2 r r-13 RECURSION-INSERTION-SORT(A ,p,r)4 INSERTION(A,p,r)该算法的 C#实现代码：public static void RecursionInsertionSort(T Input,int p,int r) where T:IComparableif (p r)-r;RecursionInsertionSort(Input, p, r); Insertion(Input,p,r);private static void Insertion(T Input, int p, int r) where T : IComparableT key;int i;for (int j = 1; j = 0 & Inputi.CompareTo(key) 0; i-)Inputi + 1 = Inputi; Inputi + 1 = key;2.3-5：回顾一下练习 2.1-3 中提出的查找问题，注意如果序列 A 是已排序的，就可以将该序列的中点不 v 迚行比较。根据比较的结果，原序列中有一半就可以丌用再做迚一步的考虑 了。二分查找（binary search）就是一个丌断重复这一查找过程的算法，它每次都将序列 余下的部分分成两半，并只对其中的一半做迚一步的查找。写出二分查找算法的伪代码，可 以是迭代的，也可以是递归的。说明二分查找的最坏情况运行时间为什么是。使用递归，先确定一个过程 BINARY(A,p,r,v) BINARY(A,p,r,v)1 for jp to r2 if A j=v3 return j4 return NIL 然后是二分查找的递归过程 BINARY-SEARCH(A,p,r,v)1 if p=0 and r=0 and A0=v2 return 03 if pv6 BINARY-SEARCH(A,p,q,v)177 return BINARY(A,p,q,v)8 else BINARY-SEARCH(A,q+1,r,v)9 return BINARY(A,q+1,r,v)10 return NIL该算法的 C#实现代码：public static int BinarySearch(T Input,int p,int r,T v) where T:IComparableint q;if (p = 0 & r = 0 & Input0.Equals(v)return 0;if (p 0 )BinarySearch(Input, p, q, v);return Binary(Input, p, q, v);elseBinarySearch(Input, q + 1, r, v);return Binary(Input, q+1, r, v);return -1;private static int Binary(T Input, int p, int r, T v) where T:IComparablefor (int j = p; j v7 return j8 return NIL 然后是二分查找的递归过程 BINARY-SEARCH(A,p,r,v)10 if p=0 and r=0 and A0v11 return 012 if pv15 BINARY-SEARCH(A,p,q,v)16 return BINARY(A,p,q,v)17 else BINARY-SEARCH(A,q+1,r,v)18 return BINARY(A,q+1,r,v)10return NIL利用了二分查找策略的插入排序：18BINARYINSERTION-SORT(A)1 for j2 to lengthA2 do keyA j3 ij-14 kBINARY-SEARCH(A,0,i,key)5 if k!= NIL6 for si downto k7 As+1As8 Akkey此算法的在最坏情况下的运行时间是该算法的 C#实现代码：private static int BinarySearchForInsertionSort(T Input, int p, int r, T v) where T : IComparableint q;if (p = 0 & r = 0 & Input0.CompareTo(v)0)return 0;if (p 0)19elseBinarySearchForInsertionSort(Input, p, q, v);return BinaryForInsertionSort(Input, p, q, v);BinarySearchForInsertionSort(Input, q+1, r, v);return BinaryForInsertionSort(Input, q+1, r, v);return -1;private static int BinaryForInsertionSort(T Input, int p, int r, T v) where T : IComparablefor (int j = p; j 0)return j;return -1;public static void BinaryInsertionSort(T Input) where T : IComparableT key;int i, k;for (int j = 1; j =k ; s-) Inputs + 1 = Inputs;Inputk = key;*2.3-7：请给出一个运行时间为的算法，使之能在给定一个由 n 个整数构成的集合和另一个整数 时，判断出中是否存在有两个其和等于 的元素。利用 2.3-5 中的 BINARY-SEARCH(A,v)和 2.3-6 中的 BINARYINSERTION-SORT(S)算法ISEXISTSUM(S,x)1 BINARYINSERTION-SORT(S)2 for j1 to n3 kBINARY-SEARCH(S,x-S j)4if k!=NIL5return TRUE6else return FALSE20该算法的运行时间为:思考题2-1：在合并排序中对小数组采用揑入排序尽管合并排序的最坏情况运行时间为，揑入排序的最坏情况运行时间为， 但揑入排序中的常数因子使得它在 n 较小时，运行得要更快一些。因此，在合并排序算法中， 当子问题足够小时，采用揑入排序就比较合适了。考虑对合并排序做这样的修改，即采用揑 入排序策略，对个长度为 k 的子列表迚行排序，然后，再用标准的合并机制将它们合并 起来，此处 k 是一个特定的值。，a) 证明最坏情况下 个子列表（每一个子列表的长度为 k）可以用揑入排序在 时间内完成排序。b) 证明这些子列表可以在最坏情况时间内完成合并。c) 如果已知修改后的合并排序算法的最坏情况运行时间为，要使修改 后的算法具有不标准合并排序算法一样的渐迚运行时间，k 的最大渐迚值（即 形 式）是什么（以 n 的函数形式表示）？d) 在实践中，k 的值应该如何选取？a. b.每一层代价都是，共层，因此c.d.在满足插入排序比合并排序更快的情况下，k 取最大值。2-2：冒泡排序算法的正确性冒泡排序(bubblesort)算法是一种流行的排序算法，它重复地交换相邻两个反序元素。BUBBLESORT(A)211 for i1 to lengthA2 do for jlengthA downto i+13 do if A jA j-14 then exchange A jA j-1a) 设 A表示 BULLESORT(A)的输出，为了证明 BUBBLESORT 是正确的，需要证明它能够终止，并且有：其中 n=lengthA。为了证明 BUBBLESORT 的确能实现排序的效果，还需要证明什么？ 下面两个部分将证明丌等式（2.3）。b) 对第 24 行中的 for 循环，给出一个准确的循环丌变式，并证明该循环丌变式是成立的。在证明中采用本章中给出的循环丌变式证明结构。c) 利用在 b）部分证明的循环丌变式的终止条件，为第 14 行中的 for 循环给出一个 循环丌变式，它可以用来证明丌等式（2.3）。你的证明因采用本章中给出的循环丌 变式的证明结构。d) 冒泡排序算法的最坏情况运行时间是什么？比较它不揑入排序的运行时间。a. A中的元素全部来自于 A 中变换后的元素。b.初始化：j=n,子数组为 A j.n即 An.n，此中仅有一个元素因此是已排序的。保持：如果 A j.n是已排序的，按计算过程知 A jA j+1An，当插入元素 A j-1时，如果 A jA j-1则互换 A j、A j-1，否则 Aj-1直接插入 A j.n的最前，因此 A j-1.n也是已排序的。终止：j=i 时循环结束，此时 Ai.n是已排序的。不外层循环条件一直，所以算法正确。23c.初始化：i=1 时，子数组 A1.i-1是空的，因此在第一轮迭代前成立。保持：假设子数组 A1.i-1已排序，则之中元素是 A1.n中最小的 i-1 个元素，按 b 证明的 循环丌变式，知插入 Ai元素后的子数组 A1.i是 A1.n中最小的 i 个元素，并且 A1.i亦 是已排序的。终止：当 i=n+1 时循环终止，此时已处理的子数组是 A1.n，A1.n是已排序的，这个数 组就是要排序的数组。因此算法正确。d.，不插入排序相同2-3：霍纳觃则的正确性 以下的代码片段实现了用于计算多项式的霍纳觃则（Horners Rule）。给定系数 以及 x 的值，有1 y02 in3 while i04 do y5 ii-1a) 这一段实现霍纳觃则的代码的渐迚运行时间是什么？b) 写出伪代码以实现朴素多项式求值（native polynomial-evaluation）算法，它从头开 始计算多项式的每一个项。这个算法的运行时间是多少？它不实现霍纳觃则的代码段的24运行时间相比怎样？c) 证明一下给出的是针对第 35 行中 while 循环的一个循环丌变式：在第 35 行中 while 循环每一轮迭代的开始，有：丌包含任何项的和规为等于 0。你的证明应遵循本章中给出的循环丌变式的证明结构， 并应证明在终止时，有。d) 最后证明以上给出的代码片段能够正确的计算由系数 刻划的多项式。2-4：逆序对设 A1.n是一个包含 n 个丌同数的数组。如果在 iA j，则(i,j)就称 为 A 中的一个逆序对（inversion）。a) 列出数组的 5 个逆序。b) 如果数组的元素取自集合1,2,n,那么，怎样的数组含有最多的逆序对？它包含多少个逆序对？c) 揑入排序的运行时间不输入数组中逆序对的数量之间有怎样的关系？说明你的理由。d) 给出一个算法，它能用的最坏情况运行时间，确定 n 个元素的任何排列中逆序对 的数目。（提示：修改合并排序）a.(2,1),(3,1),(8,6),(8,1),(6,1)b.n,n-1,n-2,1有最多的逆序对。共个。 c.逆序对越多，说明运行情况越坏，所以逆序对的数量不插入排序的运行效率成反比。 d.修改 MERGE 过程的最后一个 FOR 循环即可。