■

いま問題1.20か、、1年くらい掛かりそうなペースだなこりゃ。

問題 1.20

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

a) gcdの正規順序評価での展開 (要は式を評価するまえに展開出来る所は全て展開）
※ifの条件部は#f、#tの判定に計算しているだろうから計算結果を表示
(gcd 206 40)

(if (= 40 0)
    206
    (gcd 40 (remainder 206 40))))
※ifの条件部(= 40 0)は#fなので内部は計算せず

(if (= 40 0)
    206
    (if (= 6 0)
        40
        (gcd (remainder 206 40) (remainder 40 (remainder 206 40)))))
※ifの条件部(= 6 0)は#fなので内部は計算せず

(if (= 40 0)
    206
    (if (= 6 0)
        40
        (if (= 4 0)
            (remainder 206 40)
            (gcd (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))))
※ifの条件部(= 4 0)は#fなので内部は計算せず

(if (= 40 0)
    206
    (if (= 6 0)
        40
        (if (= 4 0)
            (remainder 206 40)
            (if (= 2 0)
                (remainder 40 (remainder 206 40))
                (gcd 
                     (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
                     (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
))))
※ifの条件部(= 2 0)は#fなので内部計算はせず

(if (= 40 0)
    206
    (if (= 6 0)
        40
        (if (= 4 0)
            (remainder 206 40)
            (if (= 2 0)
                (remainder 40 (remainder 206 40))
                (if (= 0 0)
                    (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
                    (gcd 省略)
※ifの条件部は#tなのでif文のthen, elseを選択

⇒(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
⇒(remainder 6 (remainder 40 6))
⇒(remainder 6 4)
⇒2
remainderの計算回数は7回

b) 作用的順序

(gcd 206 40)
⇒(if (= 40 0)
    206
    (gcd 40 (remainder 206 40)))
⇒(gcd 40 (remainder 206 40))
⇒(gcd 40 6)
⇒(if (= 6 0
    40
    (gcd 6 (remainder 40 6)))
⇒(gcd 6 (remainder 40 6))
⇒(gcd 6 4)
⇒(if (= 4 0)
    6
    (gcd 4 (remainder 6 4)))
⇒(gcd 4 (remainder 6 4))
⇒(gcd 4 2)
⇒(if (= 2 0)
    4
    (gcd 2 (remainder 4 2)))
⇒(gcd 2 (remainder 4 2))
⇒(gcd 2 0)
⇒(if (= 0 0)
    2
    (gcd 0 (remainder 2 0)))
⇒2

問題 1.21

(define (smallest-divisor n)
  (define (find-divisor n test-divisor)
	(cond *1
  (define (square x) (* x x))
  (find-divisor n 2))

(smallest-divisor 199)
199
(smallest-divisor 1999)
1999
(smallest-divisor 19999)
7

*1:> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor 1))))) (define (divides? a b) (= (remainder b a) 0