sicpマラソン4日目

sicp scheme
[メモ]
  • 線形再帰的プロセスでべき乗計算＝ステップ数はθ(n)、スペースはθ(n)必要 (1.2.4)
  • 線形反復的プロセスでべき乗計算＝ステップ数はθ(n)、スペースはθ(1)必要 (1.2.4)
  • 逐次平方を使用するとステップ数はθ(log n) (1.2.4)
  • 反復的アルゴリズム設計時に不変量を考えると便利 (1.2.4)
[演習問題]

1.16

(define (fast-expt2 b n)
        (fast-extp2-iter b n 1))
(define (fast-expt2-iter b n a)
        (cond ((= n 0) a)
              ((even? n) (fast-expt2-iter (* b b) (/ n 2) a))   ## (b^(n/2))^2 = (b^2)^(n/2)
              (else (fast-expt2-iter b (- n 1) (* a b)))))

1.17

(define (double x) (* x 2))
(define (halve x) (/ x 2))     ## xが偶数の時
(define (fast-mult a b)
        (cond ((= b 0) 0)
              ((even? b) (double (fast-mult a (halve b))))
              (else (+ a (fast-mult a (- b 1))))))

1.18 ステップ数はθ(n)のままだが、スペースはθ(n)からθ(1)に改善

(define (fast-mult2 a b)
        (fast-mult2-iter a b 0))
(define (fast-mult2-iter a b c)
        (cond ((= b 0) c)
              ((even? b) (fast-mult2-iter (double a) (halve b) c))
              (else (fast-mult2-iter a (- b 1) (+ c a)))))

1.19 Fibonacci数の一般化

T(p,q):(a,b)←(bq+aq+ap,bp+aq)
※Fibonacci数計算の状態変数の変換 T:(a,b)←(a+b,a) はT(0,1)
T(p,q)^2:(a,b)←((bp+aq)q+(bq+aq+ap)q+(bq+aq+ap)p,(bp+aq)p+(bq+aq+ap)q)
              ←(b(q^2+2pq)+a(q^2+2pq)+a(q^2+p^2),b(q^2+2pq)+a(q^2+p^2))
              ←(bq'+aq'+ap',bp'+aq')
p',q'は (p',q')=(p^2+q^2,q^2+2pq)と表せる
(define (fib n)
        (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
        (cond ((= count 0) b)
              ((even? count) (fib-iter a
                                       b
                                       (+ (* p p) (* q q))
                                       (+ (* q q) (* 2 p q))
                                       (/ count 2)))
              (else (fib-iter (+ (* b q) (* a q) (* a p))
                              (+ (* b p) (* a q))
                              p
                              q
                              (- count 1)))))