エンジニアをリングする

プログラをミングしたり。

my web site twitter

SICP課題1.11をもういちどていねいに

SICPが難航してきました。
どこからつまづきだしたのかちょっと戻って考えてみると、課題1.11からちゃんと理解できなくなってきたようだったので、課題1.11の解答についてじっくり考えてみたいと思います。

課題1.11 関数f

関数 f は n < 3 の場合 f(n) = n と n ≥ 3 の場合、 f(n) = f(n − 1) + 2f(n − 2) + 3f(n − 3) のルールの下に定義される。f を演算する手続を再帰プロセスを用いて書け。また f を演算する手続を反復プロセスを用いて書け。

これです。
再帰プロセスの方はそのまま翻訳すればいいだけなので書けたのですが、反復プロセスのほうがわからず、答えを見てもなぜそうなるのかわからない感じでした。
反復プロセスの方をじっくり見ていきたいと思います。

あ、ちなみに再帰プロセスの方の回答は以下。

; 再帰プロセス
gosh> (define (f n)
        (cond ((< n 3) n)
              (else (+
                      (f (- n 1))
                      (* 2 (f (- n 2)))
                      (* 3 (f (- n 3)))))))

そのまんま。

反復プロセスの解答

こちらから引用。

;; ex 1.11. Iterative implementation 
  
 (define (f n) 
   (define (iter a b c count) 
     (if (= count 0) 
       a 
       (iter b c (+ c (* 2 b) (* 3 a)) (- count 1)))) 
   (iter 0 1 2 n)) 

きれいなコードですね。
ただ、どうしてこうなった。

疑問

  • f(n)の答えには関数fを適用しないといけないはずなのに、iterの最後の再帰部分ではfを適用していない。fはどこへいった?
  • なぜ3つの引数をずらしていくことで解が導き出せるのか?
  • なぜ最初に0, 1, 2の引数を渡すのか?

ちょっと正直意味がわかりませんでした。。。
この内容で正解の値が出ることが信じられませんでした。

で、先日参加したSICP読書会で先輩メンバーにその疑問をぶつけてきました。

理解のきっかけ

何が悪かったのかというと、nが0, 1, 2...の場合のf(n)の値を考えていなかったことが問題だったようです。
nが0, 1, 2...の場合のf(n)の値を考えてみます。

; f(n)の値を考える

; 0  if n = 0 ((< n 3) n)
; 1  if n = 1 ((< n 3) n)
; 2  if n = 2 ((< n 3) n)
; 4  if n = 3 (+ (* 1 (f 2))  #-> (* 1 2)
;                (* 2 (f 1))  #-> (* 2 1)
;                (* 3 (f 0))) #-> (* 3 0)
; 11 if n = 4 (+ (* 1 (f 3))
;                (* 2 (f 2))
;                (* 3 (f 1)))
  • n < 3 の場合 f(n) = n, 具体的にはf(0) = 0, f(1) = 1, f(2) = 2
  • n >= 3 の場合のf(n)はf(n-1), f(n-2), f(n-3)の解から導き出せる

この2点をちゃんと意識したことで、ようやく少し理解できるようになりました。

解説になってるかわかんない解説

  • 解答コードの最後の(iter 0 1 2 n)は、(iter f(0) f(1) f(2) n)という意味だった!!
  • nが3以上の場合はf(n-1), f(n-2), f(n-3)を元にしてf(n)を求められる
  • n = 3のときf(n)は(+ c (* 2 b) (* 3 a))で求められる!!

解答コードにたどり着きました・・・。

挙げていた疑問が解決されました。

  • なぜ最初に0, 1, 2の引数を渡すのか?
    -> f(0), f(1), f(2)の計算済の答えを渡している。
  • f(n)の答えには関数fを適用しないといけないはずなのに、iterの最後の再帰部分ではfを適用していない。fはどこへいった?
    -> 最初の引数0, 1, 2がf(0), f(1), f(2)なので消えてない。それらの答えを元にして算出したf(3)以降もfが適用された状態になる。
  • なぜ3つの引数をずらしていくことで解が導き出せるのか?
    -> f(n-1), f(n-2), f(n-3)からf(n)が求められるから。

ただ目新しいことって別になくて、私が題意をきちんと理解していないことが疑問の原因でした・・・。

あと、もういっこ発見。counterについて。
counterを0..nで回すのかn..0で回すのかもちょっと迷いました。
解答コードはnから0までカウントダウンしています。

これは、0..nだとcounterの他にnという初期値を記憶しておかないといけませんが、n..0なら比較に0という定数を使えるので最初のnを覚えておかなくてもいいのでよりシンプルにできるということですね。
引数をもうひとつ増やせばカウントアップ方式でも正解が出せました。

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

n..0のほうがシンプルですね。

書いてみよう

見ないで書いてみます!

(define (f n)
  (define (iter a b c counter)
    (if (= counter 0)
        a
        (iter b c (+ c (* 2 b) (* 3 a)) (- counter 1))))
  (iter 2 1 0 n))

できた!!!

次のつまづき

課題1.12はできてたので、次にできなかったのは1.13です・・・。
でも「Fib(n)がφn/√5に最も近いことの証明」ということでだいぶ数学的っぽいんだよなあ・・・
続く1.14、1.15も挫折してるのでそっちはちゃんとやりたいかも。