SICP解答メモ＆解説 (問題1.11〜問題1.13）

SICP

問題1.11

とりあえず再帰プロセスの手続きを書いてみよう。

(define (f n)
  (if (< n 3)
	  n
	  (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))

これは定義式をそのまま書くだけので楽。で、実行結果はこうなった。



gosh> (f 3)

CALL f 3

 ----------f(n - 1) ----------

 CALL f 2

 RETN f 2

 ----------f(n - 2)----------

 CALL f 1

 RETN f 1

 ----------f(n - 3)----------

 CALL f 0

 RETN f 0

RETN f 4

4

今度はn＝4の時



gosh> (f 4)

CALL f 4

 ----------レベル1のf(n - 1)------------

 CALL f 3

  ----------レベル2のf(n - 1)---------

  CALL f 2

  RETN f 2

  ----------レベル2のf(n - 2)---------

  CALL f 1

  RETN f 1

  ----------レベル2のf(n - 3)---------

  CALL f 0

  RETN f 0

 RETN f 4

 ----------レベル1のf(n - 2)-------------

 CALL f 2

 RETN f 2

 ----------レベル1のf(n - 3)-------------

 CALL f 1

 RETN f 1

RETN f 11

11
ふむ、確かに木構造再帰しているみたいですね。


では次に反復プロセスを書いてみよう。反復プロセスは状態変数(state variable)を書いて末尾再帰的にすればよいから…


ってあれ書けない…う〜ん、フィボナッチ数の時の反復プロセスの求め方は、載ってたのをそのまま書いただけなんだよな。で、その求め方の例として両替の話があって…ってそこから反復プロセス求めてないじゃん。


ここから関数型言語の勉強にSICPを読もう - (7) 1章 - 反復をマスターしたいけど・・・ - higepon blogを参考にしつつ進めてみる。もう一回フィボナッチ数を反復プロセスで求めた手続きを見みる。

; this process is linear iterative.
; state variable
(define (fib-imp n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
	  b
	  (fib-iter (+ a b) a (- count 1))))

これはフィボナッチ数の「fib(0) = 0, fib(1) = 1」で値を初期化して、「計算を積み上げていっている感じ」である。
とりあえず書いてみた。

; iterative
(define (f n)
  (define iter 1st 2nd 3rd count)
    (cond ((= count 0) 1st)
	  ((= count 1) 2nd)
	  ((= count 2) 3rd)
	  (else (iter )))
   (iter 0 1 2 n))

これは「n < 3」の時のはっきりとわかっている時の値を初期化した。しかし、どう「計算を積み上げるか」がお手上げ状態になってしまって書けなかった。

解答集の解答は、

(define (f-iter n)
  (define (iter a b c count)
    (cond ((= count 0) c)
          ((= count 1) b)
          (else (iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))
  (iter 2 1 0 n))

う〜む…

で、反復プロセス練習！！練習！！練習！！ - どらや記で練習してもう一回やってみた結果…

(define (f n)
  (f-iter 2 1 0 n))
(define (f-iter a b c count)
  (cond ((= count 2) a)
	((= count 1) b)
	((= count 0) c)
	(else (f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))

う〜む…微妙に解答集と違う…ぐぬぬ

問題1.12

何を解けばいいのかいまいちわからないのでパス。

問題1.13

フィボナッチ数の証明問題なのでパス。