SICP

SICP を読んでみる #10 第一章 pp.25-27

問題解答

問1.17, 1.18
1.17 をやっていたらついでに 1.18 もやってしまったのでまとめて回答。

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

(define (double a)
  (+ a a))

(define (halve a)
  (/ a 2))

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

  (mult-iter a n 0))

正直、ビット演算とシフトを使いたい。。。

問1.19
プログラム的にやることはこれまでと変わらないのと、Fibonacchi 数の計算についての内容が主なのでパス。

本文

1.2.5 最大公約数
Euclid のアルゴリズムを使用して最大公約数(GCD)を求める

問題解答

問1.20

(gcd 206 40)
((gcd 40 (remainder 206 40)))
(((gcd (remainder 206 40) (remainder 40 (remainder 206 40))))))
:
:

正規順序評価を用いると gcd が延々展開されてしまって正常に評価がおこなわれない
→答え合わせをしたらそんなことなかった。めんどくさがらずにきちんと展開すればできた。

作用的順序評価は以下の通り

(gcd 206 40)
(gcd 40 (remainder 206 40))
(gcd 40 6)
(gcd 6 (remainder 40 6))
(gcd 6 4)
(gcd 4 (remainder 6 4))
(gcd 4 2)
(gcd 2 (remainder (4 2))
(gcd 2 0)

よって、remainder は 4 回呼ばれる。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です