Serendip

Web Studio

問題1.16

不変量 ab^n について、答えを見れば「ああ、そういうことか」と解るけれども、自分の頭ではこのような計算が思い浮かばない…

(define (fast-expt-iter b n)
  (expt-iter b n 1))

(define (expt-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (expt-iter (* b b) (/ n 2) a))
        (else (expt-iter b (- n 1) (* b a)))))

問題1.17

これは、すぐに解けた。
a を 2倍、b を2分する毎に計算が半分進む。

(define (double n)
  (* n 2))

(define (halve n)
  (/ n 2))

(define (even? n)
  (= (remainder n 2) 0))

(define (mul a b)
  (cond ((= b 0) 0)
        ((even? b) (mul (double a) (halve b)))
        (else (+ (mul (double a) (halve (- b 1))) a))))

問題1.18

不変量を何にすればいいのかがどうしても思いつかない…
答えから不変量だけを調べて問題を解いた。

(define (mul a b)
  (mul-iter a b 0))

; ab+n を不変量とする
; bが偶数時 => 2a x (b-1)/2 + n
; bが奇数時 => a x (b-1) + (a+n)

(define (mul-iter a b n)
  (cond ((= b 0) n)
        ((even? b) (mul-iter (double a) (halve b) n))
        (else (mul-iter a (- b 1) (+ a n)))))

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る