首页 > 代码库 > SICP 1.16 1.17 1.18

SICP 1.16 1.17 1.18

解:

公共过程

(define (even? n)
  (= (remainder n 2) 0))

(define (double n)
  (+ n n))

(define (halve n)
  (/ n 2))


1.16:

(define (expt b n)
  (define (iter b n a)
    (cond ((= n 0) a)
          ((even? n) (iter (* b b) (/ n 2) a))
          (else (iter b (- n 1) (* b a)))))
  (iter b n 1))

1.17 1.18

    = 2*(a*(b/2))=a*(b/2)+a*(b/2)=2a*(b/2),b是偶数

a*b = a+a*(b-1),b是奇数

    = a,b=1

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

(define (multiply2 a b)
  (define (fast-mul a b c)
    (cond ((= b 1) (+ a c))
          ((even? b) (fast-mul (double a) (halve b) c))
          (else (fast-mul a (- b 1) (+ a c)))))
  (fast-mul a b 0))