SICP读书笔记1.3 | Senghoo Kim

练习1.29

解释器内部采用有理数表示部分数值的关系，对于n = 100 和n = 1000的求值均得到0.25

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))


(define (integral f a b n)
  (define h (/ (- b a) n))
  (define (term k)
    (define (y k)
      (f (+ a (* k h))))
    (cond ((= k 0) (y k))
          ((= k n) (y k))
          ((devides? 2 k) (* 2 (y k)))
          (else (* 4 (y k)))))
  (define (next n) (+ n 1))
  (* (/ h 3) (sum term 0 next n) ))

(define (devides? a b)
  (= (remainder b a) 0))

练习1.30

(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ result (term a)))))
  (iter a 0))

练习1.31

a) product过程只需要修改上面的sum过程的 + 为 * ，并且把初始值变为1

(define (product term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* result (term a)))))
  (iter a 1))

(define (pi n)
  (define (next a) (+ a 1))
  (define (term a)
    (if (devides? 2 a)
        (/ (+ a 2) (+ a 1))
        (/ (+ a 1) (+ a 2))))
  (* (product term 1 next n) 4))


(define (devides? a b)
  (= (remainder b a) 0))

b) 上面实现的是送代计算过程，实现递归过程，同样简单修改sum的递归过程就可以

(define (product2 term a next b)
  (if (> a b)
      1
      (* (term a)
         (product2 term (next a) next b))))

练习1.32

如同习题1.31把sum 变为product时所做的变化。在accumulate中运算符和初始值是通过参数传进来的。

也就是进一步抽象共同点，在更高层次上进行抽象。

accumulate的送代版本和递归版本如下：

(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner result (term a)))))
  (iter a null-value))

(define (accumulate2 combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (product2 term (next a) next b))))

使用accumulate实现sum和product:

(define (product term a next b)
  (accumulate * 1 term a next b))

(define (sum term a next b)
  (accumulate + 0 term a next b))

练习1.33

定义过程如下:

(define (filtered-accumulate combiner null-value term a next b filter)
  (define (iter a result)
    (cond ((> a b) result)
          ((filter a) (iter (next a) (combiner result (term a))))
          (else (iter (next a) result))))
  (iter a null-value))

(define (square n) (* n n))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((devides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (devides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

(define (prime-sum a b)
  (define (term x) x)
  (define (next x) (+ x 1))
  (filtered-accumulate + 0 term a next b prime?))

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

(define (coprime-sum n)
  (define (coprime? x) (= (gcd n x) 1))
  (define (term x) x)
  (define (next x) (+ x 1))
  (filtered-accumulate + 0 term 1 next n coprime?))

练习1.34

(define (f g)
  (g 2))

程序的执行过程如下

(f f)
(f 2)
(2 2)

执行到(2 2) 时程序报错，因为2不是个有效的过程

不动点定理

文中说的某些函数指的是压缩映射的函数。

压缩映射的函数可以通过送代f(x) 求得不懂点。

详细可以参考这节公开课不动点定理

对于 $y = \frac x y$

因为函数不是压缩映射，我们可以在解不变的情况下通过改造函数得到压缩映射，也就是添加平均阻尼：

$2y= \frac x y + y$ $y= \frac 1 2 \times (\frac x y + y)$

并且这种平均阻尼技术可以加速收敛

练习1.35

黄金分割率公式为:

$\phi^2 = \phi + 1$ $\phi = 1 + \frac 1 \phi$

得证

计算换金分割率:

(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))

(define (golden-mean)
  (fixed-point (lambda (x) (+ 1 (/ 1 x))) 2.0))

#;1037> (golden-mean)
1.61803278688525

练习1.36

代码：

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (display guess)
    (newline)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(define (f)
  (fixed-point (lambda (x) (/ (log 1000) (log x))) 2))

结果：

(f)
2
9.96578428466209
3.00447220984121
6.27919575750716
3.75985070240154
5.2158437849259
4.1822071924014
4.82776509834459
4.38759338466268
4.6712500857639
4.48140361689505
4.6053657460929
4.52308496787189
4.57711468204734
4.54138248015145
4.56490324523083
4.54937267930334
4.55960649191329
4.55285387578827
4.55730552974826
4.55436906443618
4.556305311533
4.55502826357355
4.55587039670285
4.55531500119208
4.55568126354333
4.55543971573685
4.55559900999829
4.55549395753139
4.55556323729288
4.55551754841765
4.5555476793064
4.55552780851625
4.55554091291796
4.55553227080365

练习1.37

(define (cont-frac n d k)
  (define (iter i)
    (if (> i k)
        0
        (/ (n i) (+ (d i) (iter (+ i 1))))))
  (iter 1))

(define (cont-frac2 n d k)
  (define (iter i s)
    (if (= i 0)
        s
        (iter (- i 1) (/ (n i) (+ (d i) s)))))
  (iter k 0))

通过测试至少k >= 11才能保证4位精度

#;647> (cont-frac2 (lambda (i) 1.0) (lambda (i) 1.0) 10)
0.617977528089888
#;652> (cont-frac2 (lambda (i) 1.0) (lambda (i) 1.0) 11)
0.618055555555556

练习1.38

(define (d i)
  (if (= (remainder i 3) 2)
      (* (+ (quotient i 3) 1) 2)
      1))

(define (e)
  (+ (cont-frac2 (lambda (i) 1.0) d 100) 2))

结果：

#;1076> (e)
2.71828182845905

练习1.39

(define (tan-cf x k)
  (define square-x (* x x))
  (/ (cont-frac2 (lambda (i) (- square-x))
                 (lambda (i) (- (* i 2) 1))
                 k)
     x))

结果

#;1192> (tan-cf 2 100)
2.18503986326152

练习1.40

(define dx 0.00001)
(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))
(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))

(define (newton-method g guess)
  (fixed-point (newton-transform g) guess))

(define (cubic a b c)
  (lambda (x)
    (+ (* x x x) (* a x x) (* b x) c)))

练习1.41

(define (double f)
  (lambda (x)
    (f (f x))))

(define (inc x)
  (+ 1 x))

调用过程如下

(((double (double double)) inc) 5)
(((double (lambda (x) (double (double x)))) inc) 5)
(((lambda (x) (double (double (double (double x))))) inc) 5)
((double (double (double (lambda (x) (inc (inc x)))))) 5)
((double (lambda (x) (inc (inc (inc (inc (inc (inc (inc (inc x)))))))))) 5)
((lambda (x) (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc x))))))))))))))))) 5)
(inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc 5))))))))))))))))

练习1.42

(define (compose f g)
  (lambda (x) (f (g x))))

练习1.43

(define (repeated f n)
  (define (iter i res)
    (if (= i 0)
        res
        (iter (- i 1) (f res))))
  (lambda (x) (iter n x)))

练习1.44

(define dx 0.00001)
(define (smooth f)
  (lambda (x)
    (/ (+ (f (+ x dx))
          (f x )
          (f (- x dx)))
       3)))


(define (repeated-smooth f n)
  ((repeated smooth n) f))

练习1.45

根据规律可以推算出，计算n次的开方需要平均阻尼的次数等于 $\lfloor \log_2 n \rfloor$

(define (damp-count n)
  (floor (/ (log n) (log 2))))

完整代码如下：

(define (average a b)
  (/ (+ a b) 2))

(define (average-damp f)
  (lambda (x) (average x (f x))))

(define (damp-count n)
  (floor (/ (log n) (log 2))))

(define (root n i)
  (fixed-point ((repeated average-damp (damp-count n))
                (lambda (x) (/ i (expt x (- n 1))))) 1))

练习1.46

实现如下：

(define (iterative-improve good-enough? improve)
  (define (iter guess)
    (let ((next (improve guess)))
      (if (good-enough? guess next)
          next
          (iter next))))
  (lambda (x) (iter x)))

重写的sqrt和fixed-point

(define (sqrt x)
  ((iterative-improve
    (lambda (old new)
      (< (/ (abs (- old new))
            old)
         0.001))
    (lambda (guess)
      (average guess (/ x guess))))
   1))

(define (fixed-point f first-guess)
  ((iterative-improve
    (lambda (old new)
      (< (abs (- old new)) tolerance))
    f)
   first-guess))