sicp 笔记 (1)

ou

“sicp”全称是“Structure and Interpretation of Computer Programs”，是 MIT 计算机专业第一年的一门入门课程的教材（据说现在已经取消了这门课，取而代之的是另一门使用 python 的课程）。网上很多人都强烈推荐这本书，给出了各种赞美之词，因此从网上找了个排版比较好的电子版（google 搜“sicp unofficial texinfo format”，我用的是 2.neilvandyke4 这个版本）。直到研究生快毕业才开始学习别人本科第一年的教材，希望亡羊补牢还不算晚。

这里使用 plt-scheme，除了 1.28 小题的 random 函数之外其它题目都能运行，推荐使用 mit-scheme（debian 中只有 i386 的包，64 位的需要自己到官网下载编译）。

下面是第一章的习题解答部分。

E-1.1: 把内容对着敲一遍就行了

E-1.2:

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 5 4))))) (* 3 (- 6 2) (- 2 7)))

E-1.3: 3 个数中找两个比较大的数，相当于排除最小的那个。

(define (square x) (* x x))

(define (func x y z)
  (- (+ (square x) (square y) (square z))
     (square (min x y z))))

; ---------------------------------------------

(func 5 10 3)

E-1.5: 在 applicative-order 情况下每当看到“(p)”的时候都会展开，然后陷入死循环；在 normal-order 情况下返回 0，根据 if 的规则，如果条件满足就不会对 else 分支求值。

E-1.6: 在 applicative-order 情况下会死循环，因为 new-if 是一个函数，进入 new-if 后展开 good-enough? 和 improve，因为没有退出条件，两个函数一直运行，到不了 cond 那一步。

E-1.8:

(define (square x) (* x x))
(define (cube x) (* (square x) x))

(define (good-enough? guess x)
  (< (abs (- (cube guess) x))
     0.001))

(define (improve guess x)
  (/ (+ (/ x (square guess))
        (* guess 2))
     3))

(define (cube-r-iter guess x)
  (if (good-enough? guess x)
    guess
    (cube-r-iter (improve guess x) x)))

(define (cube-r x)
  (cube-r-iter 1.0 x))

; ---------------------------------------------------

(cube-r 9)

E-1.9: 第一个是递归的，第二个是迭代的。

E-1.10:

(A 1 10) = 1024；(A 2 4) = 65536；(A 3 3) = 65536

f(n) = 2n；g(n) = 2^n；h(n) = (((2^2)^2)...)^2，一共 n 个 2。

E-1.11:

(define (f-recur n)
  (if (< n 3)
    n
    (+ (f-recur (- n 1))
       (* 2 (f-recur (- n 2)))
       (* 3 (f-recur (- n 3))))))

; --------------------------------------------------------

(define (f-iter-internal n-3 n-2 n-1 count)
  (cond ((< count 3) n-1)
        (else (f-iter-internal n-2 n-1 (+ (* 3 n-3) (* 2 n-2) n-1)
                               (- count 1)))))

(define (f-iter n)
  (f-iter-internal 0 1 2 n))

; --------------------------------------------------------

(f-recur 7)
(f-iter 7)

E-1.12:

(define (pascal-triangle x y)
  (cond ((or (> x y) (< x 1) (< y 1)) 0)
        ((or (= x 1) (= x y)) 1)
        (else (+ (pascal-triangle (- x 1) (- y 1))
                 (pascal-triangle x (- y 1))))))

; ---------------------------------------------------------

(pascal-triangle 4 5)

E-1.13: 根据提示就是要证明 Fib(n) 的极限，用待定系数法：令 F(n) - aF(n - 1) = b[F(n - 1) - aF(n - 2)]，整理后得：a + b = 1，ab = -1。令G(n) = F(n) - aF(n - 1)，则 G(n) 是以 (1 - a) 为首项，b 为公比的等比数列，得 G(n) = b^(n - 1)；互换 a 和 b 的位置得 G(n) = a^(n - 1)。把 G(n) 用 F(n) 表示，最后消去 F(n - 1) 即为结果。

E-1.15: (b) 当 a / 3^n <= 0.1 时停止，所以 f(n) = log3(10a)。

E-1.16:

(define (square x) (* x x))

(define (fast-expt b n a)
  (cond ((= n 0) a)
        ((even? n) (fast-expt (square b) (/ n 2) a))
        (else (fast-expt b (- n 1) (* a b)))))

; -------------------------------------------------------------------

(fast-expt 3 3 1)

E-1.17:
E-1.18:

(define (double x) (* x 2))

(define (halve x) (/ x 2))

(define (fast-mul-recur a b)
  (cond ((= b 1) a)
        ((even? b) (fast-mul-recur (double a) (halve b)))
        (else (+ a (fast-mul-recur a (- b 1))))))

(define (fast-mul-iter a b result)
  (cond ((= b 0) result)
        ((even? b) (fast-mul-iter a (halve b) (+ result (double a))))
        (else (fast-mul-iter a (- b 1) (+ result a)))))

; -----------------------------------------------------------

(fast-mul-recur 3 7)
(fast-mul-iter 6 6 0)

E-1.19: 令 a1 = bq + aq + ap，b1 = bp + aq，则 b2 = (b1)p + (a1)q = bp' + aq'，化简后得 p' 为 pp+qq，q' 为 q*q+2pq。

E-1.23: 去掉偶数的情况要比没去掉的要快些，但是应该没 2 倍那么多，因为偶数的 smallest-divisor 是 2，在没去掉偶数的情况下每个偶数只比奇数多了一次判断。

E-1.25: 我觉得是对的，就是按照定义来算。

E-1.26: 在第一个条件中 remainder 的参数被重复计算，在 normal-order 情况下尤其明显。

E-1.28: 没看懂原题，中文版也看不懂，在网上找了答案（参考资料 [1]）

(define (square x) (* x x))

(define (expmod base e n)
  (define (check x)
    (if (and (not (or (= x 1) (= x (- n 1))))
             (= (remainder (square x) n) 1))
      0
      (remainder (square x) n)))

  (cond ((= e 0) 1)
        ((even? e)
         (check (expmod base (/ e 2) n)))
        (else
          (remainder (* base (expmod base (- e 1) n)) n))))

(define (miller-rabin-test n)
  (define (try-it a)
    (= (expmod a n n) a))

  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((miller-rabin-test n) (fast-prime? n (- times 1)))
        (else #f)))

; ----------------------------------------------------------------

(fast-prime? 6601 1)

E-1.29:

(define (y f a k h)
  (f (+ a (* k h))))

(define (sum-helper f a k h)
  (cond ((= k 0) (f a))
        ((even? k) (+ (* 2 (y f a k h)) (sum-helper f a (- k 1) h)))
        (else (+ (* 4 (y f a k h)) (sum-helper f a (- k 1) h)))))

(define (sum f a h n)
  (if (= n 0)
    (f a)
    (+ (y f a n h)
       (sum-helper f a (- n 1) h))))

; n is even
(define (integral f a b n)
  (* (/ (/ (- b a) n) 3)
     (sum f a (/ (- b a) n) n)))

; --------------------------------------------------------------------

(define (cube x) (* x x x))

(integral cube 0.0 1.0 1000)

E-1.30:

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

; --------------------------------------------------------

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

(sum identity 1 inc 100)

E-1.31: 把等号右边分子中的“2”移到左边再计算，这样分子比分母只多出一个 n。

(define (product-recur term a next b)
  (if (> a b)
    1
    (* (term a)
       (product-recur term (next a) next b))))

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

; --------------------------------------------------------

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

(product-recur identity 1 inc 3)

; n is even
(define (compute-pi n)
  (define (next a) (+ a 2))
  (define (term a) (* a a))
  (define (div n)
    (/ (* (product-recur term 4 next (- n 2)) n)
       (product-iter term 3 next (- n 1))))

  (* 8 (div n)))

(compute-pi 1000)

E-1.32:

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

; ---------------------------------------------------------------------

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

;(accumulate + 0 identity 1 inc 100)
(accumulate * 1 identity 1 inc 6)

E-1.33:

(define (filtered-accumulate combiner null-value term a next b my-filter)
  (define (func x)
    (filtered-accumulate combiner null-value term x next b my-filter))

  (cond ((> a b) null-value)
        ((my-filter a) (combiner (term a) (func (next a))))
        (else (func (next a)))))

; ---------------------------------------------------------------------

(load "1.22.scm")

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

(define (func-a a b)
  (define (prime? x)
    (= (smallest-divisor x) x))

  (filtered-accumulate + 0 identity a inc b prime?))

(define (func-b a b)
  (define (relative-prime? x)
    (if (= x b)
      #f
      (= (gcd x b) 1)))

  (filtered-accumulate * 1 identity a inc b relative-prime?))

; ---------------------------------------------------------------------

(func-a 1 20)

E-1.35:

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

E-1.36:

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))

  (define (report x)
    (display "result: ")
    (display x)
    (newline))

  (define (try guess)
    (display "try -> ")
    (display guess)
    (newline)

    (let ((next (f guess)))
      (if (close-enough? guess next)
        (report next)
        (try next))))

  (try first-guess))

; -----------------------------------------------------------

(define (average a b) (/ (+ a b) 2))
(define (func x) (/ (log 1000) (log x)))

(fixed-point (lambda (x) (average x (func x))) 2.0)

E-1.37: 之前的递归都是从大到小递减的，这里却是从小到大，一时反应不过来，刚开始还试图找 f(k) 和 f(k+1) 的递推关系式……

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

  (iter k 0))

(define (cont-frac-recur n d k)
  (define (recur i)
    (if (= i k)
      (/ (n i) (d i))
      (/ (n i) (+ (d i) (recur (+ i 1))))))

  (recur 1))

; ---------------------------------------------------

(cont-frac-iter (lambda (i) 1.0)
                (lambda (i) 1.0)
                2)

E-1.38:

(load "1.37.scm")

(define (n i) 1.0)

(define (d i)
  (cond ((= (remainder i 3) 0) 1.0)
        ((= (remainder i 3) 1) 1.0)
        (else (* 2 (/ (+ i 1) 3)))))

(+ 2 (cont-frac-iter n d 20))

E-1.39: 虽然没有提示要用 cont-frac，但是稍微观察一下会发现两者的形式很相似。

(load "1.37.scm")

(define (tan-cf x k)

  (define (n i)
    (if (= i 1)
      x
      (- (* x x))))

  (define (d i)
    (- (* 2 i) 1))

  (cont-frac-recur n d k))

; ---------------------------------------------------

(tan-cf 1.0 40)

E-1.40:

(load "../examples/1.3.4-newtons-method.scm")

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

(newtons-method (cubic 3 4 5) 1)

E-1.42:

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

(define (square x) (* x x))
(define (inc x) (+ x 1))

((compose square inc) 6)

E-1.43: 层次一多脑子就搞不清了，看来以后还要多练习。

(load "1.42.scm")

(define (repeated f n)
  (define (recur i)
    (if (= i 1)
      f
      (compose f (recur (- i 1)))))

  (lambda (x)
    ((recur n) x)))

; --------------------------------------------

(define (square x) (* x x))

((repeated square 2) 5)

E-1.44:

(load "1.43.scm")

(define dx 0.00001)

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

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

; --------------------------------------------

(define (identity x) x)

((n-fold-smoothed identity 100) 1)

E-1.46: 回调函数的参数传递很巧妙。

(define (iterative-improve good-enough? improve)
  (define (iter guess)
    (if (good-enough? guess)
      guess
      (iter (improve guess))))

  (lambda (guess)
    (iter guess)))

; ---------------------------------------------------

(define (my-sqrt x)
  (define (square y) (* y y))

  (define (good-enough? guess)
    (< (abs (- (square guess) x))
       0.001))

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

  (define (improve guess)
    (average guess (/ x guess)))

  ((iterative-improve good-enough? improve) 1.0))

; ---------------------------------------------------

(define (fixed-point f guess)
  (define tolerance 0.00001)

  (define (good-enough? guess)
    (< (abs (- (f guess) guess))
       tolerance))

  (define (improve guess)
    (f guess))

  ((iterative-improve good-enough? improve) 1.0))

; ---------------------------------------------------

(my-sqrt 9)

(fixed-point cos 1.0)

参考资料

[1] SICP Exercise 1.28: The Miller-Rabin test

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注