■

問題 1.14
木構造描く方法が無いんで普通に展開

(cc 11 5)
(+ (cc 11 4) (cc -39 5))
(+ (+ (cc 11 3) (cc -4 4)) 0)
(+ (+ (cc 11 2) (cc 1 3)) 0) 0)
(+ (+ (+ (+ (cc 11 1) (cc 6 2)) (+ (cc 1 2) (cc -9 3)) ) 0) 0)
(+ (+ (+ 1 (+ (cc 6 1) (cc 1 2)) (+ (cc 1 1) (cc -4 2))) 0) 0)

※ここで　(cc 1 n)は1 (cc n 0)は0、(cc n 1)は 1なので以下省略


プロセスのスペース数は全て0or1に展開された時のその個数であるが、以下のように解く

最初のamount数をm、コインの種類の数をnとし
その場合のステップ数をf(m,n)とする。
また、コインの種類の数を引数とする以下の関数を
用意する

するとf(m,n)は次のように展開出来る
f(m,n) 
= f(m,n-1) + f(m-g(n), n)
= f(m,n-1) + f(m-g(n),n-1) + f(m-2g(n),n)
...
= f(m,n-1) + f(m-g(n),n-1)+ ... + f(m-k_n*g(n),n-1) + f(m-(k_n+1)g(n),n)
整数k_nとはm-k_n*g(n)>0を満たす最大の整数であるとする。(k_n = floor(m/g(n))
すなわち m-(k_n+1)g(n) < 0であるから、f(m-(k_n+1)g(n),n)は1となる。

これをΣで記述すると

と書ける。
同様にしてn=5,4,3,2,1と次々展開していくと

となるが、ここで
である（∵n=1なのでこれ以降の展開はととなるため)

従ってf(m,5)は次のようになる

...


ステップ数をccの呼ばれる回数であるとすると1,0が呼ばれる一つ前に一度呼ばれるのでその数もとなる。

問題 1.15

a)
(sine 12.15)
(sine (p (sine 4.05)))
(sine (p (sine (p (sine 1.35)))))
(sine (p (sine (p (sine (p (sine 0.45)))))))
(sine (p (sine (p (sine (p (sine (p (sine 0.15)))))))))
(sine (p (sine (p (sine (p (sine (p (sine (p (sine 0.05)))))))))))
(sine (p (sine (p (sine (p (sine (p (sine (p 0.05))))))))))
...
pは5回作用させられた。

b)
ステップ数をsineとpを呼ぶ回数、スペースをpを呼ぶ回数とし、
n回目にangle<0.1となるとすると
ステップ数は2n,スペースはnとなる
すなわち双方共にとなる。
nは a/3^n < 0.1を満たす最小の整数でありそれは

よって求める値は

である。