SICP - chapter 1 习题

(define (max_tow_sum a b c)
        (cond ((and (>= a b) (>= b c)) (+ a b))
              ((and (>= a c) (>= c b)) (+ a c))
              ((and (>= b a) (>= a c)) (+ b a))
              ((and (>= b c) (>= c a)) (+ b c))
              ((and (>= c a) (>= a b)) (+ c a))
              ((and (>= c b) (>= b a)) (+ c b))))

(define (max_tow_sum2 a b c)
        (- (+ a b c) (min a b c)))

(displayln (max_tow_sum2 1 2 3))

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

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

(define (decrease a)
  (new-if (> a 0)
      (decrease (- a 1))
      a))

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

;很大的数，good_enough会爆掉；很小的数，即使0.001作为衡量标准也很大了。

(define (improve guess n)
  (/ (+ guess (/ n guess)) 2))

(define (good-enough? x y)
  (< (abs (- x y)) 0.000001))

(define (sqrt-iter1 last-guess cur-guess n)
  (if (good-enough? last-guess cur-guess)
      cur-guess
      (sqrt-iter1 cur-guess (improve cur-guess n) n)))
(define (my-sqrt1 n)
  (sqrt-iter1 (/ n 2) (+ (/ n 2) 1.0) n))

(define (sqrt-iter2 guess n)
  (let ((next-guess (improve guess n)))
  (if (good-enough? guess next-guess)
      next-guess
      (sqrt-iter2 next-guess n))))
(define (my-sqrt2 n)
  (sqrt-iter2 1.0 n))

(displayln (my-sqrt2 4))

; 需要先执行1.7
(define (improve3 guess n)
  (/ (+ (/ n (* guess guess)) (* 2 guess)) 3))
(define (sqrt3-iter guess n)
  (let ((next-guess (improve3 guess n)))
  (if (good-enough? guess next-guess)
      next-guess
      (sqrt3-iter next-guess n))))
(define (my-sqrt3 n)
  (sqrt3-iter 1.0 n))

(displayln (my-sqrt3 27.0))

;1.12
(define (pascal row col)
  (cond ((= row 1) 1)
        ((= col row) 1)
        (else (+ (pascal (- row 1) col) (pascal (- row 1) (+ col 1))))))

(displayln (pascal 5 3))

; 1.21

(define (square n)
  (* n n))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

(displayln (smallest-divisor 199))
(displayln (smallest-divisor 1999))
(displayln (smallest-divisor 19999))

; 先运行1.21，，会比较卡
; 1.22
(define (timed-prime-test n)
  (display "start-with: ")
  (displayln n)
  (start-prime-test n (current-milliseconds) 0))

(define (start-prime-test n start-time found-num)
  (if (= found-num 3)
      (report-prime (- (current-milliseconds) start-time))
      (if (prime? n)
          (begin
            (display "found: ")
            (displayln n)
            (start-prime-test (+ 2 n) start-time (+ found-num 1)))
          (start-prime-test (+ 2 n) start-time found-num))))

(define (report-prime elapsed-time)
  (display "time elapsed: ")
  (displayln elapsed-time)
  (displayln "-----------"))

(displayln (timed-prime-test 10000000001))
(displayln (timed-prime-test 100000000001))
;(displayln (timed-prime-test 1000000000001))
;(displayln (timed-prime-test 10000000000001))
;(displayln (timed-prime-test 100000000000001))
;(displayln (timed-prime-test 1000000000000001))

; 需要先运行1.22
; 1.23
(define (smallest-divisor2 n)
  (find-divisor2 n 2))

(define (find-divisor2 n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor2 n (next test-divisor)))))

(define (next n)
  (if (= n 2)
      3
      (+ n 2)))

(define (prime?2 n)
  (= n (smallest-divisor2 n)))

(define (start-prime-test2 n start-time found-num)
  (if (= found-num 3)
      (report-prime (- (current-milliseconds) start-time))
      (if (prime?2 n)
          (begin
            (display "found: ")
            (displayln n)
            (start-prime-test2 (+ 2 n) start-time (+ found-num 1)))
          (start-prime-test2 (+ 2 n) start-time found-num))))

(define (timed-prime-test2 n)
  (display "start-with: ")
  (displayln n)
  (start-prime-test2 n (current-milliseconds) 0))

; 差距确实是两倍
(displayln (timed-prime-test 100000000001))
(displayln (timed-prime-test2 100000000001))
; (displayln (timed-prime-test 1000000000001))
; (displayln (timed-prime-test2 1000000000001))
; (timed-prime-test 10000000000001)
; (timed-prime-test2 10000000000001)
; (timed-prime-test 100000000000001)
; (timed-prime-test2 100000000000001)
; (timed-prime-test 1000000000000001)
; (timed-prime-test2 1000000000000001)

; 需要先运行1.23
; 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))))) ; should be (random (- n 1))

(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

(define (start-prime-test3 n start-time found-num)
  (if (= found-num 3)
      (report-prime (- (current-milliseconds) start-time))
      (if (fast-prime? n 100)
          (begin
            (display "found: ")
            (displayln n)
            (start-prime-test3 (+ 2 n) start-time (+ found-num 1)))
          (start-prime-test3 (+ 2 n) start-time found-num))))

(define (timed-prime-test3 n)
  (display "start-with: ")
  (displayln n)
  (start-prime-test3 n (current-milliseconds) 0))

(displayln (timed-prime-test 100000000001))
(displayln (timed-prime-test2 100000000001))
;不知道为什么浏览器跑test3会死循环
;(displayln (timed-prime-test3 100000000001))

; 需要先运行1.24
; 1.27
(prime? 561)
(fermat-test 561)
(fermat-test 1105)
(fermat-test 1729)
(fermat-test 2465)

(define (square n)
  (* n n))

(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 (miller-rabin-test n)
  (define (test-p p k)
    (cond ((= k (- p 1)) true)
          ((= (remainder (* k k) p) 1) false)
          (else (test-p p (+ k 1)))))
  (define (try-it a)
    (= (expmod a (- n 1) n) 1))
  (cond ((not (test-p n 2)) false)
        ((try-it (+ 1 (random (- n 1)))) true)
        (else false)))

(define (fast-prime2? n times)
  (cond ((= n 2) true)
        ((= times 0) true)
        ((miller-rabin-test n) (fast-prime2? n (- times 1)))
        (else false)))

; 测试一下
(define (list-prime-less-than n)
  (cond ((= n 1) (displayln ""))
        ((fast-prime2? n 100)
            (displayln n)
            (list-prime-less-than (- n 1)))
        (else (list-prime-less-than (- n 1)))))

(list-prime-less-than 100)