SICPを読む_(7)1章_手続きによる抽象の構築(p20-23)

今回は木構造再帰の部分らへんを書いてます。

1.2.2木構造再帰(p20-)

計算でよくあるパターン「木構造再帰」

(define (fib n)
  (cond
   ((zero? n) 0)
   ((= n 1) 1)
   (else
    (+ (fib (- n 1))
       (fib (- n 2))))))

黄金比すげぇ(脱線)

(define (fib n)
  (fib-iter 0 1 n))

(define (fib-iter a b cont)
  (cond
   ((zero? cont) a)
   (else
    (fib-iter b (+ a b) (- cont 1)))))

１つ目の手続きは何度も同じ計算が出てくるので計算の無駄が多い、２つ目の手続きは反復的プロセスになっているため１つ目よりは計算量が減っていると。

階層構造のデータを扱うプロセスを考えるとき、木構造再帰は自然で強力である。
木構造再帰はプログラムの理解や設計を支援してくれる。

例:両替の計算(p22-23)

1ドルを両替するのに1,5,10,25,50セントがそれぞれあるときに、どれだけパターンがあるかという例。
ちょっとこれは詰まったので、実際に書いてみる。

;;--count-change

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-conins)
  (cond
   ((zero? amount) 1)
   ((or (< amount 0)(zero? kinds-of-conins)) 0)
   (else
    (+ (cc amount (- kinds-of-conins 1))
       (cc (- amount (first-denomination kinds-of-conins))
	   kinds-of-conins)))))

(define (first-denomination kinds-of-conins)
  (cond
   ((= kinds-of-conins 1) 1)
   ((= kinds-of-conins 2) 5)
   ((= kinds-of-conins 3) 10)
   ((= kinds-of-conins 4) 25)
   ((= kinds-of-conins 5) 50)))

;;とりあえず問題の簡略化のため10セントを両替してみる
;;パターンに10セントそのものが返ってくるのがあるので、両替じゃないのが1つあるけど…
(count-change 10)

;;これが実際の処理の流れかな??
(cc 10 5) -> (cc -40 5)
|
(cc 10 4) -> (cc -15 4)
|
(cc 10 3) -> (cc 0 3);;+1
|
(cc 10 2) -> (cc 5 2) -> (cc 0 2);;+1
|            |
|            (cc 5 1) -> ... -> (cc 0 1);;+1
|            |
|            (cc 5 0)
|
(cc 10 1) -> ... -> (cc 0 1);;+1
|
(cc 10 0);;+0

こうやってバラしたときに綺麗な木構造ができてるんですねーとか。

問題1.11(p23)

苦労したけど、これでいいと思う。
反復的プロセスを書くときのコツは、一度ノートとかに書いてみてどういう風にしたいか、何が状態変数となり得るかを考えることですね。。。

;;n<3   f(n)=n
;;n>=3  f(n)=f(n-1)+2f(n-2)+3f(n-3)

;;recursive
(define (f n)
  (cond
   ((< n 3) n)
   (else
    (+ (f (- n 1))
       (* 2 (f (- n 2)))
       (* 3 (f (- n 3)))))))


;;iterative
(define (f n)
  (f-iter 0 1 2 n))

(define (f-iter a b c n)
  (cond
   ((zero? n) a)
   (else
    (f-iter b c (+ (* a 3) (* b 2) c) (- n 1)))))

問題1.12(p23)

これはそんなに難しくなかったのでGitHubにソースだけ上げておく。

問題1.13(p23)

証明せよ…とは。
ちょっとこれは手に負えないので、パス。
この辺が参考になりそう、というか答え(?)かな。
SICP - 問1.13

てな感じでひとまずここまで。続きはまた次回っと。

(define -ayalog '())

括弧に魅せられて道を外した名前のないプログラマ