アルゴリズム・イントロダクション第2章第1節の練習問題 - TopCoderとJ言語と時々F#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 .
