アルゴリズム・イントロダクション第2章第1節の練習問題

2.1-1

2つの41の順序関係が維持されている(安定である)ことに注目するぐらい。

2.1-2

def insertion_sort(A):
    for j in range(1, len(A)):
        key = A[j]
        i = j-1
        while i >= 0 and A[i] < key:
            A[i+1] = A[i]
            i -= 1
        A[i+1] = key

2.1-3

def linear_search(A, v):
    for i in range(len(A)):
        if A[i] == v:
            return i
    return None

ループ不変式

第2-4行のforループが開始されるとき、部分配列 A[0 .. i-1] に目的の値 v は存在しない。

初期条件

はじめ、 i = 0 からループが開始される。このときに不変式が成り立つことを示す。 i = 0 のとき、部分配列 A[0 .. i-1] は要素をひとつも持たない。要素をひとつも持たないから、明らかに目的の値 v は存在しない。

ループ内条件

いま、 A[0 .. i-1] に目的の値 v は存在していないとする。もし、 A[i] が v ならば、このアルゴリズムは i を出力して終了するから次のループは実行されない。もし、A[i] が v でないならば、次のループが実行される。このとき、A[0 .. i-1] に v が存在せず、 A[i] も v ではないから、 A[0 .. i] に v は存在しない。よってループ不変式は維持される。

終了条件

ループが終了するとき、 i = len(A) である。このとき、ループ不変式にこのiを代入すると、部分配列 A[0 .. len(A)-1] に目的の値 v は存在しないことが分かる。ところが、部分配列 A[0 .. len(A)-1] は A そのものであるから、 A に目的の値 v が存在しなかったということが言える。

2.1-4

入力：長さnの数列 A = {a1, a2, ..., an} と B = {b1, b2, ..., bn}。ただし ai, bi (1 <= i <= n) は 0 または 1。

出力：A, Bをそれぞれn桁の2進数と見なしたとき、その和を2進数の形式で格納した長さ n+1 の数列 C。

def add(A, B):
    n = len(A)
    C = [0] * (n+1)
    carry = 0
    for i in range(n):
        s = A[i] + B[i] + carry
        if s >= 2:
            s -= 2
            carry = 1
        else:
            carry = 0
        C[i] = s
    C[n] = carry
    return C