sicp-3-5-3

Posted on 2015-03-03 22:24:29 +0900 in SICP Lisp

3.63

guess is used to share the computation result between the succssive calling. Otherwise each call to sqrt-stream x would require recursively calling.

If memo-proc is not used, these two versions would be the same efficiency.

3.64

(define (stream-limit s tolerance)
  (let ((s2 (stream-cdr s)))
    (if (< (abs
             (-
               (stream-car s)
               (stream-car s2)))
           tolerance)
      (stream-car s2)
      (stream-limit s2 tolerance))))

3.65

(define (euler-transform s)
  (let ((s0 (stream-ref s 0))           ; Sn-1
        (s1 (stream-ref s 1))           ; Sn
        (s2 (stream-ref s 2)))          ; Sn+1
    (cons-stream (- s2 (/ (square (- s2 s1))
                          (+ s0 (* -2 s1) s2)))
                 (euler-transform (stream-cdr s)))))

(define (make-tableau transform s)
  (cons-stream s
               (make-tableau transform
                             (transform s))))
(define (accelerated-sequence transform s)
  (stream-map stream-car
              (make-tableau transform s)))
(define (log2-summands n)
  (cons-stream (/ 1.0 n)
               (stream-map - (log2-summands (+ n 1)))))
(define log2-stream
  (partial-sums (log2-summands 1)))

(stream-limit
  (accelerated-sequence euler-transform log2-stream) 0.0001)

3.66

2	4	6	8
3	5	9	13
	7	11	19
		15	23

The order to traverse the pair is listed as above. Some observations:

$(i,i)=2^i-1$

$(i, i + 1) = 3*2^{i-1}-1$

$(i, k) = 3*2^{i-1}-1 + (k- i - 1) * 2^i$

3.67

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

3.68

Only the cons-stream is a normal-order function, while interleave is not. When interleave evaluate its two parameters, which includes pair, would lead to infinite loop.

3.69

(define (triples s1 s2 s3)
  (cons-stream
    (list (stream-car s1)
          (stream-car s2)
          (stream-car s3))
    (interleave
      (stream-map
        (lambda (x) (append (list (stream-car s1))
                            x))
        (stream-cdr
          (pair s2 s3)))
      (triples (stream-cdr s1)
               (stream-cdr s2)
               (stream-cdr s3)))))

3.70

(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)))
            (if (<= (weight s1car)
                    (weight s2car))
              (cons-stream s1car
                           (merge-weighted (stream-cdr s1)
                                           s2
                                           weight))
              (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)
                  (apply + x)))

(define no-factors
  (stream-filter
    (lambda (x)
      (not
        (or (divides? x 2)
            (divides? x 3)
            (divides? x 5))))
    integers))

(weighted-pairs no-factors
                no-factors
                (lambda (lst)
                  (let ((i (car lst))
                        (j (cadr lst)))
                    (+
                      (* 2 i)
                      (* 3 j)
                      (* 5 i j)))))

3.71

(define (sum-cube pair)
  (let ((i (car pair))
        (j (cadr pair)))
    (+ (* i i i)
       (* j j j))))

(define all-pairs
  (weighted-pairs integers integers sum-cube))

(define (ram-numbers stream)
  (let* ((w1 (sum-cube
               (stream-car stream)))
         (rest (stream-cdr stream))
         (w2 (sum-cube
               (stream-car rest))))
    (if (= w1 w2)
      (cons-stream w1
                   (ram-numbers (stream-cdr
                                  rest)))
      (ram-numbers rest))))

(show-stream (ram-numbers all-pairs) 6)

3.73

(define (RC r c dt)
  (lambda (i v)
    (add-streams
      (scale-stream i r)
      (integral (scale-stream i
                              (/ 1 c))
                v
                dt))))

3.74

(define zero-crossings
  (stream-map sign-change-detector sense-data
              (cons-stream 0 sense-data)))

3.75

The last value of the origin stream should be passed in, otherwise avpt would acutally become a recursive version.

3.76

(define (smooth s)
  (stream-map (lambda (x y) (/ (+ x y) 2))
              (cons-stream 0 s)
              s))

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------

« sicp-3-5-4-3-5-5 | sicp-3-5-1-3-5-2 »