Serendip

Web Studio

問題3.57

加算の回数を数えるために add-streams の中の + 演算を add 手続きに置き換える。
add 手続き中でカウンタを増加させて行き、結果の印字手続き (fib n) で add 手続きの合計回数（カウンタの最終結果）を Fibonacci 数とともに印字する。

(define counter 0)

(define (count-up)
  (set! counter (+ counter 1)))

(define (count-reset)
  (set! counter 0))

(define (add x y)
  (count-up)
  (display "(")
  (display x)
  (display "+")
  (display y)
  (display "), ")
  (+ x y))

(define (add-streams s1 s2)
  (stream-map add s1 s2))

(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs)
                                         fibs))))

(define (fib n)
  (display "Fib:")
  (display n)
  (display ", RESULT:")
  (display (stream-ref fibs n))
  (display ", COUNT:")
  (display counter)
  (count-reset)
  (newline))

メモライズした場合

(fib 0)
(fib 1)
(fib 2)
(fib 3)
(fib 4)
(fib 5)
(fib 6)
(fib 7)
(fib 8)
gosh> Fib:0, RESULT:0, COUNT:0
#<undef>
gosh> Fib:1, RESULT:1, COUNT:0
#<undef>
gosh> Fib:2, RESULT:(1+0), 1, COUNT:1
#<undef>
gosh> Fib:3, RESULT:(1+1), 2, COUNT:1
#<undef>
gosh> Fib:4, RESULT:(2+1), 3, COUNT:1
#<undef>
gosh> Fib:5, RESULT:(3+2), 5, COUNT:1
#<undef>
gosh> Fib:6, RESULT:(5+3), 8, COUNT:1
#<undef>
gosh> Fib:7, RESULT:(8+5), 13, COUNT:1
#<undef>
gosh> Fib:8, RESULT:(13+8), 21, COUNT:1
#<undef>

全ての COUNT が 1 になっているが、これはメモライズしているために新規に実行される加算のみカウントされるから（count-reset により fib が実行される度に counter は 0 となる）。
よって (fib 8) のみを実行すると COUNT は 7 と印字される。

(fib 8)
gosh> Fib:8, RESULT:(1+0), (1+1), (2+1), (3+2), (5+3), (8+5), (13+8), 21, COUNT:7
#<undef>

したがって、 n 番目の Fibonacci 数を計算する時は、加算は n-1 回実行される（n は 0 から始まるとする）。

メモライズしなかった場合

(fib 0)
(fib 1)
(fib 2)
(fib 3)
(fib 4)
(fib 5)
(fib 6)
(fib 7)
(fib 8)
gosh> Fib:0, RESULT:0, COUNT:0
#<undef>
gosh> Fib:1, RESULT:1, COUNT:0
#<undef>
gosh> Fib:2, RESULT:(1+0), 1, COUNT:1
#<undef>
gosh> Fib:3, RESULT:(1+0), (1+0), (1+1), 2, COUNT:3
#<undef>
gosh> Fib:4, RESULT:(1+0), (1+0), (1+1), (1+0), (1+1), (1+0), (2+1), 3, COUNT:7
#<undef>
gosh> Fib:5, RESULT:(1+0), (1+0), (1+1), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (3+2), 5, COUNT:14
#<undef>
gosh> Fib:6, RESULT:(1+0), (1+0), (1+1), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (3+2), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (3+2), (1+0), (1+1), (1+0), (2+1), (5+3), 8, COUNT:26
#<undef>
gosh> Fib:7, RESULT:(1+0), (1+0), (1+1), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (3+2), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (3+2), (1+0), (1+1), (1+0), (2+1), (5+3), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (3+2), (1+0), (1+1), (1+0), (2+1), (5+3), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (3+2), (8+5), 13, COUNT:46
#<undef>
gosh> Fib:8, RESULT:(1+0), (1+0), (1+1), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (3+2), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (3+2), (1+0), (1+1), (1+0), (2+1), (5+3), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (3+2), (1+0), (1+1), (1+0), (2+1), (5+3), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (3+2), (8+5), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (3+2), (1+0), (1+1), (1+0), (2+1), (5+3), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (3+2), (8+5), (1+0), (1+1), (1+0), (2+1), (1+0), (1+1), (3+2), (1+0), (1+1), (1+0), (2+1), (5+3), (13+8), 21, COUNT:79
#<undef>

この結果からわかるとおり、すでに実行された加算を繰り返し実行するために指数的増加で加算の実行回数が増えていく。

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る