《算法导论》第二章-第1节_练习（参考答案）

Exercise 2.1-1

Using figure 2.4 as a model, illustrate the operations of Insertion-Sort on the array A=⟨31,41,59,26,41,58⟩ .

插入排序思想：在遍历第二到最后元素过程中，给这个元素挪出正确的位置。

Exercise 2.1-2

Rewrite the Insertion-Sort procedure to sort into nonincreasing instead of nondecreasing order.

非升序排列：

for j = 2 to A.length
    key = A[j]
    i = j - 1
while i > 0 and A[i] < key
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = key

Exercise 2.1-3

Consider the searching problem:

Input: A sequence of n numbers A=⟨a1,a2,…,an⟩ and a value ν .

Output: And index i such that ν=A[i] or the special value NIL if ν does not appear in A

Write the pseudocode for linear search, which scans through the sequence, looking for ν . Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

线性查找伪代码：

SEARCH(A, v):
for i = 1 to A.length
if A[i] == v
return i
return NIL

SEARCH-RECURSIVE(A, size, v) //A[1..size]
if A.size > 0
if A[size] == v
return A.size
return SEARCH-RECURSIVE(A, size-1, v)
return NIL

SEARCH-RECURSIVE 递归式： T(n)=T(n−1)+Θ(1)

循环不变式证明：

查找过程中， A[1..i−1] 不包含 ν ，则继续查找，否则停止查找返回下标。 A[1..i−1] 是已经查找过得从位置 1 到 i−1 的元素，确定不含有 ν 。

初始化：

迭代之前，循环不等式成立。因为子数组是空的，没有找到，还要继续。

保持：

如果 A[1..i−1] 不包含 ν . 我们比较 A[i] 和 ν. 如果相等，则返回 i ，否则继续下一步。已知 A[1..i−1] 不包含 ν ，且 A[i] 不等于 ν , 那么 A[1..i] 中不包含 ν ，进行下一步。

终止：

当 i>A.length . 我们知道 A 里面肯定不包含 ν ，所以我们返回 NIL .

Exercise 2.1-4

Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B . The sum of the two integers should be stored in binary form in an (n+1) -element array C . State the problem formally and write pseudocode for adding the two integers.

形式化描述：

Input: An array of booleans A=⟨a1,a2,…,an⟩​ , an array of booleans B=⟨b1,b2,…,bn⟩​ , each representing an integer stored in binary format (each digit is a number, either 0 or 1, least-significant digit first) and each of length n​ .

Output: An array C=⟨c1,c2,…,cn+1⟩ where ci=[ai+bi+carry(ai−1+bi−1)]%2

伪代码：（pseudocode）

ADD-BINARY(A, B):
  C = new integer[A.length + 1]

  carry = 0
for i = 1 to A.length
      C[i] = (A[i] + B[i] + carry) % 2  // remainder
      carry = (A[i] + B[i] + carry) / 2 // quotient
  C[i] = carry

return C