sicpマラソン2日目(2)

[メモ]

• 木構造再帰＝プロセスが樹木状に進化 (1.2.2)
• 木構造再帰の必要ステップ数＝木構造の節の数に比例 (1.2.2)
• 木構造再帰の必要スペース＝木構造の最大深さに比例 (1.2.2)
• 両替の場合の数問題懐かしい (1.2.2)

[演習問題]

1.11

## 再帰的プロセス
(define (f1 n)
        (cond ((< n 3) n)
              (else (+ (f1 (- n 1))
                       (* 2 (f1 (- n 2)))
                       (* 3 (f1 (- n 3)))))))

## 反復的プロセス
(define (f2 n)
        (f2-iter 2 1 0 n))
(define (f2-iter a b c count)
        (if (= count 0)
            c
            (f2-iter (+ a (* 2 b) (* 3 c))
                     a
                     b
                     (- count 1))))

gosh > (f1 1)
1
gosh > (f2 1)
1
gosh > (f1 5)
25
gosh > (f2 5)
25
gosh > (f1 20)
10771211
gosh > (f2 20)
10771211
gosh >

できた、ちなみに(f1 10000)とかすると計算ステップ数がえらい事になって結果が返ってこないが(f2 10000)だと計算できる
1.12 パスカルの三角形

(define (pascal a b)
        (cond ((< a 2) 1)
              ((= b 1) 1)
              ((= a b) 1)
              (else (+ (pascal (- a 1) (- b 1))
                       (pascal (- a 1) b)))))

1.13 フィボナッチ数列の証明問題、今は飛ばそう