sicp 习题 1.10 ~ 1.17

1.10

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

(define (f n) (A 0 n))
(define (fm n) (* 2 n))
(define (g n) (A 1 n))
(define (gm n)
  (if (= n 1)
      2
      (* 2 (gm (- n 1)))))
(define (h n) (A 2 n))
(define (hm n)
  (if (= n 1)
      (g 1)
      (g (hm (- n 1)))))
(define (k n) (A 3 n))
(h 4)

1.11

(define (f n)
  (cond((< n 3) n)
       ((= n 3) 4)
       ((> n 3)(+ (f (- n 1))
                  (* 2 (f (- n 2)))
                  (* 3 (f (- n 3)))))))
(f 4)

1.12

(define (pascal x y)
  (cond((= x 1) 1)
       ((= y 1) 1)
       ((= x y) 1)
       ((> y x) 1)
       (else (+ (pascal (- x 1)(- y 1)) (pascal (- x 1) y)))))
(pascal 5 6)

1.16
b^n*(a*b^0) = b^(n/2)*(a*b^2) 是不变的状态

(define (f b n a)
  (cond ((= n 0) a)
        ((= n 1) (* a b))
        ((= n 2) (* a b b))
        ((even? n) (f b (/ n 2) (* a b b)))
        (else (* b (f b (- n 1) a)))))
(f 4 5 1)

1.17

(define (double a)
  (* a 2))
(define (halve a)
  (/ a 2))

(define (multiply a b)
  (cond ((= b 0) 0)
        ((even? b) (multiply (double a) (halve b)))
        (else (+ a (multiply a (- b 1))))))
(multiply 5 5)