Exercise 1.37:
An infinite
continued fraction is an expression of the form
f
=
N
1
D
1
+
N
2
D
2
+
N
3
D
3
+
…
.
As an example, one can show that the infinite continued fraction expansion with
the N
i and the D
i all equal to 1 produces 1
/
φ, where
φ is the golden ratio (described in 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
finite continued fraction
k-term
finite continued fraction—has the form
N
1
D
1
+
N
2
⋱
+
N
k
D
k
.
Suppose that n and d are procedures of one argument (the term
index i) that return the N
i and D
i 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?
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.
练习 1.37：无穷连分式是形如
f = N₁ / (D₁ + N₂ / (D₂ + N₃ / (D₃ + …)))
的表达式。举例来说，可以证明：当所有 Nᵢ 和 Dᵢ 均等于 1 时，无穷连分式展开的值为 1/φ，其中 φ 是黄金比例（见 1.2.2 节）。近似无穷连分式的一种方法是在给定项数处截断展开式。这种截断——称为 k 项有限连分式——的形式为
N₁ / (D₁ + N₂ / (⋱ + Nₖ / Dₖ))
设 n 和 d 是以项索引 i 为参数的过程，分别返回连分式各项的 Nᵢ 和 Dᵢ。定义过程 cont-frac，使得求值 (cont-frac n d k) 能计算 k 项有限连分式的值。通过对逐个 k 值求值
(cont-frac (lambda (i) 1.0)
(lambda (i) 1.0)
k)
来近似 1/φ，检验你的过程。k 至少要取多大，才能使近似值精确到 4 位小数？
若你的 cont-frac 过程产生递归型计算过程，请再写一个产生迭代型计算过程的版本；若它产生迭代型计算过程，请再写一个产生递归型计算过程的版本。