算法导论第二章答案

《算法导论第二章答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、此笔记尚未定稿如果问题和建议请联系zhangshuijing@msn.com欢迎指教第二章算法入门由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。另，思考题2-3关于霍纳规则，有些部分没有完成，故没把解答写上去，我对其c问题有疑问，请有解答方法者提供个意见。给出的代码目前也仅仅为解决问题，没有做优化，请见谅，等有时间了我再好好修改。插入排序算法伪代码INSERTION-SORT(A)1forj←2tolength[A]2dokey←A[j]3InsertA[j]intothesortedseque

2、nceA[1..j-1]4i←j-15whilei>0andA[i]>???6doA[i+1]←A[i]7i←i−18A[i+1]←keyC#对揑入排序算法的实现:publicstaticvoidInsertionSort(T[]Input)whereT:IComparable{Tkey;inti;for(intj=1;j=0&&Input[i].CompareTo(key)>0;i--)Input[i+1]=Inpu

3、t[i];Input[i+1]=key;}}揑入算法的设计使用的是增量（incremental）方法：在排好子数组A[1..j-1]后，将元素A[j]揑入，形成排好序的子数组A[1..j]这里需要注意的是由于大部分编程语言的数组都是从0开始算起，这个不伪代码认为的数组的数是第1个有所丌同，一般要注意有几个关键值要比伪代码的小1.如果按照大部分计算机编程语言的思路，修改为：INSERTION-SORT(A)1forj←1tolength[A]2dokey←A[j]3i←j-13此笔记尚未定稿如果问题和建议请联系zhang

4、shuijing@msn.com欢迎指教4whilei≥0andA[i]>???5doA[i+1]←A[i]6i←i−17A[i+1]←key循环丌变式(LoopInvariant)是证明算法正确性的一个重要工具。对于循环丌变式，必须证明它的三个性质：初始化(Initialization)：它在循环的第一轮迭代开始之前，应该是正确的。保持(Maintenance)：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也是正确的。终止(Termination)：当循环结束时，丌变式给了我们一个有用的性

5、质，它有助于表明算法是正确的。运用循环丌变式对插入排序算法的正确性进行证明：初始化：j=2，子数组A[1..j-1]只包含一个元素A[1],显然它是已排序的。保持：若A[1..j-1]是已排序的，则按照大小确定了插入元素A[j]位置之后的数组A[1..j]显然也是已排序的。终止：当j=n+1时，退出循环，此时已排序的数组是由A[1],A[2],A[3]…A[n]组成的A[1..n]，此即原始数组A。练习3141592641582.1-1：以图2-2为模型，说明INSERTION-SORT在数组A=<31,41,59,2

6、6,41,58>上的执行过程。3141592641583此笔记尚未定稿如果问题和建议请联系zhangshuijing@msn.com欢迎指教3141592641582631415941582631414159582631414158592.1-2：重写过程INSERTION-SORT，使之按非升序（而丌是按非降序）排序。INSERTION-SORT(A)1forj←2tolength[A]2dokey←A[j]3InsertA[j]intothesortedsequenceA[1..j-1]4i←j-15whilei>

7、0andA[i]和一个值v输出：下标i，使得v=A[i]，戒者当v丌在A中出现时为NIL。写出针对这个问题的现行查找的伪代码，它顺序地扫描整个序列以查找v。利用循环丌变式证明算法的正确性。确保所给出的循环丌变式满足三个必要的性质。LINEAR-SEARCH(A,v)1fori←1tolength[A]2ifv=A[i]3returni3此笔记尚未定稿如果问题和建议请联系zhang

8、shuijing@msn.com欢迎指教4returnNIL现行查找算法正确性的证明。初始化：i=1，子数组为A[1..i]，只有一个元素A[1],如果v=A[1]就返回1,否则返回NIL，算法显然是正确的。保持：若算法对数组A[1..i]正确，则在数组增加一个元素A[i+1]时，只需要多作一次比较，因此显然对A[1..i+1]也