chili 默默学编程

SICP(4):高阶过程


本文目录

1、求和的抽象;

2、不动点求平方根;

3、牛顿法求平方根(使用不动点);

整体比较简单,简略记录。


求和的抽象

1、求从 a 到 b 之间的整数和

(define (sum-int a b)
  (if (> a b)
      0
      (+ a
         (sum-int (1+ a) b))))

2、求从 a 到 b 之间的整数的平方和

(define (sum-sq a b)
  (if (> a b)
      0
      (+ (* a a)
         (sum-sq (1+ a) b))))

3、pi / 8 求和

(define (sum-pi a b)
  (if (> a b)
      0
      (+ (/ 1 (* a (+ a 2)))
         (sum-pi (1+ a) b))))

4、抽象出求和的公式,再生成各种求和公式

原则:把变化的部分抽象成参数

// sum(recursion 版本)
(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

// sum-int
(define (sum-int a b)
  (define term (lambda(x) (x)))
  (define next (lambda(x) (1+ x)))
  (sum term a next b))

// sum-sq
(define (sum-sq a b)
  (define term (lambda(x) (* x x)))
  (define next (lambda(x) (1+ x)))
  (sum term a next b))

// sum-pi
(define (sum-pi a b)
  (define term (lambda(x) (* x x)))
  (define next (lambda(x) (/ 1 (* a (+ a 2)))))
  (sum term a next b))


// sum(iterative 版本,参数能包含所有信息)
(define (sum term a next b)
  (define (iter j ans)
    (if (> j b)
        ans
        (iter (next j) (+ ans (term j)))))
  (iter a 0))

不动点求平方根 

// 平方根 sqrt 是不动点的特殊应用
(define (sqrt x)
  (fixed-point
    (lambda(y) (average (/ x y) y))
  1))

// 不动点函数
(define (fixed-point f start)
  (define (iter old new)
      (if (close-enough? old new)
          new
          (iter new (f new))))
  (iter start (f start)))

牛顿法求平方根(使用不动点)

// 倒序写
(define (sqrt x)
  (newton (lambda(y) (- x (square y)))
  1))

(define (newton f guess)
  (define df (deriv f))
  (fixed-point
    (lambda (x)
            (- x (/ (f x) (df x))))
    guess))

(define deriv 
  (lambda(f)
     (lambda(x)
            (/ (- (f (+ x dx))
                  (f x))
               dx))))
(define dx 0.00001)

reply ( 0 )