4章「正しいプログラムを書く」- 珠玉のプログラミング（Programming Pearls）
珠玉のプログラミングの4章。
偶然にも OOSC でも表明の部分を読んでいたので補足できて良かった。
4.6.1
- 0 による割り算
- 割り算は中間値を求めるところでのみ使われる。必ず定数 2 で割るので起きない。
- 配列の添え字範囲を超える
- 有効な配列の添え字は 0 ... n - 1 である
- 配列の参照は m = (l + u) / 2 でのみ発生
- 初期値 l = 0, u = n - 1
- case 1 から l は (n + 1) / 2 を超えない
- case 3 から u は (n - 1) / 2 を超えない
- l > u の状態で m で参照することはない
4.6.2
分からなかったので答えを見た。
x[m] == t の場合でも u をずらしていって l + 1 = u になるまで繰り返すのが肝
4.6.4
ループが終わる条件は2つ
・ l > u になったとき
・ x[m] = t がみつかったとき
1つめは最後まで調べた例なので log2(n)。
2つめは平均して log2(n) 。
4.6.5
分からない。この問題はすごいな。
4.6.6
豆は以下の4通りで取り出される。
●○ → 黒-1 → 計 -1
●● → 白-2,黒+1 → 計 -1
○● → 黒-1 → 計 -1
○○ → 黒-1 → 計 -1
どの場合も必ず豆が1つ減るので必ず終了する。
予想は出来ないと思ったが間違いだった。偶数奇数で白豆は分かる。
4.6.7
(x, y) が与えられたら k=i/2 からスタートして2分探索。
4.6.8
分からなかった。9章で詳細を追う。
4.6.9
(1)
入力時: a, b, c は長さ n の配列
出力時: どの a[k] 0 <= k < n に対しても a[k] = b[k] + c[k] が成り立つ
ループの不変表明は i よりも小さい k に関して a[k] = b[k] + c[k] が成り立つ
ループは k = 0 から k = n - 1 から逐次近似で範囲を広げていき結果として出力が正しくなる
(2)
入力時 x は長さが n (1 以上) の配列
出力時 max に x の中の最大値が入っている
不変表明は x[0] 〜 x[i - 1] までの最大値が max に入っていること
(3)
入力時: x は n の配列
出力時: p は x 中に t が現れる最初の位置。なければ -1
不変表明: (2)と同様
4.6.10
l > u ではなく l >= u とした場合変化表明が減らないのでダメ。
4.6.11
略。
4.scm
;; Programming Pearls Chapter 4 (import (rnrs) (mosh test)) (define (binary-search vec t) (let loop ([l 0] [u (- (vector-length vec) 1)]) (if(> l u) -1 (let* ([m (div (+ l u) 2)] [vm (vector-ref vec m)]) (cond [(< vm t) (loop (+ m 1) u)] [(= vm t) m] [else (loop l (- u 1))]))))) (test-eq -1 (binary-search '#(2 4 6 8 10 12 14 16) 5)) (test-eq 2 (binary-search '#(2 4 6 8 10 12 14 16) 6)) ;; 4.6.2 (define (binary-search-first vec t) (let loop ([l -1] [u (vector-length vec)]) (if(= u (+ l 1)) (if (or (>= u (vector-length vec)) (not (= (vector-ref vec u) t))) -1 u) (let* ([m (div (+ l u) 2)] [vm (vector-ref vec m)]) (cond [(< vm t) (loop m u)] [else (loop l m)]))))) (test-eq -1 (binary-search-first '#(2 4 6 8 10 12 14 16) 5)) (test-eq 2 (binary-search-first '#(2 4 6 8 10 12 14 16) 6)) (test-eq 3 (binary-search-first '#(2 4 6 8 8 8 10 12 14 16) 8)) ;; 4.6.3 (define (binary-search-rec vec t) (define (rec l u) (if(> l u) -1 (let* ([m (div (+ l u) 2)] [vm (vector-ref vec m)]) (cond [(< vm t) (rec (+ m 1) u)] [(= vm t) m] [else (rec l (- u 1))])))) (rec 0 (- (vector-length vec) 1))) (test-eq -1 (binary-search-rec '#(2 4 6 8 10 12 14 16) 5)) (test-eq 2 (binary-search-rec '#(2 4 6 8 10 12 14 16) 6)) (test-results)
珠玉のプログラミング—本質を見抜いたアルゴリズムとデータ構造
posted with amazlet at 09.07.11
ジョン ベントリー
ピアソンエデュケーション
売り上げランキング: 5607
ピアソンエデュケーション
売り上げランキング: 5607
