SICP学习笔记 1.3.3 过程作为一般性的方法

    练习 1.35

φ^2 = φ+1 
==> φ = 1 + (1/φ) 

(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))
  
> (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)
1.6180327868852458

 

    练习 1.36

(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (and (report v1) (< (abs (- v1 v2)) tolerance)))
  (define (report v)
    (display " *** ")
    (display v)
    (newline))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

;; 不使用平均阻尼需要34次  
> (fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0)
 *** 2.0
 *** 9.965784284662087
 *** 3.004472209841214
 *** 6.279195757507157
 *** 3.759850702401539
 *** 5.215843784925895
 *** 4.182207192401397
 *** 4.8277650983445906
 *** 4.387593384662677
 *** 4.671250085763899
 *** 4.481403616895052
 *** 4.6053657460929
 *** 4.5230849678718865
 *** 4.577114682047341
 *** 4.541382480151454
 *** 4.564903245230833
 *** 4.549372679303342
 *** 4.559606491913287
 *** 4.552853875788271
 *** 4.557305529748263
 *** 4.554369064436181
 *** 4.556305311532999
 *** 4.555028263573554
 *** 4.555870396702851
 *** 4.555315001192079
 *** 4.5556812635433275
 *** 4.555439715736846
 *** 4.555599009998291
 *** 4.555493957531389
 *** 4.555563237292884
 *** 4.555517548417651
 *** 4.555547679306398
 *** 4.555527808516254
 *** 4.555540912917957
4.555532270803653

;; 使用平均阻尼需要9次 
> (fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 2.0)
 *** 2.0
 *** 5.9828921423310435
 *** 4.922168721308343
 *** 4.628224318195455
 *** 4.568346513136242
 *** 4.5577305909237005
 *** 4.555909809045131
 *** 4.555599411610624
 *** 4.5555465521473675
4.555537551999825

 

    练习 1.37

;; 线性递归
(define (cont-frac n d k)
  (if (= k 1)
      1
      (/ (n k) (+ (d k) (cont-frac n d (- k 1))))))
      
;; 线性迭代
(define (cont-frac n d k)
  (cont-frac-iter n d (/ (n 1) (d 1)) 1 k))
(define (cont-frac-iter n d v c k)
  (if (= c k)
      v
      (cont-frac-iter n d (/ (n c) (+ (d c) v)) (+ c 1) k)))
      
;; k取值11时即可达到4位精度(取8位精度为1.61803399)
1 ]=> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 11)
0.6180555555555556

 

    练习 1.38

;; 欧拉连分式的Di过程
define (d-euler i)
  (if (= (remainder (+ i 1) 3) 0)
      (* 2.0 (/ (+ i 1) 3.0))
      1.0))
        
;; 求值
1 ]=> (+ 2 (cont-frac (lambda (i) 1.0) d-euler 100))
;Value: 2.5037311291101405

 

    练习 1.39

;; 过程定义应该如下, 但是并没有得到正确结果
(define (tan-cf x k)
  (define (n-tan i)
    (if (= i 1)
        x
        (- (* x x))))
  (cont-frac n-tan (lambda (i) (- (* 2.0 i) 1.0)) k))


1 ]=> (tan-cf (/ 3.1415926 4) 100)

;Value: -3.1312698448737733e-3