sicp习题解答1.2

上一节

;;Exercise 1.9.
The first one is recursive,
and the second one is iterative (tail recursive).


;;Exercise 1.10.
由(A x y)定义得出
(f n) = (2n)

(A 1 10)
(A 0 (A 1 9)) 得出
(g n) = (2^n)

(A 2 10)
(A 1 (A 2 9))
(A 2 1) = 2
得出

(h n) = (pow2 (h (- n 1)))
that is, 2 ^ (2 ^ (... 2)) ;; n times


;;Exercise 1.11.
(define (f-recur n)
(if (< n 3) n
    (+ (f-recur (- n 1))
       (* 2 (f-recur(- n 2)))
       (* 3 (f-recur(- n 3))))))

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



;;Exercise 1.12.
(define (Yang-Hui-San-Jiao nline)
(define (Yang-Hui-cell row col)
  ;;; (assert (not (> col row)))

    (cond ((or (= row 1)
             (= col 1)
             (= row col)) 1)
        (else (+ (Yang-Hui-cell (- row 1) (- col 1))
                 (Yang-Hui-cell (- row 1) col)))))

(define (Yang-Hui-line row)
  (define (iter c)
    (display (cons (Yang-Hui-cell row c) '()))
    (if (< c row)
        (iter (+ c 1))))

  (iter 1)
  (newline))

(define (iter r)
  (Yang-Hui-line r)
  (if (< r nline)
      (iter (+ r 1))))

(iter 1))


;;test
(Yang-Hui-San-Jiao 10)


;;Exercise 1.13.
翻定义and归纳法证明.


;;Exercise 1.14.
O(amount + kinds-of-coins) in space.
O(result * amount) in time.
refer to this


;;Exercise 1.15.
a. 5 times.
b. O(log3(n)) in both time and space.


;;Exercise 1.16.

(define (fast-expt-iter B N)
;;; loop invariant: ab^n = B^N

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

(iter 1 B N))


;;Exercise 1.17
(define (fast-multi a b)
(define (double a) (+ a a))
(define (halve a) (/ a 2))
(cond ((= 0 b) 0)
      ((even? b) (fast-multi (double a) (halve b)))
      (else (+ a (fast-multi a (- b 1))))))

(fast-multi 10 15)
(fast-multi 100 16)



;;Exercise 1.18
(define (fast-multi-iter a b)
(define (iter a b res)
  (cond ((= 0 b) res)
        ((even? b) (iter (double a) (halve b) res))
        (else (iter a (- b 1) (+ res a)))))
(iter a b 0))



;;Exercise 1.19
;(b a) -> (a b+a)

;(b a) * [0, 1] = (a b+a)


;a <-  bq + aq + ap
;b <-  bp + aq


;(a, b) * [q+p, q] = (bq + aq + ap, bp + aq)


;[q+p, q] ^ 2  = [(q+p)^2 + q^2, (q+p)q+qp] = [q'+p', q']
;[q,   p]         [q(q+p) + pq  , q^2 + p^2] = [q'   , p']

(define (fib n)
(fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
(cond ((= count 0) b)
      ((even? count)
       (fib-iter a
                 b
                 (+ (* q q) (* p p))  ; compute p'

                   (+ (* q q) (* 2 p q)); compute q'
                   (/ count 2)))
      (else (fib-iter (+ (* b q) (* a q) (* a p))
                      (+ (* b p) (* a q))
                      p
                      q
                      (- count 1)))))

;;Exercise 1.20
(define (gcd a b)
(if (= b 0)
    a
    (gcd b (remainder a b))))


;; 正则序
http://eli.thegreenplace.net/2007/07/04/sicp-sections-124-125/
(gcd 206 40)
(gcd 40 (remainder 206 40))
->
(if (= (remainder 206 40) 0) ; 1 time
  40
(gcd (remainder 206 40)
  (remainder 40 (remainder 206 40))))
->
(if (= (remainder 40 (remainder 206 40)) 0) ; 2 times

  (remainder 206 40)
(gcd
  (remainder
    40
    (remainder 206 40))
  (remainder
    (remainder 206 40)
    (remainder
      40
      (remainder 206 40)))))
-> ...
18次

(gcd 206 40) ;; remainder 1
(gcd 40 6)   ;; remainder 2
(gcd 6 4)    ;; remainder 3
(gcd 4 2)    ;; remainder 4

(gcd 2 0)
4次


;;Exercise 1.21
(define (smallest-divisor n)
(define (find-divisor n test-divisor)
  (cond ((> (* test-divisor test-divisor) n) n)
        ((= (remainder n test-divisor) 0) test-divisor)
        (else (find-divisor n (+ 1 test-divisor)))))
(find-divisor n 2))

(smallest-divisor 199)   ;199

(smallest-divisor 1999)  ;1999
(smallest-divisor 19999) ;7


;;Exercise 1.22
(define (prime? n)
(= (smallest-divisor n) n))

(define (timed-prime-test n)
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

(newline)
(display n)
(start-prime-test n (runtime)))


(define (search-for-primes begin end)
(cond ((< begin end)
       (timed-prime-test begin)
       (search-for-primes (+ 2 begin) end))))

(search-for-primes 1001 1020)

;; 1009, 1013, 1019
(search-for-primes 10001 10038)
;; 10007, 10009, 10037
(search-for-primes 100001 100044)
;; 100003, 100019, 100043
(search-for-primes 1000001 1000038)
;; 1000003, 1000033, 1000037

;Curiously, timing the runs for 1,000 10,000 100,000 and 1,000,000
;doesn’t work because my computer is too fast
;(SICP was written in the 80s!) – all the runs
;just take 0 seconds, which means that the runtime is
;below the resolution of the timer used in the timing.


;;Exercise 1.23
(define (smallest-divisor n)
(define (next n)
  (if (= n 2)
      3
      (+ n 2)))
(define (find-divisor n test-divisor)
  (cond ((> (* test-divisor test-divisor) n) n)
        ((= (remainder n test-divisor) 0) test-divisor)
        (else (find-divisor n (next test-divisor)))))
(find-divisor n 2))



;;Exercise 1.24
(define (expmod base exp m)
(cond ((= exp 0) 1)
      ((even? exp)
       (remainder (square (expmod base (/ exp 2) m))
                  m))
      (else
       (remainder (* base (expmod base (- exp 1) m))
                  m))))

(define (fermat-test n)
(define (try-it a)
  (= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
(cond ((= times 0) true)
      ((fermat-test n) (fast-prime? n (- times 1)))
      (else false)))

(define (timed-prime-test n)
(define (start-prime-test n start-time)
  (if (fast-prime? n)
      (report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

(newline)
(display n)
(start-prime-test n (runtime)))



;;Exercise 1.25
It's correct if arbitary precision arithmetic is supported.
But it will be much slower than the implementation provided
by the authors.


;;Exercise 1.26.
粗略地：
2 ^ log2(m) = m


;;Exercise 1.27.
(define (Carmichael-test n)
(define (try-it a)
  (= (expmod a n n) a))
(define (iter i)
  (cond ((= i 1) #t)  ;; no need to test (1^n = 1 % n)
          ((not (try-it i)) #f)
        (else (iter (- i 1)))))
(and (not (prime? n))
     (iter (- n 1))))

(Carmichael-test 561)
(Carmichael-test 1105)
(Carmichael-test 1729)
(Carmichael-test 2465)
(Carmichael-test 2821)
(Carmichael-test 6601)


;;Exercise 1.28.
 ; ref: CLRS 31.6,31.8
(define (square x)
(* x x))

(define (Miller-Rabin n)
(define (check x)
  (define result
    (remainder (square x) n))
  (if (and
       (= result 1)
       (not (or (= x 1) (= x (- n 1)))))
      0
      result))

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (check (expmod base (/ exp 2) m)))
         (else (remainder (* base (expmod base (- exp 1) m))
                          m))))

(define (try-it a)
  (cond ((= a 0) #t)
        ((= 1 (expmod a (- n 1) n))
         (try-it (- a 1)))
        (else #f)))
(try-it (- n 1)))


(Miller-Rabin 233)
(Miller-Rabin 9999)
(Miller-Rabin 561)
(Miller-Rabin 1105)
(Miller-Rabin 1729)
(Miller-Rabin 2465)
(Miller-Rabin 2821)
(Miller-Rabin 6601)