SICP 习题参考答案 1.2

win_hate

1. 
   
2. 此帖为 SICP 章节 1.2 的参考答案。为保持可读性，请勿直接在本帖讨论。讨论请另开新帖。
   

复制代码

• 本节电子版：[1.2  Procedures and the Processes They Generate]
  
• 答案目录：[点这里]
  

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

win_hate

Exercise 1.9.  Each of the following two procedures defines a method for adding two positive integers in terms of the procedures inc, which increments its argument by 1, and dec, which decrements its argument by 1.

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

Using the substitution model, illustrate the process generated by each procedure in evaluating (+ 4 5). Are these processes iterative or recursive?

win_hate

[解]  第一个是 recursive 的，而第二个是 iterative 的。

win_hate

Exercise 1.10.  The following procedure computes a mathematical function called Ackermann's function.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

What are the values of the following expressions?

(A 1 10)

(A 2 4)

(A 3 3)

Consider the following procedures, where A is the procedure defined above:

(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

(define (k n) (* 5 n n))

Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of n. For example, (k n) computes 5n^2.

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

win_hate

[解]
(A 0 n)=2n
(A 1 n)=2^n
(A 2 n) = 2^2^2...^2    // n 个 2，右结合

win_hate

Exercise 1.11.  A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.

win_hate

递归代码

1. 
   
2. (define (f n)
   
3.   (if (< n 3) n
   
4.       (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))
   

复制代码

迭代代码

1. 
   
2. (define (g x y z n)
   
3.   (if (= 0 n) x
   
4.       (g y z (+ (* 3 x) (* 2 y) z) (- n 1))))
   

复制代码

迭代代码这样使用：

1. 
   
2. (g 0 1 2 n)
   

复制代码

[ 本帖最后由 win_hate 于 2008-9-7 11:22 编辑 ]

win_hate

Exercise 1.12.  The following pattern of numbers is called Pascal's triangle.



The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it. Write a procedure that computes elements of Pascal's triangle by means of a recursive process.

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

win_hate

1. 
   
2. (define (binomial n m)
   
3.   (if (or (= m 0) (= m n))
   
4.       1
   
5.       (+ (binomial (- n 1) m) (binomial (- n 1) (- m 1)))))
   

复制代码

上面的递归虽然很直观，却是一个坏递归的例子。其空间需求以指数方式增长，并做了大量重复的工作。下面这个效率较高，但可读性就差一些。

1. 
   
2. (define (binomial n m)
   
3.   (define (f n m r)
   
4.     (if (= m 0) r (f (- n 1) (- m 1) (/ (* r n) m))))
   
5. 
   
6.   (cond ((< m 0) 0)
   
7.         ((= m 0) 1)
   
8.         ((> m n) 0)
   
9.         ((= n m) 1)
   
10.         ((and (> n 0) (> (* 2 m) n)) (f n (- n m) 1))
    
11.         (else (f n m 1))))
    

复制代码

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

win_hate

Exercise 1.13.  Prove that Fib(n) is the closest integer to ^n/5, where  = (1 + 5)/2. Hint: Let   = (1 - 5)/2. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that Fib(n) = (^n  -^n)/5.

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