因为连分式本质上就是一个除法计算序列,所以题目给出 \(k\) 项连分式:
可以转换成以下等价的除法计算序列:
而这个除法序列又可以用一个递归表达式来表示:
其中函数 \(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\) 项连分式等价于除法计算序列
如果要迭代地计算这个除法计算序列,我们必须倒转公式中各个除法项计算的先后顺序,先计算高次项,然后才是低次项。
也即是说,我们必须先计算
然后计算
再然后计算
一直这样反方向回溯下去,直到到达
这时我们就得出了整个连分式的解,而且整个计算过程是迭代地进行的。
这个迭代计算连分式过程的定义如下:
;;; 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