Exercise 3.56. - 3.58.
Exercise 3.56
(define S (cons-stream 1 (merge (merge (scale-stream S 2) (scale-stream S 3)) (scale-stream S 5))))
で良いはずなんだけど手元の gosh 0.8.11 では merge がうまく動いてくれなくて無限ループになった。
Exercise 3.57
メモ化なしの場合、フィボナッチ数列のストリームの各要素を求めるのに加算が何回必要かという問題。
(define fibs (cons-stream 0 (cons-stream 1 (add-streams (stream-cdr fibs) fibs))))
まずは具体的に考えていくしかないわな。
- 最初の 0 と 1 の 2 項は既知なので足し算の数は 0 回。
- 第 3 項は既知の第 1 項、第 2 項の和 0 + 1 = 1 で求まるから足し算は 1 回。
- 第 4 項は第 2 項、第 3 項の和 1 + 1 = 2 だけど、第 2 項を求めるのに足し算は 0 回必要。第 3 項を求めるのに足し算は 1 回必要。最後にその 2 つを足すの 1 回必要。よって計 2 回必要となる。
以上から n > 3 のとき、第 n 項の足し算の回数は {第 (n-2) 項の回数} + {第 (n-1) 項の回数} + 1 で良いはず。ちなみにメモ化してたらどの項も足し算は 1 回で済む。
Exercise 3.58
(define (expand num den radix) (cons-stream (quotient (* num radix) den) (expand (remainder (* num radix) den) den radix)))
これが何をする関数かと言う問題。見ただけでは分からなかったので、実際に紙と鉛筆で (expand 1 7 10) と (expand 3 8 10) を解いてみた。
そうしたらすぐに分かった。expand は radix 進数のときの有理数 num/dev を少数で表現したときのの各桁の数字がストリームになって求まるというモノ。
project euler で循環小数の問題があったはずなので、これは使えるはず。しめしめ。
今日はここまで
最初に読んだときは何で飛ばしたんだろうと思うぐらいにストリームがおもしろい。でも結構必死ｗ。当初の目論見通りに project euler の方へ還元できればいいけど。
