YOSHINO日記

プログラミングに関すること

SICP: 1.10 反復的な手法を見つけるには法則を見つける必要がある

問題

Exercise 1.11 gives us a function defined by the rules that

f(n) = n if n < 3
f(n) = f(n - 1) + 2f(n - 2) + 3f(n -3) if n ≥ 3

再帰的手法と反復手法の両方の解法を考える。

再帰

(define (f n)    
  (if (< n 3)    
    n                                                            
    (+ (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3)))))))    
    
; (f 3) = 4    
; (f 4) = 11    
; (f 5) = 25  

再帰の手法はすぐに思い浮かべることができる。

再帰の手法はわかりやすいけれど、計算の重複を避けられず、効率では反復的な手法に劣ることが多い。

反復の手法は答えから法則を見つけて作成しなければいけない。

反復

解法

まずは解法から(ここで示すのが唯一の正解でもないし、一番効率的なものでもないと思う)

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

; 以下のように展開する
; (f 3)
; (f-iter 2 1 0 3)
; (f-iter 4 2 1 2)
; 4

; (f 4)
; (f-iter 2 1 0 4)
; (f-iter 4 2 1 3)
; (f-iter 11 2 1 2)
; 11

; (f 5)
; (f-iter 2 1 0 5)
; (f-iter 4 2 1 4)
; (f-iter 11 2 1 3)
; (f-iter 25 2 1 2)
; 25

思考プロセス

まず、以下のように書き出して眺める。

f(0) = 0
f(1) = 1
f(2) = 2

n=3   f(3) = f(2) + 2 * f(1) + 3 * f(0)
n=4   f(4) = f(3) + 2 * f(2) + 3 * f(1)
n=5   f(5) = f(4) + 2 * f(3) + 3 * f(2)
.
.
.
n=k   f(k) = f(k-1) + 2 * f(k-2) + 3 * f(k-3)

f(n)を求めるためには、

1回前の値(n-1) 2回前の値(n-2) 3回前の値(n-3)

の3つの状態を知っている必要があることがわかる。

1回前の値: a

2回前の値: b

3回前の値: c

とするならば、

次の値は以下のようになる。

1回前の値: (+ a (* 2 b) (* 3 c))
2回前の値: a
3回前の値: b

もう一度、解法を見てみる。

 (f-iter (+ a (* 2 b) (* 3 c))                                                                   
            a                                                                                              
            b                                                                                                         
            (- count 1))))       

3つの変数がわかれば、次の値がわかる。

そして、どこまで計算すればよいかはcountが知っている。

反復計算の特徴として計算量がどのプロセスでも等しくなる。

言い方を変えれば変数の数はいつも同じになる。

今回の場合では4つだ。

反復的な手法を見つけるためには、

いくつ状態を保存すれば良いのか(変数にすれば良いのか)?

と考えるのが良いのだと思う。