SICP問題1.14
プログラムの木構造は以下のとおりとなる。
(11 5)
┌─┴─┐
(-39 5) (11 4)
┌─┴─┐
(-14 4) (11 3)
┌───┴────────┐
(1 3) (11 2)
┌─┴┐ ┌───┴─────────┐
(-9 3) (1 2) (6 2) (11 1)
┌─┴─┐ ┌┴───────┐ ┌┴┐
(-4 2) (1 1) (1 2) (6 1) (10 1) (11 0)
┌─┴─┐ ┌┴──┐ ┌┴┐ ┌┴┐
(0 1) (1 0) (-4 2) (1 2) (5 1) (6 0) (9 1) (10 0)
┌┴─┐ ┌┴┐ ┌┴┐
(0 1) (1 0) (4 1) (5 0) (8 1) (9 0)
┌┴┐ ┌┴┐
(3 1) (4 0) (7 1) (8 0)
┌┴┐ ┌┴┐
(2 1) (3 0) (6 1) (7 0)
┌┴┐ ┌┴┐
(1 1) (2 0) (5 1) (6 0)
┌┴┐ ┌┴┐
(0 1) (1 0) (4 1) (5 0)
┌┴┐
(3 1) (4 0)
┌┴┐
(2 1) (3 0)
┌┴┐
(1 1) (2 0)
┌┴┐
(0 1) (1 0)プロセスのステップ数とスペース量の増加の程度は以下のようになる。
ステップ数はccを呼び出す回数(コインの数分呼び出しが指数的に増加する)→指数的に増加 必要なスペース量は計算中どの節が上方に残っているかを覚えておく量→入力に対して線形にしか増加しない。 よってステップ数の増加の程度はΘ(n^5) スペース量の増加の程度はΘ(n)
だと思うけど、さっぱり自信なし…。
SICP問題1.15
すっかり忘れ去っているラジアンの定義 from Wikipedia
ラジアンは円周上でその円の半径と同じ長さの弧を切り取る二本の半径が成す角の値と定義される。度数法で測った360度は弧度法においては2πラジアンとなる。 よって1ラジアン＝(360/2π)≒57.29578度となる。
で問題。
a. (sine 12.15) の評価で手続き p は何回作用させられたか
(sine 12.15) (p (sine (/ 12.15 3.0))) (p (p (sine (/ 4.05 3.0)))) (p (p (p (sine (/ 1.35 3.0))))) (p (p (p (p (sine (/ 0.45 3.0)))))) (p (p (p (p (p (sine (/ 0.15 3.0))))))) ; => 5回 (p (p (p (p 0.14950000000000002))))) (p (p (p 0.43513455050000005))) (p (p 0.9758465331678772)) (p -0.7895631144708228) -0.39980345741334
ということで5回。
b. (sine a) の評価で、手続き p の生成するプロセスが使うスペースとスペースの増加の程度は(a の関数として)何か
さっぱり分からない…。orz
http://sicp.naochan.com/memo.pl?p=%CC%E4%C2%EA1.15
辺りを見ると、スペース数, ステップ数ともに増加の程度はΘ(log a)というのが答えのようだけど、回答見てもさっぱり分かりませんでした…。
気になる本
ガムテープで文字を書こう! ―話題の新書体「修悦体」をマスターして
- 作者: 佐藤修悦(さとうしゅうえつ)
- 出版社/メーカー: 世界文化社
- 発売日: 2009/04/10
- メディア: 単行本（ソフトカバー）
- 購入: 11人 クリック: 615回
- この商品を含むブログ (31件) を見る
