Serendip

Web Studio

問題1.19

p' : (+ (* p p) (* q q))
q' : (+ (* 2 p q) (* q q))

問題1.20

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

正規順序の置き換えの場合。
赤字部分が実行される remainder。
remainder を rem と省略表記している。
18回。

(gcd 206 40)

(if (= 40 0) ; #f
    206
    (gcd 40 (rem 206 40)))

(if (= (rem 206 40) 0) ; #f
    40
    (gcd (rem 206 40) (rem 40 (rem 206 40))))

(if (= (rem 40 (rem 206 40)) 0) ; #f
    (rem 206 40)
    (gcd (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40)))))

(if (= (rem (rem 206 40) (rem 40 (rem 206 40))) 0) ; #f
    (rem 40 (rem 206 40))
    (gcd (rem (rem 206 40) (rem 40 (rem 206 40))) (rem (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40))))))

(if (= (rem (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40)))) 0) ; #t
    (rem (rem 206 40) (rem 40 (rem 206 40)))
    (gcd (rem (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40)))) (rem (rem (rem 40 (rem 206 40))) (rem (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40)))))))

;(rem (rem 206 40) (rem 40 (rem 206 40)))
;(rem 6 (rem 40 6))
;(rem 6 4)
2

作用的順序の置き換えの場合。
4回。

(gcd 206 40)
(if (= 40 0) ; #f
    206
    (gcd 40 (rem 206 40)))

(if (= 40 0) ; #f
    206
    (gcd 40 6))

(if (= 6 0) ; #f
    40
    (gcd 6 (rem 40 6)))

(if (= 6 0) ; #f
    40
    (gcd 6 4))

(if (= 4 0) ; #f
    6
    (gcd 4 (rem 6 4)))

(if (= 4 0) ; #f
    6
    (gcd 4 2))

(if (= 2 0) ; #f
    4
    (gcd 2 (rem 4 2)))

(if (= 2 0) ; #f
    4
    (gcd 2 0))

(if (= 0 0) ; #t
    2
    (gcd 2 0))

2

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

posted with amazlet at 08.11.07

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

Amazon.co.jp で詳細を見る