[SICP] 問題 1.37 : 連分数

a. 無限の連分数(continued fraction)は
の形の式である. 例えばNiとDiがすべて1の無限連分数展開が1/φになることが示せる. φは(1.2.2節で示した)黄金比. 無限連分数の近似値のとり方の一つは, 与えられた項数で展開を中断することで, そういう中断--- k項有限連分数(k-term finite continued fraction)という---は
の形である. nとdを一引数(項の添字i)で連分数の項のNiとDiを返す手続きとする. (cont-frac n d k)がk項有限連分数を計算するような手続きcont-fracを定義せよ.

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           k)

のkの順次の値で1/φの近似をとり, 手続きを調べよ. 4桁の精度の近似を得るのに, kはどのくらい大きくしなければならないか.

b. cont-fracが再帰的プロセスを生成するなら, 反復的プロセスを生成するものを書け. 反復的プロセスを生成するなら, 再帰的プロセスを生成するものを書け.

連分数を求める手続きを定義します.

;; 再帰的プロセスを生成
(define (cont-frac-r n d k)
  (define (iter i)
    (if (> i k)
        0
        (/ (n i)
           (+ (d i) (iter (+ i 1))))))
  (iter 1))

;; 反復的プロセスを生成
(define (cont-frac-i n d k)
  (define (iter i result)
    (if (= i 0)
        result
        (iter (- i 1)
              (/ (n i)
                 (+ (d i) result)))))
  (iter k 0))

(define (phi-r k)
  (/ 1 (cont-frac-r (lambda (i) 1.0)
                    (lambda (i) 1.0)
                    k)))

(define (phi-i k)
  (/ 1 (cont-frac-i (lambda (i) 1.0)
                    (lambda (i) 1.0)
                    k)))

再帰的プロセスを生成する手続きは, 上の方から計算しています. 反復的プロセスを生成する手続きは, 下の方から計算するようにしています.

黄金比Φの計算をしてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (phi-r 15)
1.6180327868852458
> (phi-i 15)
1.6180327868852458
> 

kの値を15にすれば良さそうです.