sicp 笔记 (8)

第三章习题 3.38 – 3.72 的解答。

E-3.38:

(a) 每个人的操作都作为一个原子操作的话,有 A(3, 3) 共 6 种可能:

Peter Paul Mary: 90 70 35
Peter Mary Paul: 90 45 25
Paul Peter Mary: 80 70 35
Paul Mary Peter: 80 40 20
Mary Peter Paul: 50 40 20
Mary Paul Peter: 50 30 20

(b) 其中一种情况:假设三人同时取到账户余额都是 100,各自执行操作后最后写入账户的是 Peter,于是账户余额为 90。

E-3.39: 可能的值为 100,101 和 121。

E-3.40: 可能值为 10^2,10^3 和 10^6。加了 serializer 后只有 10^6。

E-3.41: 我觉得没必要。查看账户是一个只读操作,并且不存在被打断的情况。

E-3.42: 两个函数最后结果都一样(没有取 balance/2 这样的情况),但中间过程的结果可能不一样。因为第一个版本每次执行 withdraw 或 deposit 都会开一个新进程,这样多个用户的执行顺序是不确定的;而这个版本则是每次都使用同一个进程,保证用户的操作顺序。

E-3.43: 假设第一个人刚把 balance 取出来,第二个人完整地执行了 exchange,这样第一个人取到的值是旧的,再用来交换就会出错。因为系统允许负数,并且仅仅是在账户中交换(账户的操作 withdraw 和 deposit 都是 serialize 的),尽管最后每个账户的结果可能不对,但是总的钱数不会变。

E-3.44: 我觉得两者是一样的,反正取出多少就存入多少,总量保持不变,只是最终状态不一致。

E-3.45: 多次调用了 balance-serializer。

E-3.46: 可能一个线程刚拿到结果,另一个线程就把结果给改了,这样返回给第一个线程的结果是错的。

E-3.47: 使用 test-and-set! 参考 make-mutex 的实现。

(define (make-semaphore n)
  (let ((count 0)
        (mutex (make-mutex)))
    (define (the-semaphore m)
      (cond ((eq? m 'acquire)
             (mutex 'acquire)
             (if (= count n)
               (begin (mutex 'release)
                      (the-semaphore 'acquire))
               (begin (set! count (+ count 1))
                      (mutex 'release))))
            ((eq? m 'release)
             (mutex 'acquire)
             (if (> count 0)
               (set! count (- count 1)))
             (mutex 'release))))

    the-semaphore))

E-3.48: 都从最小编号的取起相当于排队系统,只有一个入口,防止循环等待。

E-3.49: 略。

E-3.50:

(load "../examples/3.5.1-streams-are-delayed-lists.scm")

(define (my-stream-map proc . argstreams)
  (if (stream-null? (car argstreams))
    the-empty-stream
    (cons-stream
      (apply proc (map stream-car argstreams))
      (apply my-stream-map
             (cons proc (map stream-cdr argstreams))))))

E-3.51: define 语句输出 0,第一个 ref 语句应该输出的是 1-5,第二个 ref 语句输出 6-7。

如果按照书本的实现,第一条 define 语句输出了 0-10;第一个 ref 语句直接输出 5;第二个 ref 直接输出 7。只有在构造的时候输出了一次列表(并且是完整的列表),后续的两个 ref 语句都没有重复输出。如果在 delay 和 force 函数中添加打印信息,可以发现在 stream-enumerate-interval 中已经把整个列表构造好了,这是因为 plt-scheme 并不是惰性求值的,解析器会先把递归函数先算出来再执行函数 cons-stream,因此会发现在初始化的时候已经把列表构造完成了。如果要实现惰性求值的功能,可以把 cons-stream 按以下方法实现(参考资料 [1]):

(define-syntax cons-stream
  (syntax-rules ()
                ((_ x y) (cons x (delay y)))))

(define (stream-cdr s) (force (cdr s)))

一般的 scheme 都自带了 delay 和 force,在这里使用的 plt-scheme(mzshcme 4.2.1)是有的。

E-3.52: 结果依次为 1,6,10,36,210。如果没有记忆功能的话结果应该是错的,因为 accum 被重复执行了。

E-3.53: f(n) = 2n

E-3.54:

(load "3.50.scm")
(load "../examples/3.5.2-infinite-streams.scm")

(define (mul-streams s1 s2)
  (my-stream-map * s1 s2))

(define factorials (cons-stream 1 (mul-streams (stream-cdr integers) factorials)))

E-3.55:

(load "../examples/3.5.2-infinite-streams.scm")

(define (partial-sums s)
  (cons-stream (stream-car s) (add-streams (partial-sums s) (stream-cdr s))))

E-3.56: 题目说得很清楚了。

(define S (cons-stream 1 (merge (scale-stream 2)
                                (merge (scale-stream 3)
                                       (scale-stream 5)))))

E-3.57: 当 n>1 时,加法运算次数应该是 2 次,因为每次计算下一个值都只是将前两次的值加起来。如果没有实现记忆功能,每次计算 f(n) 时都要重新计算 f(n-1) 和 f(n-2)。

E-3.58: expand 的意义是求在 radix 进制下,num 除以 den 的商(如果 quotient 和 remainder 的操作也遵循 radix 进制的话)。

E-3.59:

(a) 下面是自己实现的版本,当然是很丑的……

(define (integrate-series stream)
  (let ((counter 0))
    (define (recur s)
      (set! counter (+ counter 1))
      (cons-stream (* (/ 1 counter)
                      (stream-car s))
                   (recur (stream-cdr s))))

    (recur stream)))

然后很不甘心地在网上搜了下,果然找到更好的(参考资料 [2]):

(load "../exercises/3.54.scm") ; mul-streams
(load "../examples/3.5.2-infinite-streams.scm") ; ones integers

(define (div-streams s1 s2)
  (stream-map / s1 s2))

(define (integrate-series a)
  (mul-streams a                                  ; a0, a1, a2, ...
               (div-streams ones integers)))      ; 1/1, 1/2, 1/3, ...

(b) 按定义来就行。

(define cosine-series
  (cons-stream 1 (integrate-series (scale-stream sine-series -1))))

(define sine-series
  (cons-stream 0 (integrate-series cosine-series)))

E-3.60: 假设两个序列为 (ca a0 a1 a2 …) 和 (cb b0 b1 b2 …),其中 ca 和 cb 是常数,则可拆为 ca * cb + ca * (b0 b1 b2 …) + cb * (a0 a1 a2 …) + (a0 a1 a2 …) * (b0 b1 b2 …) = ca * cb + ca * (b0 b1 b2 …) + (a0 a1 a2 …) * (cb b0 b1 b2 …)。

(define (mul-series s1 s2)
  (cons-stream (* (stream-car s1) (stream-car s2))
               (add-streams (scale-stream (stream-cdr s2) (stream-car s1))
                            (mul-series (stream-cdr s1) s2))))

E-3.61:

(define (invert-unit-series stream)
  (cons-stream 1 (scale-stream (mul-series (stream-cdr stream)
                                           (invert-unit-series stream))
                               -1)))

E-3.62: 使用 invert-unit-series 前需要先将分母的常数变为 1,这也是为什么常数不能为 0 的原因。

(define (div-series s1 s2)
  (let ((c2 (stream-car s2)))
    (if (= c2 0)
      (display "error\n")
      (mul-series (scale-stream s1 (/ 1 c2))
                  (invert-unit-series (scale-stream s2 (/ 1 c2)))))))

E-3.63: 通过在 lambda 中加入打印每次计算的 guess 值可以看到题中的写法的确存在重复计算。使用了 guesses 变量后,每次访问后续的元素的时候都能直接从链表中取出(本地变量相当于对已有计算结果的一个引用),而直接写的话就是一个函数调用,每次都得从头计算。

如果没有使用 memo-proc,则没有记忆功能,也就是说每次使用流的时候都要重新计算,这样两者就一样了。

E-3.64:

(load "../examples/3.5.3-exploiting-the-stream-paradigm.scm")

(define (stream-limit stream tolerance)
  (let ((first (stream-ref stream 0))
        (second (stream-ref stream 1)))
    (if (< (abs (- first second)) tolerance)
      second
      (stream-limit (stream-cdr stream) tolerance))))

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

(define (my-sqrt x tolerance)
  (stream-limit (sqrt-stream x) tolerance))

(my-sqrt 2 0.000001)

E-3.65: 模仿pi的计算。

(load "../examples/3.5.3-exploiting-the-stream-paradigm.scm")

(define (ln2-summands n)
  (cons-stream (/ 1.0 n)
               (stream-map - (ln2-summands (+ n 1)))))

(define ln2-stream
  (partial-sums (ln2-summands 1)))

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

;(display-stream-n ln2-stream 10)
;(display-stream-n (euler-transform ln2-stream) 10)
(display-stream-n (accelerated-sequence euler-transform ln2-stream) 10)

E-3.66: interleave 的取法是,从右上角(第一排)和右下角(去掉第一行和第一列后剩下的部分)之间轮流取一个元素。也就是说,当 i>1 时,(1,i) 和 (1,i+1) 之间隔着一个右下角的元素。而 (1,1) 是第一个被取到的元素,然后从 interleave 的结果中取下一个元素,因此取到 (1,100) 时一共取了 1+99+98=198 个元素。

令 f(n,n) 表示取到 (n,n) 时一共取的元素个数。先找一下规律:

f(2,2) – f(1,2) = 0 = 2^0 – 1
f(3,3) – f(2,3) = 1 = 2^1 – 1
f(4,4) – f(3,4) = 3 = 2^2 – 1
f(5,5) – f(4,5) = 7 = 2^3 – 1
f(6,6) – f(5,6) = 15 = 2^4 – 1
f(7,7) – f(6,7) = 31 = 2^5 – 1

即 f(n,n) – f(n-1,n) = 2^(n-2) – 1,其中 n>=2。

再看下一组规律:

f(2,2) – f(1,1) = 1
f(3,3) – f(2,2) = 3
f(4,4) – f(3,3) = 7
f(5,5) – f(4,4) = 15
f(6,6) – f(5,5) = 31

同理可得:f(n,n) – f(n-1, n-1) = 2^(n-1) – 1,其中 n>=2。

初值 f(1,1)=1,解得 f(n,n) = 2^n + n – 2,其中 n>=2。

于是

f(100,100) = 2^100 + 100 – 2 = 2^100 + 98
f(99,100) = f(100,100) – 2^98 + 1 = 2^100 + 98 – 2^98 + 1 = 2^100 – 2^98 + 99

E-3.67: 把第一列剩余的部分加上。

(load "../examples/3.5.3-exploiting-the-stream-paradigm.scm")

(define (full-pairs s t)
  (cons-stream (list (stream-car s) (stream-car t))
               (interleave
                 (interleave
                   (stream-map (lambda (x)
                                 (list x (stream-car t)))
                               (stream-cdr s))
                   (stream-map (lambda (x)
                                 (list (stream-car s) x))
                               (stream-cdr t)))
                 (pairs (stream-cdr s) (stream-cdr t)))))

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

(display-stream-n (full-pairs integers integers) 20)

E-3.68: 在做 3.66 的时候已经想到这个问题了,当时发现是死循环,但是没想到是为啥。原因见参考资料 [3],原文部分摘录如下:

猛地想起来,虽然stream是lazy的,但scheme本身不是lazy的啊!

尤其是,scheme的函数调用,仍然是call-by-value的!

也就是说,尽管调用pairs后,我们只需要计算完interleave的第一个参数(stream-map ...)的第一个元素就可以输出(而在此时,这已经可以计算出来了),但由于call-by-value的限制,我们明知计算第二个参数没有用,还是得先计算才行!

问题就出在这里,第二个参数是什么?是对pairs的递归调用!而根据刚才的分析,这一调用同样还会进行更进一步的递归……而这个过程是无穷的!

于是就只能挂掉了……

而示例程序之所以不会错,正是因为将第一项独立出来马上可以取到,而避免了先要进行无谓计算的问题。

E-3.69: 先利用 pairs 生成二元组,再从二元组和第三维生成三元组。

(load "../examples/3.5.3-exploiting-the-stream-paradigm.scm")

(define (triples s t u)
  (stream-map (lambda (x)
                (append (car x) (cdr x)))
              (pairs (pairs s t) u)))

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

(display-stream-n (triples integers integers integers) 100)

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

(stream-filter (lambda (x)
                 (= (+ (square (car x))
                       (square (cadr x)))
                    (square (caddr x))))
               (triples integers integers integers))

E-3.70: 因为 p1 和 p2 是两个不同的整数对,因此 merge 不能在 weight 相等的时候只取 p1 或 p2。还有就是用 merge-weighted 取代了原来的 interleave。这里不能把 weight-pairs 定义成“(merge-weighted integer-pairs integer-pairs weight)”,原因如 3.68 所述。

(load "../examples/3.5.3-exploiting-the-stream-paradigm.scm")

(define (merge-weighted s1 s2 weight)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
          (let ((s1car (stream-car s1))
                (s2car (stream-car s2)))
            (cond ((< (weight s1car) (weight s2car))
                   (cons-stream
                     s1car
                     (merge-weighted (stream-cdr s1) s2 weight)))
                  (else
                    (cons-stream
                      s2car
                      (merge-weighted s1 (stream-cdr s2) weight))))))))

(define (weighted-pairs s t weight)
  (cons-stream (list (stream-car s) (stream-car t))
               (merge-weighted (stream-map (lambda (x)
                                             (list (stream-car s) x))
                                           (stream-cdr t))
                               (weighted-pairs (stream-cdr s) (stream-cdr t) weight)
                               weight)))

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

(weighted-pairs integers integers
                (lambda (x)
                  (+ (car x) (cadr x))))

(define not235
  (stream-filter (lambda (x)
                   (and (not (= 0 (remainder x 2)))
                        (not (= 0 (remainder x 3)))
                        (not (= 0 (remainder x 5)))))
                 integers))

(weighted-pairs not235 not235
                (lambda (x)
                  (let ((i (car x))
                        (j (cadr x)))
                    (+ (* 2 i) (* 3 j) (* 5 i j)))))

E-3.71:

(load "../exercises/3.70.scm")

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

(define (cube-sum pair)
  (+ (cube (car pair)) (cube (cadr pair))))

(define cube-sum-list
  (stream-map cube-sum
              (weighted-pairs integers integers cube-sum)))

(define (ramanujan s)
  (let ((first (stream-car s))
        (second (stream-car (stream-cdr s))))
    (if (= first second)
      (cons-stream first
                   (ramanujan (stream-cdr s)))
      (ramanujan (stream-cdr s)))))

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

(display-stream-n (ramanujan cube-sum-list) 10)

接下来的5个依次是:4104,13832,20683,32832,39312。

E-3.72: 仿照3.71的做法即可。

(load "../exercises/3.70.scm")

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

(define (square-sum pair)
  (+ (square (car pair)) (square (cadr pair))))

(define square-sum-list
  (stream-map (lambda (x)
                (append (list (square-sum x)) x)) ; 第一个是平方和,后面是pair
              (weighted-pairs integers integers square-sum)))

(define (square-3 s)
  (let ((first (stream-car s))
        (second (stream-car (stream-cdr s)))
        (third (stream-car (stream-cdr (stream-cdr s)))))
    (if (and (= (car first) (car second))
             (= (car first) (car third)))
      (cons-stream (list first second third)
                   (square-3 (stream-cdr s)))
      (square-3 (stream-cdr s)))))

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

(display-stream-n (square-3 square-sum-list) 10)

参考资料

[1] SICP 3.5时delay的疑问(关于PLT Scheme)
[2] 练习 3.59
[3] SICP学习笔记之二:“微小”的差别……

发表于 2014年1月5日
本文目前尚无任何评论.

发表评论

XHTML: 您可以使用这些标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>