SICP 习题参考答案，3.5

win_hate

1. 
   
2. (define (stream-limit s t)
   
3.   (define (f a s)
   
4.     (let ((b (stream-car s)))
   
5.       (if (< (abs (- a b)) t) b
   
6.           (f b (stream-cdr s)))))
   
7.   (f (stream-car s) (stream-cdr s)))
   
8. 
   
9. 
   
10. (define (sqrt x tolerance)
    
11.   (stream-limit (sqrt-stream x) tolerance))
    

复制代码

演示

1. 
   
2. > (sqrt 2 0.00001)
   
3. 1.41421356237469
   

复制代码

win_hate

Exercise 3.65.  Use the series



to compute three sequences of approximations to the natural logarithm of 2, in the same way we did above for . How rapidly do these sequences converge?

win_hate

• 
  
  1. 
     
  2. (define harmonic-float
     
  3.   (stream-map (lambda (x) (/ 1.0 x)) integers))
     
  4. 
     
  5. (define (alternizer s)
     
  6.   (let* ((a (stream-car s))
     
  7.         (s1 (stream-cdr s))
     
  8.         (b (stream-car s1)))
     
  9.     (cons-stream a
     
  10.                  (cons-stream (* -1 b)
      
  11.                               (alternizer (stream-cdr s1))))))
      

  复制代码
  
  
  alternizer 作用在一个流上，把奇数项保持不变，偶数项乘上 -1.
  
  harmonic-float 生成调和级数。
  
  把 alternizer 作用在调和级数上就得到了 ln 2 对应的级数
  
  
  1. 
     
  2. (define log2-series
     
  3.   (alternizer harmonic-float))
     
  4. 
     
  5. (define log2-stream
     
  6.   (partial-sums log2-series))
     

  复制代码
  
  
• 加速和不加速的版本
  
  
  1. 
     
  2. (define s1 log2-stream)
     
  3. (define s2 (euler-transform s1))
     
  4. (define s3 (accelerated-sequence euler-transform
     
  5.                                  s1))
     

  复制代码
  
  
• 收敛速度对比：
  
  
  1. 
     
  2. > (log 2)
     
  3. 0.693147180559945
     
  4. 
     
  5. > (print-stream s1 10)
     
  6. 1.0
     
  7. 0.5
     
  8. 0.833333333333333
     
  9. 0.583333333333333
     
  10. 0.783333333333333
      
  11. 0.616666666666667
      
  12. 0.759523809523809
      
  13. 0.634523809523809
      
  14. 0.745634920634921
      
  15. 0.645634920634921
      
  16. 
      
  17. > (print-stream s2 10)
      
  18. 0.7
      
  19. 0.690476190476191
      
  20. 0.694444444444444
      
  21. 0.692424242424242
      
  22. 0.693589743589744
      
  23. 0.692857142857143
      
  24. 0.693347338935574
      
  25. 0.693003341687552
      
  26. 0.693253968253968
      
  27. 0.693065750674446
      
  28. 
      
  29. > (print-stream s3 10)
      
  30. 1.0
      
  31. 0.7
      
  32. 0.69327731092437
      
  33. 0.693148869332925
      
  34. 0.693147196073549
      
  35. 0.693147180663564
      
  36. 0.693147180560404
      
  37. 0.693147180559945
      
  38. 0.693147180559943
      
  39. 0.693147180559945
      

  复制代码
  
  
• 继续对比
  
  
  1. 
     
  2. > (log 2)
     
  3. 0.693147180559945
     
  4. 
     
  5. > (stream-ref s1 10000)
     
  6. 0.693197173060958
     
  7. 
     
  8. > (stream-ref s2 100)
     
  9. 0.693147296621065
     
  10. 
      
  11. > (stream-ref s3 10)
      
  12. +nan.0                            ;; orz, what is this?
      
  13. 
      
  14. > (stream-ref s3 9)
      
  15. 0.693147180559945
      
  16. 
      
  17. > (log 2)
      
  18. 0.693147180559945
      

  复制代码
  
  
  可以看到 s3 中只用了 10 项就准确地计算出了 log 2 的 15 位小数。而未加速的 s1 用了 10000 项才得到 7 个准确的数字。
  
  现在看看那个 +nan.0
  
  
  1. 
     
  2. (print-stream s3 20)
     
  3. 1.0
     
  4. 0.7
     
  5. 0.69327731092437
     
  6. 0.693148869332925
     
  7. 0.693147196073549
     
  8. 0.693147180663564
     
  9. 0.693147180560404
     
  10. 0.693147180559945
      
  11. 0.693147180559943
      
  12. 0.693147180559945
      
  13. +nan.0
      
  14. +nan.0
      
  15. +nan.0
      
  16. +nan.0
      
  17. +nan.0
      
  18. +nan.0
      
  19. +nan.0
      
  20. +nan.0
      
  21. +nan.0
      
  22. +nan.0
      

  复制代码
  
  
  可以看到，从第 11 项起，得到的都是 +nan.0。Euler 加速公式中有 (s(n+1)-s(n))^2，我猜测这是增量太小引发的下溢。
  
• 最后我们来估计一下 s3 的复杂度。因为这个序列中的一个项，是通过多次欧拉变换得到的。为求出 s3 中的第 n 项，实际需要计算多少个项呢？
  
  从序列 A 欧拉变换到 B，如果有 A 中的前 n 项，可以得到 B 中的 n-2 项。设 s3 形式为：S(0), S(1), ...., S(n), ....
  
  则求 S(0) 需要原始序列 1 项，求 S(1) 需要原始序列 3 项，求 S(2) 需要原始序列 5 项，...，求 S(n) 需要原始序列 2n+1 项。
  
  所以原始序列计算 2n+1 项，然后进行 n 次欧拉变换，每次变换出来的序列比前一序列项数少 2，直到剩下 1 项。总共要计算
  
  (2n+1)+(2n-1)+...+5+3+1 = (n+1)^2 项。
  

[ 本帖最后由 win_hate 于 2009-2-1 12:00 编辑 ]

win_hate

Exercise 3.66.  Examine the stream (pairs integers integers). Can you make any general comments about the order in which the pairs are placed into the stream? For example, about how many pairs precede the pair (1,100)? the pair (99,100)? the pair (100,100)? (If you can make precise mathematical statements here, all the better. But feel free to give more qualitative answers if you find yourself getting bogged down.)

win_hate

• 分析：
  
  考虑 f(i,j)。设从第 i 行起，共有 T 个已处理元素。则
  
  设从第 n 行起往后，已处理元素个数为 S(n)，有
  
  S(n)=0, n>i
  S(n)=S(n+1)*2+1, n<i
  
  容易计算出 S(1) = 2^(i-1)S(i)+2^(i-1)-1.
  
  如果 i=j，则 S(i)=1, S(1)=2^i-1
  
  如果 i<j，则 在第 i 行，有 j-i+1 个元素，在下面的行，有 (j-i+1)-2 = i-j-1 个元素。
  
  所以 i 以及后面的行有 S(i)=2(j-i) 个元素。
  
  S(1)=2^i(j-i)+2^(i-1)+1.
  
• 代码
  
  1. 
     
  2. (define (f i j)
     
  3.   (let* ((T (if (= i j) 1 (* 2 (- j i))))
     
  4.          (d (expt 2 (- i 1))))
     
  5.     (- (* (+ T 1) d) 1)))
     

  复制代码
  
  
• 演示：
  
  
  1. 
     
  2. > (stream-ref x (- (f 1 10) 1))
     
  3. (1 10)
     
  4. > (stream-ref x (- (f 2 10) 1))
     
  5. (2 10)
     
  6. > (stream-ref x (- (f 3 10) 1))
     
  7. (3 10)
     
  8. > (stream-ref x (- (f 4 10) 1))
     
  9. (4 10)
     
  10. > (stream-ref x (- (f 5 10) 1))
      
  11. (5 10)
      
  12. > (stream-ref x (- (f 6 10) 1))
      
  13. (6 10)
      
  14. > (stream-ref x (- (f 7 10) 1))
      
  15. (7 10)
      
  16. > (stream-ref x (- (f 8 10) 1))
      
  17. (8 10)
      
  18. > (stream-ref x (- (f 9 10) 1))
      
  19. (9 10)
      
  20. 
      
  21. > (stream-ref x (- (f 10 10) 1))
      
  22. (10 10)
      
  23. > (stream-ref x (- (f 9 9) 1))
      
  24. (9 9)
      
  25. > (stream-ref x (- (f 8 8) 1))
      
  26. (8 8)
      
  27. > (stream-ref x (- (f 7 7) 1))
      
  28. (7 7)
      
  29. > (stream-ref x (- (f 6 6) 1))
      
  30. (6 6)
      
  31. > (stream-ref x (- (f 5 5) 1))
      
  32. (5 5)
      
  33. > (stream-ref x (- (f 4 4) 1))
      
  34. (4 4)
      
  35. > (stream-ref x (- (f 3 3) 1))
      
  36. (3 3)
      
  37. > (stream-ref x (- (f 2 2) 1))
      
  38. (2 2)
      
  39. > (stream-ref x (- (f 1 1) 1))
      
  40. (1 1)
      

  复制代码
  
  
• 附带一个前 2^n 个数的分布图。
  pairs.figure.pdf (26.69 KB, 下载次数: 28)
  2009-02-01 12:11 上传

  点击文件名下载附件
  
  

[ 本帖最后由 win_hate 于 2009-2-1 12:12 编辑 ]

win_hate

Exercise 3.67.  Modify the pairs procedure so that (pairs integers integers) will produce the stream of all pairs of integers (i,j) (without the condition i < j). Hint: You will need to mix in an additional stream.

win_hate

• 分析：简单的处理为交替从 3 个流中取数。我们的 interleave 只混合两个流，可以把它扩充成混合多个流的版本:
  
  
  1. 
     
  2. (define (interleaves . s)
     
  3.   (cons-stream
     
  4.    (stream-car (car s))
     
  5.    (apply interleaves (append (cdr s) (list (stream-cdr (car s)))))))
     
  6. 
     
  7. (define (all-pairs s1 s2)
     
  8.   (cons-stream
     
  9.    (list (stream-car s1) (stream-car s2))
     
  10.    (interleaves
      
  11.     (stream-map (lambda (x) (list (stream-car s1) x)) (stream-cdr s2))
      
  12.     (stream-map (lambda (x) (list x (stream-car s2))) (stream-cdr s1))
      
  13.     (all-pairs (stream-cdr s1) (stream-cdr s2)))))
      

  复制代码
  
  
• 演示
  
  
  1. 
     
  2. > (define x (all-pairs integers integers))
     
  3. > (take x 10)
     
  4. ((1 1) (1 2) (2 1) (2 2) (1 3) (3 1) (2 3) (1 4) (4 1) (3 2))
     

  复制代码
  
  
• 另外几个思路。
  
  
  • 先把两个流混合起来，再与第三个流混合。
    
    1. 
       
    2. (define (pairs-all s1 s2)
       
    3.   (cons-stream
       
    4.    (list (stream-car s1) (stream-car s2))
       
    5.    (interleaves
       
    6.     (interleaves
       
    7.      (stream-map (lambda (x) (list (stream-car s1) x)) (stream-cdr s2))
       
    8.      (stream-map (lambda (x) (list x (stream-car s2))) (stream-cdr s1)))
       
    9.     (pairs-all (stream-cdr s1) (stream-cdr s2)))))
       

    复制代码
    
    
  • 直接生成两个流混合后的结果，然后与第三个混合。
    
    1. 
       
    2. (define (ya-pairs-all s1 s2)
       
    3.   (define (f x s)
       
    4.     (cons-stream (list x (stream-car s))
       
    5.                  (cons-stream (list (stream-car s) x)
       
    6.                               (f x (stream-cdr s)))))
       
    7.   (cons-stream
       
    8.    (list (stream-car s1) (stream-car s2))
       
    9.    (interleaves
       
    10.     (f (stream-car s1) (stream-cdr s2))
        
    11.     (ya-pairs-all (stream-cdr s1) (stream-cdr s2)))))
        

    复制代码
    
    
  • 前一个做法的推广，既然我们能直接生成两个流的混合（没有直接使用 interleave），能不能直接生成三个流混合的结果呢？ pairs 生成的流是 (i, j), 其中 i<=j； 我们只要遍历这个流，并把其中分量不等的项反转、插入，就能得到所需的结果。
    
    
    1. 
       
    2. (define (all-pairs-1 s1 s2)
       
    3.   (define (f s)
       
    4.     (let ((h (stream-car s)))
       
    5.       (if (= (car h) (cadr h))
       
    6.           (cons-stream h (f (stream-cdr s)))
       
    7.           (cons-stream h
       
    8.                        (cons-stream (reverse h)
       
    9.                                     (f (stream-cdr s)))))))
       
    10.   (f (pairs s1 s2)))
        

    复制代码
    
    
  
  

[ 本帖最后由 win_hate 于 2009-2-2 12:35 编辑 ]

win_hate

Exercise 3.68.  Louis Reasoner thinks that building a stream of pairs from three parts is unnecessarily complicated. Instead of separating the pair (S0,T0) from the rest of the pairs in the first row, he proposes to work with the whole first row, as follows:

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

Does this work? Consider what happens if we evaluate (pairs integers integers) using Louis's definition of pairs.

win_hate

• 分析：
  
  1. 
     
  2. (define (pairs s t)
     
  3.   (interleave
     
  4.    (stream-map (lambda (x) (list (stream-car s) x))
     
  5.                t)
     
  6.    (pairs (stream-cdr s) (stream-cdr t))))
     

  复制代码
  
  
  问题出在对 interleave 的调用和 pairs 的自引用上。
  
  
  • interleave 是函数，所以先求值其参数，
    
  • stream-map 调用 cons-stream，它是个宏，不对参数求值，所以能终止。
    
  • 但 interleave 对第二个参数的求值 (pairs (stream-cdr s) (stream-cdr t)) 不会终止。它会不断调用 pairs，直到耗尽所有空间。
    
  
  
  对比一下原来的 pairs
  
  
  1. 
     
  2. (define (pairs s t)
     
  3.   (cons-stream
     
  4.    (list (stream-car s) (stream-car t))
     
  5.    (interleave
     
  6.     (stream-map (lambda (x) (list (stream-car s) x))
     
  7.                (stream-cdr t))
     
  8.     (pairs (stream-cdr s) (stream-cdr t)))))
     

  复制代码
  
  
  这里也存在 interleave 和 pairs，但此时是包含在一个 cons-stream 里的。cons-stream 是宏，不会对参数穷追猛打。
  
• 其实 Louis Reasoner 的方案比我们最初的方案更为自然。但由于 scheme 的函数调用是严格的，所以他的方案行不通。
  如果我们更进一步，把 scheme 的函数调用也修改为惰性的，那么 Louis Reasoner 的方案就可行了。
  
  用 lazy scheme 来试一下：
  
  
  1. 
     
  2. #lang lazy
     
  3. 
     
  4. (define (interleave s1 s2)
     
  5.   (cons (car s1)
     
  6.         (interleave s2 (cdr s1))))
     
  7. 
     
  8. (define (pairs s t)
     
  9.   (interleave
     
  10.    (map (lambda (x) (list (car s) x))
      
  11.         t)
      
  12. 
      
  13.    (pairs (cdr s) (cdr t))))
      
  14. 
      
  15. (define (integers-starting-from n)
      
  16.   (cons n (integers-starting-from (+ n 1))))
      
  17. 
      
  18. (define integers (integers-starting-from 1))
      

  复制代码
  
  
  这里要使用 mzsheme 解释器。
  
  
  1. 
     
  2. > (define x (pairs integers integers))
     
  3. > (display (take 10 x))
     
  4. ((1 1) (2 2) (1 2) (3 3) (1 3) (2 3) (1 4) (4 4) (1 5) (2 4))
     

  复制代码
  
  

[ 本帖最后由 win_hate 于 2009-2-1 13:07 编辑 ]

win_hate

Exercise 3.69.  Write a procedure triples that takes three infinite streams, S, T, and U, and produces the stream of triples (S_i,T_j,U_k) such that i < j < k. Use triples to generate the stream of all Pythagorean triples of positive integers, i.e., the triples (i,j,k) such that i < j and i^2 + j^2 = k^2.