SICP

Exercise 1.37. a. An infinite continued fraction is an expression of the form

As an example, one can show that the infinite continued fraction expansion with the Ni and the Di all equal to 1 produces 1/, where is the golden ratio (described in section 1.2.2). One way to approximate an infinite continued fraction is to truncate the expansion after a given number of terms. Such a truncation–a so-called k-term finite continued fraction–has the form

Suppose that n and d are procedures of one argument (the term index i) that return the Ni and Di of the terms of the continued fraction. Define a procedure cont-frac such that evaluating (cont-frac n d k) computes the value of the k-term finite continued fraction. Check your procedure by approximating 1/ using

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

for successive values of k. How large must you make k in order to get an approximation that is accurate to 4 decimal places?

b. If your cont-frac procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

递归式子与数学式子基本是等同的。我们可以将 k 项有限连分式写为如下的数学式

fix space after alignment

$$cf(i) = \left\{\begin{aligned} 0 & i > k \\ \frac{N_i}{D_i + f(i+1)} & (i <= k) \\ \end{aligned} \right. $$ 这样的式子写为我们的程序就是：

(define (cont-frac n d k)
  (define (rec i)
    (cond ((> i k) 0)
          (else
           (/ (n i)
              (+ (d i)
                 (rec (+ i 1)))))))
  (rec 1))

写迭代式时，有了前面写迭代式的经验，我们就知道需要一个变量 result 来存储结果。通过观察，我们知道迭代时候 i 的初始值应该为 k。最后我们验证这两个过程产生的结果是一样的。

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


;;; tests begin
(load "../testframe.scm")
(assert= (cont-frac/iter (lambda (i) 1.0)
                         (lambda (i) 1.0)
                         100)
         (cont-frac (lambda (i) 1.0)
                    (lambda (i) 1.0)
                    100))

(define (spot)

要使得近似值有 4 位精度，我们应该观察到第五位。下面的实验结果说明只要 k 取到大于 14 的数字都可以保证有 4 位精度：

                                        ; 1/(golden ratio) = .6180339887498948

  (display (cont-frac (lambda (i) 1.0)
                      (lambda (i) 1.0)
                      10))
                                        ;Value: .6179775280898876

  (display (cont-frac (lambda (i) 1.0)
                      (lambda (i) 1.0)
                      11))
                                        ;Value: .6180555555555556

  (display (cont-frac (lambda (i) 1.0)
                      (lambda (i) 1.0)
                      14))
                                        ;Value: .6180327868852459
)

SICP 全笔记