Scheme - 高階手続きによる抽象(一般的方法としての手続き(連分数と黄金比))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の1(手続きによる抽象の構築)、1.3(高階手続きによる抽象)、1.3.3(一般的方法としての手続き)の問1.37を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 1.37.

再帰的プロセス。

コード

sample.scm

(define (cont-frac n d k)
  (define (frac-iter i)
    (if (< i k)
        (/ (n i) (+ (d i) (frac-iter (+ i 1))))
        (/ (n i) (d i))))
  (frac-iter 1))

(define (cont-frac-iter n d k)
  (newline)
  (display k)
  (display " *** ")
  (define x (cont-frac n d k))
  (display x)
  (cond ((and (< x 0.6181) (> x 0.6180)))
        (else (cont-frac-iter n d (+ k 1)))))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> (/ 2 (+ 1 (sqrt 5)))

;Value: .6180339887498948

1 ]=> 
(cont-frac-iter (lambda (i) 1.0)
                (lambda (i) 1.0)
                1)

1 *** 1.
2 *** .5
3 *** .6666666666666666
4 *** .6000000000000001
5 *** .625
6 *** .6153846153846154
7 *** .6190476190476191
8 *** .6176470588235294
9 *** .6181818181818182
10 *** .6179775280898876
11 *** .6180555555555556
;Value: #t

1 ]=> ^D
End of input stream reached.
Moriturus te saluto.

ということで、連分数を使って1/Φ (黄金比の逆数)の4桁の制度の近似を得るには、kは11くらいに大きくしなければならない。

反復的プロセスを生成するものに書き直す。

コード

sample.scm

(define (cont-frac n d k)
  (define (frac-iter i result)
    (if (= i 0)
        result
        (frac-iter (- i 1) (/ (n i) (+ (d i) result)))))
  (frac-iter k 0))

(define (cont-frac-iter n d k)
  (newline)
  (display k)
  (display " *** ")
  (define x (cont-frac n d k))
  (display x)
  (cond ((and (< x 0.6181) (> x 0.6180)))
        (else (cont-frac-iter n d (+ k 1)))))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> 
(cont-frac-iter (lambda (i) 1.0)
                (lambda (i) 1.0)
                1)

1 *** 1.
2 *** .5
3 *** .6666666666666666
4 *** .6000000000000001
5 *** .625
6 *** .6153846153846154
7 *** .6190476190476191
8 *** .6176470588235294
9 *** .6181818181818182
10 *** .6179775280898876
11 *** .6180555555555556
;Value: #t

1 ]=> ^D        
End of input stream reached.
Moriturus te saluto.