SICP练习——chap1（未完待续）

习题答案已经搬到github中

 

 

 

 

看这书相当费时间，习题慢慢做，边做边发吧。

 

 

 

练习1.1

10    12    8    3    6    19    false    4    20

 

练习1.2  将下面的表达式转换为前缀形式

(/  (+  5  4  (-  2  (-  3  (+  6  (/  4  5)))))  (*  3  (-  6  2)  (-  2  7)))

 

练习1.3  定义一个过程，它以3个数为参数，返回其中较大的两个数之和

 

(define (largerSum a b c)
  (cond ((and (> a c) (> b c)) (+ a b))
        ((and (> a b) (> c b)) (+ a c))
        (else (+ b c))
        )
  )

 

练习1.4  描述下面的过程的行为

 

(define  (a-plus-abs-b  a  b)
    ((if  (>  b  0)  +  -)  a  b)
)

若b大于0，返回（a+b），否则返回（a-b）

 

练习1.5  下面的过程在正则序和应用序下有何不同

 

(define  (p)  (p))
(define  (test  x  y)
    (if  (=  x  0)
        0
        y
    )
)
(test  0  (p))

在正则序下，上面的过程会返回0，则应用序下会陷入无限循环

 

练习1.6  

这个自定义的过程在正则序和应用序下有不同的行为，在应用序下会陷入无限循环

 

练习1.7  给计算平方根的过程加上一个精度控制

 

(define (countSqrt x precision)
  (sqrt-loop x (nextGuess x 1.0) 1.0 precision)
  )

(define (sqrt-loop original guess lastGuess precision)
  (if (goodEnough guess lastGuess precision)
      guess
      (sqrt-loop original (nextGuess original guess) guess precision)
      )
  )

(define (goodEnough guess lastGuess precision)
  (< (/ (abs (- guess lastGuess)) lastGuess) precision)
  )
 
(define (nextGuess original y)
  (/ (+  original  y)  2)
  )

 

 

练习1.8  求立方根的牛顿法基于如下事实，如果y是x的立方根的一个近似值，那么下式将给出一个更好的近似值：

 

 

(define (countCubeRoot x precision)
  (countCubeRootLoop x (nextGuess x 1.0) 1.0 precision)
  )

(define (countCubeRootLoop original guess lastGuess precision)
  (if (goodEnough guess lastGuess precision)
      guess
      (countCubeRootLoop original (nextGuess original guess) guess precision)
      )
  )

(define (sqr y)
  (* y y)
  )

(define (goodEnough guess lastGuess precision)
  (< (/ (abs (- guess lastGuess)) lastGuess) precision)
  )
 
(define (nextGuess original y)
  (/ (+ (/ original (sqr y)) (* 2 y)) 3)
  )

 

 

练习1.9  下面几个过程各定义了一种加起两个正整数的方法，它们都是基于过程inc（将参数加1）和dec（将参数减1）.

 

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

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

 

 用代换模型展示这两个过程在求职（+ 4 5）时所产生的计算过程。

 

 

(define (+ a b)
    (if  (= a 0)
        b
        (inc (+ (dec a) b))
    )
)
(+ 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
递归计算过程


(define (+ a b)
    (if (= a 0)
        b
        (+ (dec a) (inc b))
    )
)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9
迭代计算过程

 

 

练习1.10  下面过程计算一个称为Ackermann函数的数学函数：

 

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

 

下面的表达式的值是什么？

 

(A  1  10)
(A  2  4)
(A  3  3)

 

 请考虑下面的过程，其中的A就是上面定义的过程：

 

(define  (f  n)  (A  0  n))
(define  (g  n)  (A  1  n))
(define  (h  n)  (A  2  n))
(define  (k  n)  (*  5  n  n))

 请给出过程f、g和h对给定整数值n所计算的函数的数学定义。例如，(k  n)的计算是5(n^2)

(A 1 10) = 1024

(A 2 4) = 65536

(A 3 3) = 65536

 

 

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

 

 

(define  (g  n)  (A  1  n))
    (A (- 1 1) (A  1  (- n 1)))
    (A  0  (A  1 n-1))
    (A  0  (A  0  (A  1  n-2)))
    (A  0  (A  0  (A  0  ...  (A  1  1))))
    (A  0  (A  0  (A  0  ..  2)))    
    2^n

 

 

(define  (h  n)  (A  2  n))
    (A  (-  2  1)  (A  2  n-1))
    (A  1  (A  2  n-1))
    (A  (-  1  1)  (A  2  (A  2  n-1)))
    (A  0  (A  2  (A  2  n-1)))
    (*  2  (A  2  (A  2  n-1)))
    2^(2^(2^ (...2)))    (2的个数等于n)

 

练习1.11  函数f由如下的规则定义：如果n<3，那么f(n)=n；如果n>=3，那么f(n)=f(n-1)+2f(n-2)+3f(n-3)。请写一个采用递归计算过程计算f的过程，再写一个采用迭代计算过程计算f的过程。

递归计算过程

 

(define (f111 n)
    (if (< n 3)
        n
        (+ 
            (f111 (- n 1)) 
            (* 2 (f111 (- n 2)))
            (* 3 (f111 (- n 3)))
        )
    )
 ) 

迭代计算过程

 

(define (g  n)
  (define (g-iter a b c count)
    (if (> count n)
        a
        (g-iter (+ a
                   (* 2 b)
                   (* 3 c))
                a
                b
                (+ count 1))))
  (if (< n 3)
      n
      (g-iter 2 1 0 3)))

 

练习 1.12  帕斯卡三角形边界上的数都是1，内部的每个数是位于它上面的两个数之和。请写一个过程，采用递归计算过程计算出帕斯卡三角形

 

(define (pascal-triangle  row  col)
    (if  (or  
             (=  col  1) 
             (= col row)
         )
         1
         (+ 
             (pascal-triangle  (- row 1)  (- col 1) )
             (pascal-triangle  (- row 1)  col)
         )
    )
)

 

练习1.13  证明Fib(n)是最接近于ⁿ/5的整数，其中 = (1 + 5)/2。提示，令  = (1 - 5)/2，使用归纳法和斐波纳契数列的定义证明Fib(n) = (ⁿ - ⁿ)/5。

 

    如提示所说，先证明Fib(n) = (ⁿ - ⁿ)/5。

    具体的证明方法略（并不难）。

    然后，为了了证明Fib(n)是最接近于ⁿ/5的整数，则需要证明(ⁿ/5 = ⁿ5 -  Fib(n)) < 0.5，此时原命题成立。

    事实上，虽然当n=1时，ⁿ/5的值约等于0.618033988（好神奇，黄金分割比例），但此时，ⁿ5约等于1.11803398，与之最近的整数是1，等于Fib(1)，命题成立。

    当n>=2时，ⁿ/5<0.5，原命题仍然成立。