SICP-1.2.1节练习

lispor posted @ Feb 15, 2011 03:34:46 PM in Scheme with tags SICP , 1477 阅读

```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?```

```一、用第一个过程的计算过程：
(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

```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.```

```scheme@(guile-user)> (define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
scheme@(guile-user)> (A 1 10)
1024
scheme@(guile-user)> (A 2 4)
65536
scheme@(guile-user)> (A 3 3)
65536

f(n) = 2n

g(n) = 2^n

|0,  n=0
h(n) = |2,  n=1
|2^{h(n-1)}, otherwise```

(输入验证码)
or Ctrl+Enter