算法导论2.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 855 阅读时长 ≈ 1 分钟

2.1-1

\(\begin{aligned} &[],[31,41,59,26,41,58]\\ &[\underline{31}],[41,59,26,41,58]\\ &[31,\underline{41}],[59,26,41,58]\\ &[31,41,\underline{59}],[26,41,58]\\ &[\underline{26},31,41,59],[41,58]\\ &[26,31,41,\underline{41},59],[58]\\ &[26,31,41,41,\underline{58},59],[] \end{aligned}\)

2.1-2

初始化：一开始时求了前\(0\)个元素的和，也就是说不包含任何数。

保持：在迭代到第\(i\)个元素时，\(sum\)是数组\(A[1:i-1]\)的元素之和。添加上\(A[i]\)后，\(sum\)就成为了数组\(A[1:i]\)的元素之和。

终止：最终，通过下标\(i\)迭代了每一个元素，只要超过了长度\(n\)，循环终止。因此整个算法是正确的。此时就有\(sum=A[1:n]\)。

2.1-3

1
2
3
4
5
6
7
8
INSERTION-SORT(A, n)
  for i = 2 to n
    key = A[i]
    j = i – 1
    while j > 0 and A[j] < key
      A[j + 1] = A[j]
      j = j – 1
    A[j + 1] = key

这时候在插入的元素的位置，右边全是比它小的，左边全是比它大的。

2.1-4

1
2
3
4
5
LINEAR-SEARCH(A, n, x)
  for i = 1 to n
    if A[i] == x
      return i
  return NIL

循环不变量：\(A[1:i-1]\)中都不包含数\(x\)。

初始化：迭代开始前处理的是空数组，并没有发现和\(x\)的元素。

保持：在数组\(A[1:i-1]\)没有发现\(x\)的基础上，判断\(A[i]\)是否和\(x\)相等。如果相等，那么及时返回下标\(i\)，循环不变量\(A[1:i-1]\)依旧不包含\(x\)；否则说明数组\(A[1:i]\)也没有发现\(x\)。

终止：如果找到了一个\(i\)使得\(A[i]=x\)，那么算法立刻返回当前下标，算法提前结束。当直到循环结束时，下标\(i\)的值已经为\(n+1\)，这说明数组\(A[1,n]\)并没有发现\(x\)，故返回NIL，算法正确结束。

2.1-5

1
2
3
4
5
6
7
8
9
10
ADD-BINARY-INTEGERS(A, B, n)
  let C[0 : n] be new arrays
  carry = 0
  for i = 0 to n - 1
    sum = carry + A[i] + B[i]
    C[i] = sum % 2
    carry = floor(sum / 2)
  C[n] = carry
  return C