SICP問題1.16

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

SICP問題1.17

とりあえず必要そうな手続きを定義。

(define (square n)
  (* n n))
(define (double n)
  (+ n n))
(define (halve n)
  (/ n 2))
(define (even? n)
  (= (remainder n 2) 0))

答え

(define (my-* x y)
  (cond ((= y 0) 0)
        ((even? y) (double (my-* x (halve y))))
        (else (+ x (my-* x (- y 1)))))
)

SICP問題1.18

(define (square n)
  (* n n))
(define (double n)
  (+ n n))
(define (halve n)
  (/ n 2))
(define (even? n)
  (= (remainder n 2) 0))

; 1.16 のべき乗
(define (my-expt b n)
  (define (my-iter-expt b n a)
    (cond ((= n 0) a)
          ((even? n) (my-iter-expt (square b) (/ n 2) a))
          (else (my-iter-expt b (- n 1) (* b a))))
  )
(my-iter-expt b n 1)
)
; 1.17 の乗算
(define (my-* x y)
  (cond ((= y 0) 0)
        ((even? y) (double (my-* x (halve y))))
        (else (+ x (my-* x (- y 1)))))
)

これらの結果を使用して加算, 二倍, 二分による対数的ステップ数の二つの整数を乗算を行う反復的プロセスを工夫せよ。とのことなので

(define (my-iter-* x y)
  (define (iter x y a)
    (cond ((= y 0) a)
          ((even? y) (iter (double x) (halve y) a))
          (else (iter x (- y 1) (+ a x))))
  )
  (iter x y 0)
)

んーと1.16関係ないような気が…。

SICP問題1.19

T^1 の時の a
  bq + aq + ap
T^2 の時の a
(bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
= bpq + a(q^2) + b(q^2) + a(q^2) + apq + bpq + apqq + a(p^2)
= 2a(q^2) + 2apq + 2bpq + b(q^2) + a(p^2)
= b((q^2) + 2pq)) + a((q^2) + 2pq) + a((p^2) + (q^2))

T^1 の時の b
  bp + aq
T^2 の時の b
(bp + aq)p + (bq + aq + ap)q
= b(p^2) + apq + b(q^2) + a(q^2) + apq
= a(q^2) + 2apq + b(p^2) + b(q^2)
= b((p^2) + (q^2)) + a((q^2) + 2pq)

よって
p' = (p^2) + (q^2)
q' = (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
                   (+ (square p) (square q))
                   (+ (square q) (double (* p q)))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1))))
)

となる。

今日の夕飯

• 豚ハツのコチュジャン焼き
• ブリの塩焼き
• 餡かけ焼きそば

しかし、カマボコがすごい色だなぁ。