SICPを読もう5

Programming Scheme SICP

ミッシングリンクを埋めようということで、問題1.14から1.16。あんま進まんかった。眠い。もずくうまい。
問題1.14
まさに木構造木構造したもの描くのは面倒なので適当にS式。そういう簡単な図とかのインターフェイスとしてはやっぱり紙媒体の方が優れてるなあと思う。

(cost-change 11)
(cc 11 5)
(+ (cc 11 4) (cc 10 5))
(+ (+ (cc 11 3) (cc 10 4)) (+ (cc 10 4) (cc 9 5)))

もういいじゃんって気がしてきました。スペースとステップ数ってなんだべ。このS式で言うところの横幅が即ちスペースで縦の行数がステップ数というところか。

問題1.15
(sine 12.15)でpが何回呼ばれますかー、って何回1/3かければ0.1未満になるかってこと。

(define (f x n) (if (< x 0.1) n (f (/ x 3) (+ n 1))))
(f 12.15 0)
; 5
(letrec ((f (lambda (x n) (if (< x 0.1) n (f (/ x 3) (+ n 1)))))) (f 12.15 0))
; 5
((lambda (f x n) (f f x n)) (lambda (f x n) (if (< x 0.1) n (f f (/ x 3) (+ n 1)))) 12.15 0)
; 5

5回だそうです。上から別にこの問題ではそんなこと求められてませんけれど、letrecとかlambdaを使って書いてみた。うんletrecはlambdaの構文糖衣ですね。シンタックスシュガーって言った方が通りいいかもれません。

末尾再帰なんだからスペースは増えない、という考えで合ってんのかな？ ο(1)？
ステップ数はο(a)かなあ。

1.2.4 べき乗

うわーものすごく単純でわかりやすいことだけど逐次平方を使った方がべき乗が速くなるということに納得。

問題1.16

(define (fast-expt x n) 
  (define (cube x) (* x x))
  (define (iter a x n)
    (cond
      ((= n 1) (* a x))
      ((even? n) (iter a (cube x) (/ n 2)))
      (else (iter (* a x) x (- n 1)))))
  (iter 1 x n))
(fast-expt 2 10)
; 1024
(fast-expt 2 15)
; 32768

よろし。スムーズに解けなかった。なんかほげーっとなりながらあー正しい答えがでねー、と手だけ動かしてる自分に気付いた。一旦手を止めて考えればわかって直ぐできた。ちゃんと脳味噌使ったほうが速くできる。

(fast-expt 2 10)
= (fast-expt 4 5)
= (* 4 (fast-expt 4 4))
= (* 4 (fast-expt 16 2))
= (* 4 (fast-expt 256 1))
= (* 4 256)
= 1024

ということです。てか普通にちゃんと読めば書いてあることだったけど。ちゃんと読みましょう。

test