SICP 习题参考答案，3.5

win_hate

• 分析
  
  • 用一个函数 pm 取信号判断信号的符号。如果负返回 -1，否则 +1。在此基础上实现 sign-change-detector，满足：
    
    

    (+1, +1) -> 0
    (-1, -1) -> 0
    (+1, -1) -> +1        ;; 注意，根据书本上对 sign-change-detector 的调用，第二个参数是先出现的信号。
    (-1, +1) -> -1

    
    
    1. 
       
    2. (define (pm x)
       
    3.   (if (>= x 0) 1 -1))
       
    4.         
       
    5. (define (sign-change-detector signal last-value)
       
    6.   (let ((s1 (pm last-value)) (s2 (pm signal)))
       
    7.         (/ (- s2 s1) 2)))
       

    复制代码
    
    
  • 按书本上 zero-crossing 的定义，作者实际上在流首插入了一个辅助信号 0，用于计算第一个信号的 zero-crossing
    
  • 书本上的序列
    ...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 ...
    有点问题。
    
    1->2: 0
    2->1.5: 0
    1.5->1: 0
    1-> 0.5: 0
    0.5-> -1: -1
    
    所以是 4 个 0 后跟一个 1，但书本上的 zero-crossing 序列是 5 个 0 后跟一个 1。
    
    如果把两个序列起头的省略号去掉，并认为信号序列前有一个辅助的 0，则 zero-crossing 序列是 5 个 0 起头。
    
  • 为测试书本上的数据，我们的代码必须能处理有限的流（因为书上的数据只有有限项）。可以在有限流后附加一个常数，变成无限流；
    也可以修改我们的流处理代码（stream-map, take 等），使之能处理有限流。在这里，我们用后一种方法。
    
  
  
• 代码
  
  
  1. 
     
  2. (define sense-data
     
  3.   (list->stream '(1 2 1.5 1 0.5 -0.1 -2 -3 -2 -0.5 0.2 3 4)))
     
  4. 
     
  5. (define (pm x)
     
  6.   (if (>= x 0) 1 -1))
     
  7.         
     
  8. (define (sign-change-detector signal last-value)
     
  9.   (let ((s1 (pm last-value)) (s2 (pm signal)))
     
  10.         (/ (- s2 s1) 2)))
      
  11.          
      
  12. (define (make-zero-crossings input-stream last-value)
      
  13.   (if (stream-null? input-stream) '()
      
  14.       (cons-stream
      
  15.        (sign-change-detector (stream-car input-stream) last-value)
      
  16.        (make-zero-crossings (stream-cdr input-stream)
      
  17.                             (stream-car input-stream)))))
      
  18.   
      
  19. (define zero-crossings (make-zero-crossings sense-data 0))
      
  20. 
      
  21. (define zero-crossings-1
      
  22.   (stream-map sign-change-detector sense-data
      
  23.               (cons-stream 0 sense-data)))
      

  复制代码
  
  
• 演示：
  
  100 多于实际的项数，take 只返回有限项。
  
  
  1. 
     
  2. > (take zero-crossings 100)
     
  3. (0 0 0 0 0 -1 0 0 0 0 1 0 0)
     
  4. 
     
  5. > (take zero-crossings-1 100)
     
  6. (0 0 0 0 0 -1 0 0 0 0 1 0 0)
     

  复制代码
  
  

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

win_hate

Exercise 3.75.  Unfortunately, Alyssa's zero-crossing detector in exercise 3.74 proves to be insufficient, because the noisy signal from the sensor leads to spurious zero crossings. Lem E. Tweakit, a hardware specialist, suggests that Alyssa smooth the signal to filter out the noise before extracting the zero crossings. Alyssa takes his advice and decides to extract the zero crossings from the signal constructed by averaging each value of the sense data with the previous value. She explains the problem to her assistant, Louis Reasoner, who attempts to implement the idea, altering Alyssa's program as follows:

(define (make-zero-crossings input-stream last-value)
  (let ((avpt (/ (+ (stream-car input-stream) last-value) 2)))
    (cons-stream (sign-change-detector avpt last-value)
                 (make-zero-crossings (stream-cdr input-stream)
                                      avpt))))

win_hate

• 分析
  
  设信号序列为： x(0), x(1), x(2), ...
  
  目标是平滑出另一个序列： y(0), y(1), y(2), ....
  
  满足
  

  y(0)=x(0)        ;; 第一项如何处理，书本没有说明。我认为保留第一项比较合理。
  2 y(n)=x(n-1)+x(n)

  
  
  Louis Reasoner 的代码对应的递推公式为：
  
  y(n)=(x(n)+y(n-1)) /2
  
  
• 代码：
  
  
  1. 
     
  2. (define (make-zero-crossings input-stream last-value org-value)
     
  3.   (let ((avpt (/ (+ (stream-car input-stream) org-value) 2)))
     
  4.     (cons-stream (sign-change-detector avpt last-value)
     
  5.                  (make-zero-crossings (stream-cdr input-stream)
     
  6.                                       avpt (stream-car input-stream)))))
     
  7. 
     
  8. (define zero-crossings (make-zero-crossings sense-data 0 0))
     

  复制代码
  
  
• 演示
  
  
  1. 
     
  2. > (take zero-crossings  12)
     
  3. (0 0 0 0 0 0 -1 0 0 0 0 1)
     

  复制代码
  
  

win_hate

Exercise 3.76.  Eva Lu Ator has a criticism of Louis's approach in exercise 3.75. The program he wrote is not modular, because it intermixes the operation of smoothing with the zero-crossing extraction. For example, the extractor should not have to be changed if Alyssa finds a better way to condition her input signal. Help Louis by writing a procedure smooth that takes a stream as input and produces a stream in which each element is the average of two successive input stream elements. Then use smooth as a component to implement the zero-crossing detector in a more modular style.

win_hate

• 代码
  
  1. 
     
  2. (define (smooth s)
     
  3.   (cons-stream
     
  4.    (stream-car s)
     
  5.    (stream-map (lambda (x y) (/ (+ x y) 2))
     
  6.               s (stream-cdr s))))
     
  7. 
     
  8. (define zero-crossings
     
  9.   (make-zero-crossings (smooth sense-data) 0))
     

  复制代码
  
  
  
• 演示
  
  1. 
     
  2. > (take zero-crossings 100)
     
  3. (0 0 0 0 0 0 -1 0 0 0 0 1 0)
     

  复制代码

win_hate

Exercise 3.77.  The integral procedure used above was analogous to the ``implicit'' definition of the infinite stream of integers in section 3.5.2. Alternatively, we can give a definition of integral that is more like integers-starting-from (also in section 3.5.2):

(define (integral integrand initial-value dt)
  (cons-stream initial-value
               (if (stream-null? integrand)
                   the-empty-stream
                   (integral (stream-cdr integrand)
                             (+ (* dt (stream-car integrand))
                                initial-value)
                             dt))))

When used in systems with loops, this procedure has the same problem as does our original version of integral. Modify the procedure so that it expects the integrand as a delayed argument and hence can be used in the solve procedure shown above.

win_hate

1. 
   
2. (define (integral delayed-integrand initial-value dt)
   
3.     (cons-stream initial-value
   
4.                  (let ((integrand (force delayed-integrand)))
   
5.                    (if (stream-null? integrand)
   
6.                        the-empty-stream
   
7.                        (integral (delay (stream-cdr integrand))
   
8.                                  (+ (* dt (stream-car integrand))
   
9.                                     initial-value)
   
10.                                  dt)))))
    

复制代码

演示:

1. 
   
2. > (stream-ref (solve (lambda (y) y) 1 0.001) 1000)
   
3. 2.716923932235896
   

复制代码

注意，相应的 solve 代码为：

1. 
   
2. (define (solve f y0 dt)
   
3.   (define y (integral (delay dy) y0 dt))
   
4.   (define dy (stream-map f y))
   
5.   y)
   

复制代码

此代码在 guile 中运行时会出错，说 y 没有定义。 注释 199 也指出了并不是每种解释器都支持上述写法。我是用 mzscheme 来做这个题目的。

如果只有 guile，则可以把 solve 函数肢解掉再用：

1. 
   
2. guile> (define y (integral (delay dy) 1 0.001))
   
3. guile> (define dy (stream-map (lambda (y) y) y))
   
4. guile> (stream-ref y 1000)
   
5. 2.7169239322359
   

复制代码