1.37

练习 1.37 a) 一个无穷连分式是一个如下形式的表达式:

f=N1D1+N2D2+N3D3+ f = \frac{N_1}{D_1 + \frac{N_2}{D_2 + \frac{N_3}{D_3 + \cdots}}}

作为一个例子,我们可以证明在所有的 NiN_iDiD_i 都等于1时,这一无穷连分式产生出1/ϕ1/\phi,其中的ϕ\phi就是黄金分割率(见1.2.2节的描述)。逼近某个无穷连分式的一种方法是在给定数目的项之后截断,这样的一个截断称为 k 项有限连分式,其形式是:

N1D1+N2+NkDk \frac{N_1}{D_1 + \frac{N_2}{ \ddots + \frac{N_k}{D_k}}}

假定n和d都是只有一个参数(项的下标i)的过程,它们分别返回连分式的项NiN_iDiD_i。请定义一个过程 cont-frac,使得对 (cont-frac n d k) 的求值计算出k项有限连分式的值。

通过如下调用检查你的过程对于顺序的k值是否逼近1/ϕ1/\phi

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

你需要取多大的k才能保证得到近似值具有十进制的4位精度?

(define (cont-frac n d k)
    (if (= k 1) 1
        (/ (n 1) (+ (d 1) (cont-frac n d (- k 1))))
    )
)

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

作为对比,之前使用不动点方式计算的 1/ϕ 1/\phi 的结果是:

(define tolerance 0.00001)

(define (fixed-point f x)
    (define (close-enough? v1 v2)
        (< (abs (- v1 v2)) tolerance))
  (define (iteration f x)
    (if (close-enough? x (f x))
        x
        (iteration f (f x))))
  (iteration f x))

(fixed-point (lambda (x) (+ 1 (/ 1 x))) 0.5)

要达到4位的精度,即需要逼近值和真实值的差的绝对值小于 0.0001。

经过实验,当 k 达到 11 时,即可达到4位的精度。

(cont-frac (lambda (i) 1.0)
            (lambda (i) 1.0)
            10)
(cont-frac (lambda (i) 1.0)
            (lambda (i) 1.0)
            11)

b) 如果你的过程产生一个递归计算过程,那么请写出另一个产生迭代计算的过程。如果它产生迭代计算,请写出另一个过程,使之产生一个递归计算过程。

对于所有 NiN_iDiD_i 都返回 1 时,就有: f=11+11+11+ f = \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \cdots}}} f(1)=11 f(1) = \frac{1}{1} f(2)=11+11=11+f(1) f(2) = \frac{1}{1 + \frac{1}{1}} = \frac{1}{1 + f(1)} f(3)=11+11+11=11+f(2) f(3) = \frac{1}{1 + \frac{1}{1 + \frac{1}{1}}} = \frac{1}{1 + f(2)} \cdots

a) 展示了递归的过程,以下使用一个迭代过程:

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

    (iter 1 k 1)
)

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

results matching ""

    No results matching ""