SICP 习题参考答案，3.5

win_hate

•   生成三元组
  
  
  • 分析：
    
    [1, 2,...] X [1, 2, ...] X [1,2,...] 构成的三元组，其中分量按下标非严格递增。
    
    可以分成两类，一类是 (1, *, * ) 的，另一类是 [2,3,...] X [2,3,...] X [2,3,...] 形成的三元组。
    
    第一类可以把 1 插入 [1,2,...] X [1,2,...] 形成的二元组，第二类简单地递归。所以有
    
    
    1. 
       
    2. (define (triples s)
       
    3.   (define (f x)
       
    4.     (lambda (y) (cons x y)))
       
    5.   (let ((a (stream-car s)))
       
    6.     (cons-stream
       
    7.      (list a a a)
       
    8.      (interleave (stream-map (f a)
       
    9.                              (stream-cdr (pairs s s)))
       
    10.                  (triples (stream-cdr s))))))
        

    复制代码
    
    
  • 演示：
    
    
    1. 
       
    2. > (print-stream (triples integers) 10)
       
    3. (1 1 1)
       
    4. (1 1 2)
       
    5. (2 2 2)
       
    6. (1 2 2)
       
    7. (2 2 3)
       
    8. (1 1 3)
       
    9. (3 3 3)
       
    10. (1 2 3)
        
    11. (2 3 3)
        
    12. (1 1 4)
        

    复制代码
    
    
  • 生成 Pythagoras 三元组
    
    用一个谓词函数去过滤即可
    
    
    1. 
       
    2. (define (select x)
       
    3.   (define (square x) (* x x))
       
    4.   (let ((a (car x)) (b (cadr x))
       
    5.         (c (caddr x)))
       
    6.     (= (+ (square a) (square b))
       
    7.        (square c))))
       
    8. 
       
    9. (define Pythagoras
       
    10.   (stream-filter select (triples integers)))
        

    复制代码
    
    
  • 演示
    
    
    1. 
       
    2. > (print-stream Pythagoras 6)
       
    3. (3 4 5)
       
    4. (6 8 10)
       
    5. (5 12 13)
       
    6. (9 12 15)
       
    7. (8 15 17)
       
    8. (12 16 20)
       

    复制代码
    
    
  • 作为练习，作者无疑是想让读者使用上述过滤的方式来生成 Pythagoras 三元组。不过这个方法效率很低，事实上我无法计算出第 7 组数。我们看一下上面滤出来的第 6 组数处在流中的什么位置。
    
    
    1. 
       
    2. (define (index x s)
       
    3.   (define (f s i)
       
    4.     (if (equal? (stream-car s)  x) i
       
    5.         (f (stream-cdr s) (+ i 1))))
       
    6.   (f s 0))
       

    复制代码
    
    
    1. 
       
    2. > (index '(12 16 20) (triples integers))
       
    3. 583678
       

    复制代码
    
    
  • 另一个方法。事实上，Pythagoras 三元组是有公式的。
    
    如果 (a,b,c) 是一个 Pythagoras 三元组，则 (ak, bk, ck) 也是。所以只要求出互素的三元组就可以了，这样的三元组称为本原解。本原解可表示为
    

    (a, b, c) = (s^2-r^2, 2sr, s^2+r^2)  ;; 次序不计
    其中 (r, s)=1, a+b 为奇数, s>r

    
    
    所以我们只要用 pairs 生成二元组，并过滤出互素且分量和为奇数的序列，然后把公式 map 上去即可。
    
    
    1. 
       
    2. (define (f x)
       
    3.   (let* ((a (car x))
       
    4.         (b (cadr x))
       
    5.         (aa (* a a))
       
    6.         (bb (* b b)))
       
    7.     (list (- bb aa) (* 2 a b) (+ aa bb))))
       
    8. 
       
    9. (define (p x)
       
    10.   (let ((a (car x)) (b (cadr x)))
        
    11.     (and (= 1 (gcd a b))
        
    12.          (odd? (+ a b)))))
        
    13.         
        
    14. (define Fast-Pythagoras
        
    15.   (cons-stream (list 0 0 0)
        
    16.                (stream-map f
        
    17.                 (stream-filter p
        
    18.                  (pairs integers integers)))))
        

    复制代码
    
    
  • 演示：
    
    
    1. 
       
    2. (print-stream Fast-Pythagoras 20)
       
    3. (0 0 0)
       
    4. 
       
    5. (3 4 5)
       
    6. 
       
    7. (5 12 13)
       
    8. 
       
    9. (15 8 17)
       
    10. 
        
    11. (35 12 37)
        
    12. 
        
    13. (7 24 25)
        
    14. 
        
    15. (21 20 29)
        
    16. 
        
    17. (63 16 65)
        
    18. 
        
    19. (99 20 101)
        
    20. 
        
    21. (45 28 53)
        
    22. 
        
    23. (143 24 145)
        
    24. 
        
    25. (9 40 41)
        
    26. 
        
    27. (195 28 197)
        
    28. 
        
    29. (77 36 85)
        
    30. 
        
    31. (255 32 257)
        
    32. 
        
    33. (323 36 325)
        
    34. 
        
    35. (117 44 125)
        
    36. 
        
    37. (399 40 401)
        
    38. 
        
    39. (483 44 485)
        
    40. 
        
    41. (55 48 73)
        

    复制代码
    
    
    为了简洁，我把 (0, 0, 0) 也生成了，它是一个平凡解。前面使用直接过滤生成的 6 组数中，有一些不是本原解，所以在这里没有出现。
    
  
  
  

[ 本帖最后由 win_hate 于 2009-2-3 20:51 编辑 ]

win_hate

Exercise 3.70.  It would be nice to be able to generate streams in which the pairs appear in some useful order, rather than in the order that results from an ad hoc interleaving process. We can use a technique similar to the merge procedure of exercise 3.56, if we define a way to say that one pair of integers is ``less than'' another. One way to do this is to define a ``weighting function'' W(i,j) and stipulate that (i_1,j_1) is less than (i_2,j_2) if W(i_1,j_1) < W(i_2,j_2). Write a procedure merge-weighted that is like merge, except that merge-weighted takes an additional argument weight, which is a procedure that computes the weight of a pair, and is used to determine the order in which elements should appear in the resulting merged stream.[69] Using this, generalize pairs to a procedure weighted-pairs that takes two streams, together with a procedure that computes a weighting function, and generates the stream of pairs, ordered according to weight. Use your procedure to generate

a. the stream of all pairs of positive integers (i,j) with i < j ordered according to the sum i + j

b. the stream of all pairs of positive integers (i,j) with i < j, where neither i nor j is divisible by 2, 3, or 5, and the pairs are ordered according to the sum 2 i + 3 j + 5 i j.

[69] We will require that the weighting function be such that the weight of a pair increases as we move out along a row or down along a column of the array of pairs.

win_hate

• 分析
  
  注意注释 69。该注释强调了 weight (i,j) 应该分别关于 i 和 j 非严格上升。
  
  
  • 我们生成的上三角二元组可以分为两类，一类是第一行，即 (1,*) 模式，另一类为下面的行。
  • 把 weight map 到第一行，显然得到一个排序好的流(上升)。
  • 那另一个流有怎么样呢？另一个流被递归处理，只要递归成立，则它也是一个上升流。
  • 现在我们有了两个上升流。用一个按序提取的 interlever，即 merge 就可以合并成一个上升流。(其实就是 merge sort)。
  • 不过且慢，第二个流是递归处理的，它本身又是两个流的混合。为得到第二个流的第一个数，我们要把另两个流混合。但这两个流
    中又有一个是两个流的混合......
    于是我们陷入了无终止的后退，一个数都出不来。
  • 注意到 (2,2) 是第二个流中最小的，所以在递归时，以它为第一项。这样 merge 就可以马上进行，不会出现前面所说的无穷后退。
  • 所以这里把 (1,1) 或 (2,2)，或 (i,i) 单独处理，有两个理由。一个是标准 scheme 的惰性不够（见 Exercise 3.68），一个是为
    了避免前面所说的无穷后退。
  • 可以看到，注释 69 很重要。如果 weight  函数选择不当，则第一个流是未排序的，按序 merge 也就无从谈起。
    
  
  按 weight 的定义， (2,2) 是这个流中的最小元素。
• 代码
  
  
  1. 
     
  2. (define (pairs-weight s1 s2 weight)
     
  3.   (if (or (stream-null? s1)) '()
     
  4.       (cons-stream
     
  5.        (list (stream-car s1) (stream-car s2))
     
  6.        (merge-weight
     
  7.         (stream-map (lambda (x) (list (stream-car s1) x))
     
  8.                     (stream-cdr s2))
     
  9.         (pairs-weight (stream-cdr s1)
     
  10.                       (stream-cdr s2) weight)
      
  11.         weight))))
      

  复制代码
  
  
• a.
  
  
  1. 
     
  2. (define (f x)
     
  3.   (apply + x))
     
  4. 
     
  5. (define A (pairs-weight integers
     
  6.                         integers f))
     

  复制代码
  
  
  1. 
     
  2. (take A 10)
     
  3. ((1 1) (1 2) (1 3) (2 2) (1 4) (2 3) (1 5) (2 4) (3 3) (1 6))
     

  复制代码
  
  
• b.
  
  
  1. 
     
  2. (define (g x)
     
  3.   (apply
     
  4.    (lambda (i j) (+ (* 2 i) (* 3 j) (* 5 i j)))
     
  5.    x))
     
  6. 
     
  7. (define S
     
  8.   (stream-filter
     
  9.    (lambda (x)
     
  10.      (not (or (= 0 (modulo x 2))
      
  11.               (= 0 (modulo x 3))
      
  12.               (= 0 (modulo x 5)))))
      
  13.    integers))
      
  14. 
      
  15. (define B (pairs-weight S S g))
      

  复制代码
  
  
  1. 
     
  2. > (take B 10)
     
  3. ((1 1) (1 7) (1 11) (1 13) (1 17) (1 19) (1 23) (1 29) (1 31) (7 7))
     

  复制代码
  
  
  注意，中文版在这里有个小错误。p238 中间，
  
  

  错误：而且这里的 i 或者 j 可以被 2, 3, 5 整除
  正确：而且这里的 i 和 j 都不可以被 2, 3, 5 整除

  
  [ 本帖最后由 win_hate 于 2009-2-3 23:43 编辑 ]

win_hate

Exercise 3.71.  Numbers that can be expressed as the sum of two cubes in more than one way are sometimes called Ramanujan numbers, in honor of the mathematician Srinivasa Ramanujan.70 Ordered streams of pairs provide an elegant solution to the problem of computing these numbers. To find a number that can be written as the sum of two cubes in two different ways, we need only generate the stream of pairs of integers (i,j) weighted according to the sum i3  + j3 (see exercise 3.70), then search the stream for two consecutive pairs with the same weight. Write a procedure to generate the Ramanujan numbers. The first such number is 1,729. What are the next five?

win_hate

• 分析
  
  • 先按 w(i,j)=i^3+j^3 得到一个排序的流。
  • 再把一个函数 map 到此流上，把流中元素 (i,j) 变为 (i^3+j^3, (i,j))
  • 再把另一个函数 map 到新的流上，此函数以重量相同为标准，把相邻的项合并成 (总项数，重量，项 1， 项 2 ....)
    
  
  
• 代码
  
  
  1. 
     
  2. (define (f x)
     
  3.   (let ((a (car x))
     
  4.         (b (cadr x)))
     
  5.     (+ (* a a a) (* b b b))))
     
  6. 
     
  7. (define Ramanujans-stream
     
  8.   (stream-map
     
  9.    (lambda (x) (list (f x) x))
     
  10.    (pairs-weight integers integers f)))
      
  11. 
      
  12. (define (group-with-weight s)
      
  13.   (define (g s w cur cnt)
      
  14.     (let ((a (stream-car s)))
      
  15.       (if (= (car a) w)
      
  16.           (g (stream-cdr s) w
      
  17.              (cons (cadr a) cur) (+ cnt 1))
      
  18.           (cons-stream
      
  19.            (cons cnt (cons w cur))
      
  20.            (g (stream-cdr s) (car a) (cdr a) 1)))))
      
  21.   (let ((b (stream-car s)))
      
  22.     (g (stream-cdr s) (car b)
      
  23.        (cdr b) 1)))
      
  24. 
      
  25. (define R
      
  26.   (stream-filter (lambda (x) (= (car x) 2))
      
  27.                  (group-with-weight Ramanujans-stream)))
      

  复制代码
  
  
• 演示
  
  1. 
     
  2. > (print-stream R 10)
     
  3. 
     
  4. (2 1729 (9 10) (1 12))
     
  5. 
     
  6. (2 4104 (9 15) (2 16))
     
  7. 
     
  8. (2 13832 (18 20) (2 24))
     
  9. 
     
  10. (2 20683 (19 24) (10 27))
      
  11. 
      
  12. (2 32832 (18 30) (4 32))
      
  13. 
      
  14. (2 39312 (15 33) (2 34))
      
  15. 
      
  16. (2 40033 (16 33) (9 34))
      
  17. 
      
  18. (2 46683 (27 30) (3 36))
      
  19. 
      
  20. (2 64232 (26 36) (17 39))
      
  21. 
      
  22. (2 65728 (31 33) (12 40))
      

  复制代码
  
  

[ 本帖最后由 win_hate 于 2009-2-3 21:04 编辑 ]

win_hate

Exercise 3.72.  In a similar way to exercise 3.71 generate a stream of all numbers that can be written as the sum of two squares in three different ways (showing how they can be so written).

win_hate

• 与上题类似
  
• 代码
  
  1. 
     
  2. (define (g x)
     
  3.   (let ((a (car x))
     
  4.         (b (cadr x)))
     
  5.     (+ (* a a) (* b b))))
     
  6. 
     
  7. (define sum-of-square
     
  8.   (stream-map (lambda (x) (list (g x) x))
     
  9.               (pairs-weight integers integers g)))
     
  10. 
      
  11. (define square-of-tree
      
  12.   (stream-filter (lambda (x) (= (car x) 3))
      
  13.                  (group-with-weight sum-of-square)))
      

  复制代码
  
  
• 演示
  
  
  1. 
     
  2. > (print-stream square-of-tree 10)
     
  3. 
     
  4. (3 325 (10 15) (6 17) (1 18))
     
  5. 
     
  6. (3 425 (13 16) (8 19) (5 20))
     
  7. 
     
  8. (3 650 (17 19) (11 23) (5 25))
     
  9. 
     
  10. (3 725 (14 23) (10 25) (7 26))
      
  11. 
      
  12. (3 845 (19 22) (13 26) (2 29))
      
  13. 
      
  14. (3 850 (15 25) (11 27) (3 29))
      
  15. 
      
  16. (3 925 (21 22) (14 27) (5 30))
      
  17. 
      
  18. (3 1025 (20 25) (8 31) (1 32))
      
  19. 
      
  20. (3 1250 (25 25) (17 31) (5 35))
      
  21. 
      
  22. (3 1300 (20 30) (12 34) (2 36))
      

  复制代码
  
  [ 本帖最后由 win_hate 于 2009-2-3 21:02 编辑 ]

win_hate

Exercise 3.73.  

                                          



Figure 3.33:  An RC circuit and the associated signal-flow diagram.

We can model electrical circuits using streams to represent the values of currents or voltages at a sequence of times. For instance, suppose we have an RC circuit consisting of a resistor of resistance R and a capacitor of capacitance C in series. The voltage response v of the circuit to an injected current i is determined by the formula in figure 3.33, whose structure is shown by the accompanying signal-flow diagram.

Write a procedure RC that models this circuit. RC should take as inputs the values of R, C, and dt and should return a procedure that takes as inputs a stream representing the current i and an initial value for the capacitor voltage v0 and produces as output the stream of voltages v. For example, you should be able to use RC to model an RC circuit with R = 5 ohms, C = 1 farad, and a 0.5-second time step by evaluating (define RC1 (RC 5 1 0.5)). This defines RC1 as a procedure that takes a stream representing the time sequence of currents and an initial capacitor voltage and produces the output stream of voltages.

[ 本帖最后由 win_hate 于 2009-2-11 10:16 编辑 ]

win_hate

• 代码
  
  按图 3-33 写的
  
  
  1. 
     
  2. (define (RC R C dt)
     
  3.   (lambda (IS v0)
     
  4.     (let* ((s1 (scale-stream IS (/ 1 C)))
     
  5.            (s2 (integral s1 v0 dt))
     
  6.            (s3 (scale-stream IS R)))
     
  7.       (add-streams s2 s3))))
     
  8. 
     
  9. (define RC1 (RC 5 1 0.5))
     

  复制代码
  
  
• 演示
  
  
  1. 
     
  2. > (define s (cons-stream 1 s))
     
  3. 
     
  4. > (define v (RC1 s 1))
     
  5. 
     
  6. > (take v 10)
     
  7. (6 6.5 7.0 7.5 8.0 8.5 9.0 9.5 10.0 10.5)
     

  复制代码
  
  

win_hate

Exercise 3.74.  Alyssa P. Hacker is designing a system to process signals coming from physical sensors. One important feature she wishes to produce is a signal that describes the zero crossings of the input signal. That is, the resulting signal should be + 1 whenever the input signal changes from negative to positive, - 1 whenever the input signal changes from positive to negative, and 0 otherwise. (Assume that the sign of a 0 input is positive.) For example, a typical input signal with its associated zero-crossing signal would be

...1  2  1.5  1  0.5  -0.1  -2  -3  -2  -0.5  0.2  3  4 ...... 0  0    0  0    0     -1  0   0   0     0    1  0  0 ...

In Alyssa's system, the signal from the sensor is represented as a stream sense-data and the stream zero-crossings is the corresponding stream of zero crossings. Alyssa first writes a procedure sign-change-detector that takes two values as arguments and compares the signs of the values to produce an appropriate 0, 1, or - 1. She then constructs her zero-crossing stream as follows:

(define (make-zero-crossings input-stream last-value)
  (cons-stream
   (sign-change-detector (stream-car input-stream) last-value)
   (make-zero-crossings (stream-cdr input-stream)
                        (stream-car input-stream))))

(define zero-crossings (make-zero-crossings sense-data 0))

Alyssa's boss, Eva Lu Ator, walks by and suggests that this program is approximately equivalent to the following one, which uses the generalized version of stream-map from exercise 3.50:

(define zero-crossings
  (stream-map sign-change-detector sense-data <expression>))

Complete the program by supplying the indicated <expression>.