SICP-1.1.7节练习
SICP-1.2.2节练习

SICP-1.2.1节练习

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

练习 1.9 - 1.10

 
练习 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?
我的解答:
一、用第一个过程的计算过程:
(+ 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

从上面可以看出:第一个过程为递归计算过程,第二个过程为迭代计算过程。
 
练习 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.
我的解答:
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
 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter