SICPを読む(12) 問題1.11 - 1.15 やっぱり反復が・・・。

やっぱり、ひげぽんと同じように反復が解けなかった・・・。

問題1.11

フィボナッチ強力版の登場です。ボスクラス。

n < 3の時、 f(n) = n
n >= 3の時、f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)
となる関数を再帰と反復で計算する手続きを書け。

再帰は一瞬で解けた。

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

反復は終端の処理が判らず、答えを見た。

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

答えを見てもすぐにアルゴリズムが見出せなかったが、仕事中に謎が解けた(笑

反復のポイントは、

ずらし。
- a b c を (iter (+ ...) a bとして、cを捨てる。
先読みしている。
- count - 2 の時にはcount - 4まで先読み。

悩んだので、何も見ずに解けるようになった。

問題1.12

パスカルの三角形の要素を計算せよ。

公式があるようですが、公式を使わずに解きます。

と、三角形を崩して、左上方向と、上方向に走査していこうと思います。

(define (pascal row col)
  (if (or (= col 0) (= row col))
      1
      (+ (pascal (- row 1) col)
         (pascal (- row 1) (- col 1)))))

(pascal 4 0) ; 1
(pascal 4 1) ; 4
(pascal 4 2) ; 6
(pascal 4 3) ; 4
(pascal 4 4) ; 1

おぉぉぉぉ。

自分で再帰的パターンを見出すことが出来ました!!

感動。

参考:パスカルの三角形 - Wikipedia

問題1.13

数学的帰納の問題。

問題を読んでもさっぱりわからないので、答えを見た。

答えを読んだら、もっとわからなくなった。まぁ、いっか。

問題1.14

紙に書いたが・・・ゼロを忘れてた。
スペースとステップ数の関係がイマイチ掴めてない。

問題1.15

計算するのが面倒だったので、dispalyデバッグを使って確認。大体予想どおり。
スペースとステップ数の関係がイマイチ掴めてない。

まとめ

「考える」というプロセスがやけに楽しい。
数学おもろい。
括弧に慣れてきた。
Schemeはシンプルだ。
スペースとステップ数計算の理解度が全然足りない。

更新履歴

2013/05/23
- 1.12を少し修正。