练习 1.37

因为连分式本质上就是一个除法计算序列，所以题目给出 \(k\) 项连分式：

\[\cfrac{N_1}{D_1 + \cfrac{N_2}{\ddots + \cfrac{N_k}{D_k}}}\]

可以转换成以下等价的除法计算序列：

\[N_1 / (D_1 + (N_2 / (D_2 + \dotsi + (N_k / D_k))))\]

而这个除法序列又可以用一个递归表达式来表示：

\[ \begin{align}\begin{aligned}cf(1)\\N_1 / (D_1 + cf(2))\\N_1 / (D_1 + (N_2 / (D_2 + cf(3))))\\N_1 / (D_1 + (N_2 / (D_2 + (N_3 / (D_3 + cf(4))))))\\\dotsi\\N_1 / (D_1 + (N_2 / (D_2 + (N_3 / (D_3 + \dotsi + (N_k / D_k))))))\end{aligned}\end{align} \]

其中函数 \(cf(i)\) 表示连分式的第 \(i\) 个项。

根据这个递归表达式，我们可以给出（递归计算版本）连分式过程的定义：

;;; 37-rec-cont-frac.scm

(define (cont-frac N D k)

    (define (cf i)
        (if (= k i)
            (/ (N k) (D k))
            (/ (N i)
               (+ (D i) (cf (+ i 1))))))

    (cf 1))

迭代版本的连分式过程

前面说过，一个 \(k\) 项连分式等价于除法计算序列

\[N_1 / (D_1 + (N_2 / (D_2 + \dotsi + (N_k / D_k))))\]

如果要迭代地计算这个除法计算序列，我们必须倒转公式中各个除法项计算的先后顺序，先计算高次项，然后才是低次项。

也即是说，我们必须先计算

\[cf(k) = N_k / D_k\]

然后计算

\[cf(k-1) = N_{k-1} / (D_{k-1} + cf(k))\]

再然后计算

\[cf(k-2) = N_{k-2} / (D_{k-2} + cf(k-1))\]

一直这样反方向回溯下去，直到到达

\[N_1 / (D_1 + cf(2))\]

这时我们就得出了整个连分式的解，而且整个计算过程是迭代地进行的。

这个迭代计算连分式过程的定义如下：

;;; 37-iter-cont-frac.scm

(define (cont-frac N D k)

    (define (iter i result)
        (if (= i 0)
            result
            (iter (- i 1)
                  (/ (N i)
                     (+ (D i) result)))))

    (iter (- k 1)
          (/ (N k) (D k))))

连分式定义的黄金分割率函数

使用连分式定义的黄金分割率函数的定义如下：

;;; 37-golden-ratio.scm

(load "37-rec-cont-frac.scm")

(define (golden-ratio k)
    (+ 1
       (cont-frac (lambda (i) 1.0)
                  (lambda (i) 1.0)
                  k)))

测试：

1 ]=> (load "37-golden-ratio.scm")

;Loading "37-golden-ratio.scm"...
;  Loading "37-rec-cont-frac.scm"... done
;... done
;Value: golden-ratio

1 ]=> (golden-ratio 1)

;Value: 2.

1 ]=> (golden-ratio 10)

;Value: 1.6179775280898876

1 ]=> (golden-ratio 11)

;Value: 1.6180555555555556

从测试结果可以看出，只要 \(k\) 的值大于等于 \(11\) ，就可以保证计算所得的黄金分割率的精度到达前四位： \(1.618\) 。

测试迭代连分式过程

前面的黄金分割率函数使用的是递归版本的连分式过程，现在来试试迭代版本的连分式程序，确保它运作良好：

;;; 37-golden-ratio-using-iter-cont-frac.scm

(load "37-iter-cont-frac.scm")

(define (golden-ratio k)
    (+ 1
       (cont-frac (lambda (i) 1.0)
                  (lambda (i) 1.0)
                  k)))

测试：

1 ]=> (load "37-golden-ratio-using-iter-cont-frac.scm")

;Loading "37-golden-ratio-using-iter-cont-frac.scm"...
;  Loading "37-iter-cont-frac.scm"... done
;... done
;Value: golden-ratio

1 ]=> (golden-ratio 1)

;Value: 2.

1 ]=> (golden-ratio 10)

;Value: 1.6179775280898876

1 ]=> (golden-ratio 11)

;Value: 1.6180555555555556

讨论

blog comments powered by Disqus