問題5.29 – SICP（計算機プログラムの構造と解釈）その279
2009年11月18日
問題5.29
;;; EC-Eval input:
(define (fib n)
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
(total-pushes = 3 maximum-depth = 3)
;;; EC-Eval value:
ok
;;; EC-Eval input:
(fib 3)
(total-pushes = 128 maximum-depth = 18)
;;; EC-Eval value:
2
...
実行結果の表
| n | Fib(n) | total-pushes | maximum-depth |
|---|---|---|---|
| 0 | 0 | 16 | 8 |
| 1 | 1 | 16 | 8 |
| 2 | 1 | 72 | 13 |
| 3 | 2 | 128 | 18 |
| 4 | 3 | 240 | 23 |
| 5 | 5 | 408 | 28 |
| 6 | 8 | 688 | 33 |
| 7 | 13 | 1136 | 38 |
| 8 | 21 | 1864 | 43 |
a. Fib(n) を計算するのに必要なスタックの最大深さの n を使った式
上記表の結果から、D = (5 * n) + 3 となる。
b. プッシュの総数の式と式 S(n) = a * Fib(n + 1) + b の a と b の値
プッシュの数：S(n) は S(n-1) + S(n-2) + k で表せると考える。
よって、上記表の結果より、k は 40 であるとわかる。
また、上記表の結果から、 S(n) = a * Fib(n + 1) + b は a = 56、b = -40 となることがわかる。
$(n) = 56 * Fib(n + 1) - 40
計算機プログラムの構造と解釈
posted with amazlet at 08.11.07
ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542
ピアソンエデュケーション
売り上げランキング: 6542