Hatena::Groupcsnagoya-sicp

gabuchanの日記

2008-11-10

問題1.15

| 15:38

考えるよりもプログラムが書きたいので問われているステップ数を数えるプログラムを書いたら、問題のプログラムとほぼ同じものが出来たというオチ。

(define (step n)
  (define (step-iter n count)
    (if (not (> n 0.1))
        count
        (step-iter (/ n 3.0) (+ count 1))))
  (step-iter n 0))

(print (step 12.15))

ということで、a.の答えは

$ gosh 1.15.scm
5

悩むのはb.のスペースとステップ数。。。

ステップ数は

(p (sine (p (sine ...

って増えていくから、2n なんだけどSICPが言う「増加の程度」としては、

n^2 ステップが必要なプロセスも、1000n^2 ステップが必要なプロセスも 3n^2 + 10n + 17 ステップが必要なプロセスもすべてΘ(n^2)の増加の程度という.

なので、よりスペースやステップに影響を与える変数に着目して、2n ステップは答えとしてはΘ(n) かなぁ。(かなり自信ないです。)

スペースも同様にΘ(n) かなぁ。(かなり自信ないです。)