SICP读书笔记2.1

练习2.1

通过分子和分母相乘的结果的符号决定分子的符号，分母取绝对值。

改进后程序如下:

(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons ((if (> (* n d) 0) + -)
           (abs (/ n g))) (abs (/ d g)))))

练习2.2

(define (make-point x y) (cons x y))
(define (x-point p) (car p))
(define (y-point p) (cdr p))

(define (make-segment p1 p2) (cons p1 p2))
(define (start-segment p) (car p))
(define (end-segment p) (cdr p))

(define (midpoint-segment s)
  (make-point (average (x-point (start-segment s))
                       (x-point (end-segment s)))
              (average (y-point (start-segment s))
                       (y-point (end-segment s)))))

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

练习2.3

方法1

用厂和宽表示一个矩形，代码如下：

(define (make-rectangle length width)
  (cons length width))

(define (length-rectangle r) (car r))
(define (width-rectangle r) (cdr r))

(define (perimeter-rectangle r)
  (* (+ (length-rectangle r) (width-rectangle r) 2)))

(define (area-rectangle r)
  (* (length-rectangle r) (width-rectangle r)))

方法2

另一种方法可以是用坐标系上四个点表示一个矩形，也可以是四条边表示一个矩形。

但是不管内部表示如何，只要正确实现了length-rectangle 和 width-rectangle 则area-rectangle 和perimeter-rectangle 就可以正常使用。

练习2.4

cdr 代码如下 :

(define (cdr z)
  (z (lambda (p q) q)))

假设构造时使用 x 和 y，cons的结果为

(cons x y)
(lambda (m) (m x y))

对此使用car 展开为：

(car (lambda (m) (m x y)))
((lambda (m) (m x y)) (lambda (p q) p))
((lambda (p q) p) x y)
x

练习2.5

首先定义cons:

(define (cons1 x y)
  (* (expt 2 x) (expt 3 y)))

定义一个过程用于计算一个数的因子中的特定数字的个数

(define (factor-count c n)
  (if (not (= (remainder c n) 0))
      0
      (+ 1 (d (/ c n) n))))

然后定义car和cdr

(define (car1 c)
  (factor-count c 2))

(define (cdr1 c)
  (factor-count c 3))

练习2.6

计算one

展开调用为

(add-1 zero)
(lambda (f) (lambda (x) (f ((zero f) x))))
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) x) x))))
(lambda (f) (lambda (x) (f x)))

计算two

展开调用为

(add-1 one)
(lambda (f) (lambda (x) (f ((one f) x))))
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) (f x))) f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) (f x)) x))))
(lambda (f) (lambda (x) (f (f x))))

也就是每个数字代表的是内部lambda当中f的调用次数。

加法

(define (+ a b)
  (lambda (f)
    (lambda (x)
      ((a f)
       ((b f) x)))))

尝试使用one 和two展开函数，里层lambda内部为

((one f) ((two f) x))
((one f) (((lambda (f) (lambda (x) (f (f x)))) f) x))
((one f) (f (f x)))
(((lambda (f) (lambda (x) (f x))) f) (f (f x)))
(((lambda (x) (f x))) (f (f x)))
(f (f (f x)))

套上外层调用得到:

(lambda (f) (lambda (x) (f (f (f x)))))

与预期结果一致

练习2.7

(define (upper-bound i) (cdr i))
(define (lower-bound i) (car i))

练习2.8

区间减法结果的下界为两个区间的下界之差，上界为两个区间的上界之差

(define (sub-interval x y)
  (make-interval (- (lower-bound x) (lower-bound y))
                 (- (upper-bound x) (upper-bound y))))

练习2.9

设输入的两个区间分别为 $x(x_1, x_2), y (y_1, y_2)$

$x$ 的宽度 $w_x$ 为: $(x_1 + x_2) /2$

$y$ 的宽度 $w_y$ 为: $(y_1 + y_2) /2$

$x + y$ 的宽度为：

$[(x_1 + y_1) + (x_2 +y_2)] / 2$

简化得：

$w_x + w_y$

得证

同理可证减法情况

练习2.10

(define (div-interval x y)
  (if (>= 0 (* (lower-bound y) (upper-bound y)))
      (error "Div error")
      (mul-interval x
                    (make-interval (/ 1. (upper-bound y))
                                   (/ 1. (lower-bound y))))))

练习2.11

条件有9种可能性，分别是: x的两个数大于0；x的两个数小于0；x的两个数一个大于0一个小于0； y的两个数大于0；y的两个数小于0；y的两个数一个大于0一个小于0；

x的3种可能和y的3种可能交叉后一共9种。

再按照每种可能，选出最大值和最小值。

(define (interval-sign x)
  (cond ((and (>= (upper-bound i) 0)
              (>= (lower-bound i) 0))
         1)
        ((and (< (upper-bound i) 0)
              (< (lower-bound i) 0))
         -1)
        (else 0)))

(define (mul-interval x y)
  (cond ((> (interval-sign x) 0)
         (cond ((> (interval-sign y) 0)
                (make-interval (* (lower-bound x)
                                  (lower-bound y))
                               (* (upper-bound x)
                                  (upper-bound y))))
               ((< (interval-sign y) 0)
                (make-interval (* (upper-bound x)
                                  (lower-bound y))
                               (* (lower-bound x)
                                  (upper-bound y))))
               (else
                (make-interval (* (upper-bound x)
                                  (lower-bound y))
                               (* (upper-bound x)
                                  (upper-bound y))))))
        ((< (interval-sign x) 0)
         (cond ((> (interval-sign y) 0)
                (make-interval (* (lower-bound x)
                                  (upper-bound y))
                               (* (upper-bound x)
                                  (lower-bound y))))
               ((< (interval-sign y) 0)
                (make-interval (* (upper-bound x)
                                  (upper-bound y))
                               (* (lower-bound x)
                                  (lower-bound y))))
               (else
                (make-interval (* (lower-bound x)
                                  (upper-bound y))
                               (* (lower-bound x)
                                  (lower-bound y))))))
        (else
         (cond ((> (interval-sign y) 0)
                (make-interval (* (lower-bound x)
                                  (upper-bound y))
                               (* (upper-bound x)
                                  (upper-bound y))))
               ((< (interval-sign y) 0)
                (make-interval (* (upper-bound x)
                                  (lower-bound y))
                               (* (lower-bound x)
                                  (lower-bound y))))
               (else
                (make-interval (min (* (lower-bound x)
                                       (lower-bound y))
                                    (* (upper-bound x)
                                       (upper-bound y)))
                               (max (* (upper-bound x)
                                       (lower-bound y))
                                    (* (lower-bound x)
                                       (upper-bound y)))))))))

练习 2.12

(define (make-center-percent center percent)
  (make-interval (* center (- 1 percent))
                 (* center (+ 1 percent))))

(define (center i)
  (/ (+ (lower-bound i) (upper-bound i)) 2))

(define (percent i)
  (- 1 (/ (lower-bound i) (center i))))

练习2.13

设两个区间 $A, B$ ，两个区间的中心分别为 $C_A, C_B$ ，两个区间的误差分别为 $P_A,P_B$

$A=(C_A \times (1 - P_A) , C_A \times (1 + P_A))$ $B=(C_B \times (1 - P_B) , C_B \times (1 + P_B))$

在A, B 区间都是正数的情况下：

$A \times B = [C_A C_B \times (1 - (P_A + P_B) + P_A P_B) \quad , \quad C_A C_B \times (1 + (P_A + P_B) + P_A P_B)]$

由题意可知 $P_A P_B$ 是很小的数所以可以忽略，得乘积的误差为 $P_A+P_B$