SICP 习题参考答案 1.2

win_hate

Fib(n)=(phi^n-psi^n)/sqrt(5)

容易证明：

1、|psi|<1, 所以 |(psi)^n|<1
2、1/sqrt(5)<1/2

所以 |psi^n/sqrt(5)|<1/2，即 Fib(n) 是最接近 phi^n/sqrt(5) 的整数。

win_hate

Exercise 1.14.  Draw the tree illustrating the process generated by the count-change procedure of section 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?

win_hate

等我素描班毕业后再画。

win_hate

Exercise 1.15.  The sine of an angle (specified in radians) can be computed by making use of the approximation sin x x if x is sufficiently small, and the trigonometric identity



to reduce the size of the argument of sin. (For purposes of this exercise an angle is considered ``sufficiently small'' if its magnitude is not greater than 0.1 radians.) These ideas are incorporated in the following procedures:

(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))

a.  How many times is the procedure p applied when (sine 12.15) is evaluated?

b.  What is the order of growth in space and number of steps (as a function of a) used by the process generated by the sine procedure when (sine a) is evaluated?

[ 本帖最后由 win_hate 于 2008-9-8 19:31 编辑 ]

win_hate

a) 5 次

计算次数的代码为

1. 
   
2. (ceiling (/ (log 121.5) (log 3)))
   

复制代码

b) 如果直接用书中代码进行计算，则时间增长和空间增长都是， O(log_3 10a)

不过，因为 sin 是周期函数，所以在调用 sine 之前先约化到 [-pi, pi]  间是合适的。如采用这种方式，则时间和空间都是  O(1) 的。

[ 本帖最后由 win_hate 于 2008-9-8 19:41 编辑 ]

win_hate

Exercise 1.16.  Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. (Hint: Using the observation that (b^(n/2))^2 = (b^2)^(n/2), keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product a bn is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

[ 本帖最后由 win_hate 于 2008-9-9 13:15 编辑 ]

win_hate

1. 
   
2. (define (pow b n)
   
3.   (define (f b n c)
   
4.     (cond ((= n 0) c)
   
5.           ((even? n) (f (* b b) (/ n 2) c))
   
6.           (else (f b (- n 1) (* b c)))))
   
7. 
   
8.     (f b n 1))
   

复制代码

win_hate

Exercise 1.17.  The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure:

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.

win_hate

1. 
   
2. (define (mul a b)
   
3.   (define (f a b c)
   
4.     (cond ((= b 0) c)
   
5.           ((even? b) (f (+ a a) (/ b 2) c))
   
6.           (else (f a (- b 1) (+ c a)))))
   
7. 
   
8.   (f a b 0))
   

复制代码

win_hate

Exercise 1.18.  Using the results of exercises 1.16 and 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.40