計算機プログラムの構造と解釈 第二版 P26 問題1.19
計算機プログラムの構造と解釈 第二版
P26 問題1.19
すごく難しかったが、
割とよくできたと思うので、結果を乗せておきます。
(Tpq)^2 = Tp'q' なので、Tpq を二回実行して、比較してみれば、p' q'は、もとまる。 Tpqを一回実行した結果の対をA B とすると、 A = bq + aq + ap B = bp + aq Tpqの二回目の実行を行った結果の対を A' B'とすると、 A' = Bq + Aq + Ap B' = Bp + Aq B'を用いて比較を行う。B'を展開すると B' = Bp + Aq B' = (bp + aq)p + (bq + aq + ap)q B' = bpp + apq + bqq + aqq + apq B' = b(pp + qq) + a(qq + 2pq) ここで、 B'= bp' + aq' であるから。 B' = b(pp + qq) + a(qq + 2pq) と比較すると、 p' = pp + qq q' = qq + 2pq (define (fib n) (fib-iter 1 0 0 1 n)) (define (fib-iter a b p q count) (cond ((= count 0) b) ((even? count) (fib-iter a b (+ (* p p) (* q q)) ;ここがp' (+ (* q q) (* 2 p q)) ;ここがq' (/ count 2))) (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))))