知识点

1. 循环不变式
   需要证明个性质：
   1. 初始化：循环的第一次迭代之前，它为真。
   2. 保持：如果循环的末次迭代之前它为真，那么下次迭代之前它仍为真
   3. 终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法的正确性。

习题

1.1

31，41，59，26，41，58
31，41，59，26，41，58
31，41，59，26，41，58
26，31，41，59，41，58
26，31，41，41，59，58
26，31，41，41，58，59
1.2

INSERTION-STOP(A)
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

1-3

LINEARSEARCH-STOP(A,u)
    for i = 1 to A.length
        key = A[i]
        if key == u 
            return i
    return nil

1-4

形式化描述：对于二进制的相加，是低位数相加，为2进一位，当前位为当前位-2，进的一位参加下一位的相加。

BINARYADD-STOP(A,B)
    C[1] = 0
    for i = 1 to n
        keyc = C[i]
        keya = A[i]
        keyb = B[i]
        sum = keyc + keya + keyb
        if sum > 1 
            C[i+1] =1
            C[i] = sum - 2
        else
            C[i+1] = 0
            C[i] = sum
    return C