《算法导论》第二章习题解答

如果错误，或者有更好的方法，欢迎大家指正

2-1：插入排序

2-1-1：描述数组A = {31,41,59,26,41,58}插入排序过程

　　　　解： 1、　　31 41 59 26 41 58

　　　　　　 2、　　31 41 59 26 41 58

　　　　　　 3、　　26 31 41 59 41 58

　　　　　　 4、　　26 31 41 41 59 58

　　　　　　 5、　　26 31 41 41 58 59

2-1-2：写出插入排序（非升序）伪代码

　　　　解： INSERTION_SORT(A)

　　　　　　　　for i <- 2 upto length(A)

　　　　　　　　　　key <- A[i]

　　　　　　　　　　j <- i-1

　　　　　　　　　　while A[j] < key and j>0

　　　　　　　　　　　　A[j+1] <- A[j]

　　　　　　　　　　　　i <- i-1

　　　　　　　　　　A[i+1] <- key

　　　　　　　　endfor

2-1-3：考虑下面的查找问题

　　　　输入：一列数A=<a1，a2，….，an>和一个值v

　　　　输出：下标i，使得v = A[i]，如果v不在A中，输出NIL

　　　　写出针对这个问题的线性查找伪代码，它顺序地扫描整个序列以查找v，利用循环不变式说明正确性

　　　　　　解： FindValue(A[1…..n],v)

　　　　　　　　　　for i <-1 upto n

　　　　　　　　　　　　if A[i] = v then return i

　　　　　　　　　　endfor

　　　　　　　　　　return NIL

　　　　　　初始化：在迭代第一轮之前，是正确的，因为它没有进行任何查找工作，也没有返回任何数值

　　　　　　保持：　假设在第k次迭代是正确的，那么有两种情况，在k的时候算法已经结束了，可知返回的结果是正确的，如果没有返回那么说明前面k次没有　　　　　　　　　　匹配到v，那么k+1次迭代的时候也是正确的

　　　　　　终止：有两种情况，在中途终止，即找到了i，在最后终止，没有找到i，返回NIL

2-1-4：有两个各存放在数组A和B的n位二进整数，考虑他们的相加问题，两个整数的和以二进制形式存放在局偶n+1个元素的数组C中，请给出这个问题的形式化描　　　　述，并写出伪代码

　　　　　　解：形式化描述： A[1…..n],其中A[i] =0 或者 = 1， B[1…..n],其中B[i]=0 或者B[i]=1, C[i….n+1],其中C[i]=0 或者C[i]=1,

　　　　　　　　　　add描述： C[i] = (A[i]+B[i]+flag)%2, 其中：如果C[i-1] <2, flag=0，反之 flag=1, (当i=1时，flag=0)

　　　　　　　　伪代码如下：

　　　　　　　　BINARY_ADD(A[1….n],B[1…n],C[1…..n+1])

　　　　　　　　　　flag <- 0

　　　　　　　　　　for i <- 1 upto n

　　　　　　　　　　　　value <- A[i] + B[i] + flag

　　　　　　　　　　　　C[i] <- value mod 2

　　　　　　　　　　　　if value < 2 then flag <- 0

　　　　　　　　　　　　else then flag <- 1

　　　　　　　　　　endfor

　　　　　　　　　　C[n+1] <- flag

2-2：算法分析

2-2-1：　　解： Θ(n³)

2-2-2：　　解：伪代码：

　　　　　　　　SELECTION_SORT(A[1…..n])

　　　　　　　　for i <- 1 upto n-1

　　　　　　　　　　key <- A[i]

　　　　　　　　　　Index <- i

　　　　　　　　　　for j <- i+1 upto n

　　　　　　　　　　　　if A[j] < key

　　　　　　　　　　　　　　key <- A[j]

　　　　　　　　　　　　　　Index <- j

　　　　　　　　　　A[Index] <- A[i]

　　　　　　　　　　A[i] <- key

　　　　　　　　end

　　　　　　　　循环不变式：在迭代k次后，A[1…k]已经按非降序排列好，且A[k+1….n]比A[1…k]中的元素都大

　　　　　　　　因为在执行n-1次循环之后，最后只剩下最后一个元素，所以它是剩下的所以元素中最小的

　　　　　　　　最佳和最坏情况都是 Θ(n²)

2-2-3　　解答：假定每个元素被搜索的概率为p,则有pn<1(因为有可能搜索的元素不在数组中)，那么平均查找的元素数PFind为1/p *(1+….+n) + (1-pn)*n,　　　　　　　　最坏的情况为n，我们很容易获知PFind最小的时候为n/2,最大的时候为n，所以平均和最坏情况运行时间都为Θ(n)

2-2-4　　解答：我们可以首先设计一个针对该问题的一个特定输入，使得这个特定输入是最好的情况，然后不断修改算法，使其针对该特列的运行时间达到最佳

2-3 算法设计

2-3-1：　　解：　　　　　　　　　3 9 26 38 41 49 52 57

　　　　　　　　　　　　　　　　3 26 41 52　　　　　　9 38 49 57

　　　　　　　　　　　　　　 3 41　　　26 52　　 38 57　　 9 49　

　　　　　　　　　　　　　　3　　41　　52　　26　　38　　57　　9　　49

2-3-2：　　解：MERGE(A[1…..n], A, p, q, r)

　　　　　　　　n1 <- q-p+1

　　　　　　　　n2 <- r-q

　　　　　　　　create array L[1….n1] and R[1…..n2]

　　　　　　　　for i <- 1 upto n1

　　　　　　　　　　L[i] <- A[p+i-1]

　　　　　　　　for i <- 1 upto n2

　　　　　　　　　　R[i] <- A[q+i]

　　　　　　　　i <- 1, j <- 1

　　　　　　　　for k <- p upto r

　　　　　　　　　　if L[i] < R[j]

　　　　　　　　　　　　then A[k] <- L[i]

　　　　　　　　　　　　　　　i <- i+1

　　　　　　　　　　　　　　　if i = n1+1

　　　　　　　　　　　　　　　for k <- k+1 upto r

　　　　　　　　　　　　　　　　　A[k] <- R[j]

　　　　　　　　　　　　　　　　　j <- j+1

　　　　　　　　　　　　　　　break

　　　　　　　　　　　　　else A[k] <- R[i]　　　　

　　　　　　　　　　　　　　　j <- j+1

　　　　　　　　　　　　　　　if j = n2+1

　　　　　　　　　　　　　　　for k <- k+1 upto r

　　　　　　　　　　　　　　　　　A[k] <- L[i]

　　　　　　　　　　　　　　　　　i <- i+1

　　　　　　　　　　　　　　　break

2-3-3：　　解：当n=2时，有T(2) = nlgn = 2*lg2 = 2 成立

　　　　　　　假设n=2^k时成立，即有T(2^k) = 2^{k *}lg(2^k) = k*2^k

　　　　　　　当n = 2^k+1时，有：T(2^k+1) = 2*T(2^k+1/2) + 2^k+1= 2*k*2^k +2^k+1 = (k+1)*2^k+1

　　　　　　　综上得证

2-3-4：　　解：　　T(n) = Θ(1)　　n=1 or 2

　　　　　　　　　　　　　　=　　T(n-1)+ Θ(n)　　n>2

2-3-5：　　解：伪代码如下：

　　　　　　　　BINARY-SEARCH(A[1….n],v)

　　　　　　　　b <- length(A)

　　　　　　　　a <-1

　　　　　　　　while a>b

　　　　　　　　　　n <- (a+b)/2

　　　　　　　　　　if A[n] = v

　　　　　　　　　　　　return n

　　　　　　　　　　else if A[n] > v

　　　　　　　　　　　　b = n

　　　　　　　　　　else

　　　　　　　　　　　　a = n

　　　　　　　　　很显然算法在最坏情况下运行时间为Θ（lgn）

2-3-6:　　解：不能，因为虽然对于某次迭代，查找的次数变为了lgj，但是移动复制的次数认为j

2-3-7　　　解：算法思路：首先对S[1…n]进行非降序排序，然后设置两个指向标i=1,j=n,执行下面的操作:

　　　　　　　　　　S[i] + S[j] = X，　　返回true

　　　　　　　　　　　　　　　　< X,　　i = i+1

　　　　　　　　　　　　　　　　> X,　　j = j-1

　　　　　　　　　　如果 i>j 返回false

　　　　　　　　正确性说明：很显然，如果S[i] + S[j]< X，则如果存在一个a，使得S[a] + S[j] = x，那么这个S[a]一定要大于s[j],换句话说a要大于i，另外　　　　　　　　一种情况是存在一个a，使得S[i] + S[a] = x，那么这个S[a]一定要大于s[j],换句话说a要大于j，下面我们说明第二种情况不存在，在执行到j　　　　　　　　　　前，因为偏移量总是1，所以必然会执行到a，这个时候在i之前的所有数，与S[a]相加是要小于X的，根据上面的公式，会移动前半段，即变动i，直　　　　　　　　到到达i,所以不存在，同理可以说明>X的情况，因此如果算法返回false的话，算法可以验证那么对于任意的i,都不存在j使得其和等于X

　　　　　　　　时间复杂度分析：排序为Θ(nlgn)，之后为Θ(n)，算法的时间复杂度为Θ(nlgn)

思考题