SICP 习题参考答案，3.5

win_hate

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

复制代码

win_hate

Exercise 3.55.  Define a procedure partial-sums that takes as argument a stream S and returns the stream whose elements are S0, S0 + S1, S0 + S1 + S2, .... For example, (partial-sums integers) should be the stream 1, 3, 6, 10, 15, ....

win_hate

1. 
   
2. (define (partial-sums s)
   
3.   (letrec ((r (cons-stream
   
4.             (stream-car s) (add-streams (stream-cdr s) r))))
   
5.     r))
   

复制代码

3.54 的阶乘是本题的一个特例。只要把本题中的 s 换成整数流，add-streams 换成 mul-stream，就能计算出阶乘。

[ 本帖最后由 win_hate 于 2008-9-3 12:09 编辑 ]

win_hate

Exercise 3.56.  A famous problem, first raised by R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, let us call the required stream of numbers S and notice the following facts about it.

    * S begins with 1.

    * The elements of (scale-stream S 2) are also elements of S.

    * The same is true for (scale-stream S 3) and (scale-stream 5 S).

    * These are all the elements of S.

Now all we have to do is combine elements from these sources. For this we define a procedure merge that combines two ordered streams into one ordered result stream, eliminating repetitions:

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

Then the required stream may be constructed with merge, as follows:

(define S (cons-stream 1 (merge <??> <??>)))

Fill in the missing expressions in the places marked <??> above.

[ 本帖最后由 win_hate 于 2008-9-3 12:18 编辑 ]

win_hate

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

复制代码

[ 本帖最后由 win_hate 于 2008-9-3 12:18 编辑 ]

win_hate

Exercise 3.57.  How many additions are performed when we compute the nth Fibonacci number using the definition of fibs based on the add-streams procedure? Show that the number of additions would be exponentially greater if we had implemented (delay <exp>) simply as (lambda () <exp>), without using the optimization provided by the memo-proc procedure described in section 3.5.1.64

win_hate

这个题目算了吧。

win_hate

Exercise 3.58.  Give an interpretation of the stream computed by the following procedure:

(define (expand num den radix)
  (cons-stream
   (quotient (* num radix) den)
   (expand (remainder (* num radix) den) den radix)))

(Quotient is a primitive that returns the integer quotient of two integers.) What are the successive elements produced by (expand 1 7 10) ? What is produced by (expand 3 8 10) ?

win_hate

num 是分子，den 是分母，应有条件 num<den.

显然是计算 num/den 的  radix 进制展开。

win_hate

Exercise 3.59.  In section 2.5.3 we saw how to implement a polynomial arithmetic system representing polynomials as lists of terms. In a similar way, we can work with power series, such as





represented as infinite streams. We will represent the series a0 + a1 x + a2 x^2 + a3 x^3 + ··· as the stream whose elements are the coefficients a0, a1, a2, a3, ....

a. The integral of the series a0 + a1 x + a2 x^2 + a3 x^3 + ··· is the series



where c is any constant. Define a procedure integrate-series that takes as input a stream a0, a1, a2, ... representing a power series and returns the stream a0, (1/2)a1, (1/3)a2, ... of coefficients of the non-constant terms of the integral of the series. (Since the result has no constant term, it doesn't represent a power series; when we use integrate-series, we will cons on the appropriate constant.)

b. The function x->e^x is its own derivative. This implies that ex and the integral of ex are the same series, except for the constant term, which is e^0 = 1. Accordingly, we can generate the series for e^x as

(define exp-series
  (cons-stream 1 (integrate-series exp-series)))

Show how to generate the series for sine and cosine, starting from the facts that the derivative of sine is cosine and the derivative of cosine is the negative of sine:

(define cosine-series
  (cons-stream 1 <??>))
(define sine-series
  (cons-stream 0 <??>))

[ 本帖最后由 win_hate 于 2009-1-23 09:30 编辑 ]