算法导论2.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 791 阅读时长 ≈ 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