;; 1.29
(define (simpson-integral f a b n)
  (define (coefficient i)
    (cond ((or (= i 0) (= i n)) 1)
          ((even? i) 2)
          (else 4)))
  (let ((h (/ (- b a)n )))
    (* (/ h 3)
       (sum (lambda (i) (* (f (+ a (* i h))) (coefficient i)))
            0
            (lambda (i) (+ i 1))
            n))))
 
;; 1.30
(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ result (term a)))))
  (iter a 0))
 
;; 1.31 只需要把sum改动两处。
; 递归实现
(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))
 
; 迭代实现
(define (product term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* result (term a)))))
  (iter a 1))
 
; 阶乘
(define (factorial n)
  (product (lambda (x) x) 1 (lambda (i) (+ 1 i)) n))
 
; π的近似值
(define (calc-pi n)
  (define (term i)
    (/ (- (square i) 1) (square i)))
  (define (next i)
    (+ 2 i))
  (* 4 (product term 3.0 next n)))
 
;; 1.32
(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (accumulate combiner null-value term (next a) next b))))
 
(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner result (term a)))))
  (iter a null-value))
 
;; 1.33
; filtered-accumulate 的两种实现
(define (filtered-accumulate combiner null-value term a next b filter)
  (define (do-filter x)
    (if (filter x) x null-value))
  (if (> a b)
      null-value
      (combiner (do-filter (term a))
                (filtered-accumulate combiner null-value term (next a) next b filter))))
 
(define (filtered-accumulate combiner null-value term a next b filter)
  (define (do-filter x)
    (if (filter x) x null-value))
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner result (do-filter (term a))))))
  (iter a null-value))
 
; (a)
(filtered-accumulate + 0 (lambda (x) x) a (lambda (i) (+ 1 i)) b prime?)
; (b)
(filtered-accumulate * 1 (lambda (x) x) 1 (lambda (i) (+ 1 i)) (- 1 n) (lambda (a) (= 1 (gcd a n))))
 
;; 1.34 (f f)相当于(f 2)，相当于(2 2)，会因为2并非可以调用的函数而出错。
 
;; 1.35 证明不动点直接计算即可，计算的(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)。
 
;; 1.36 全部代码如下
(define tolerance 0.00001)
 
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (display guess)
    (newline)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))
 
(define (f x) (/ (log 1000) (log x)))
 
(display (fixed-point f 2))
(newline) (newline)
(display (fixed-point (lambda (x) (average x (f x))) 2))
(newline) (newline)
 
; 使用与不使用平均阻尼的步数分别为9与34步。
 
;; 1.37
; 递归版本
(define (cont-frac n d k)
  (define (shift f)
    (lambda (i) (f (+ 1 i))))
  (if (= 0 k)
      0
      (/ (n 1) (+ (d 1) (cont-frac (shift n) (shift d) (- k 1))))))
 
; 迭代版本
(dsefine (cont-frac n d k)
  (define (iter result i)
    (if (= 0 i)
        result
        (iter (/ (n i) (+ (d i) result)) (- i 1))))
  (iter 0 k))
 
; 当k不小于11时，结果有4位精度。
 
;; 1.38
(define (e-2 k)
  (cont-frac (lambda (i) 1.0)
             (lambda (i)
               (if (= 2 (remainder i 3))
                   (* 2 (/ (+ 1 i) 3))
                   1))
             k))
 
;; 1.39
(define (tan-cf x k)
  (cont-frac (lambda (i)
               (if (= 1 i) x (- (square x))))
             (lambda (i)
               (- (* 2 i) 1))
             k))
 
;; 1.40
(define (cubic a b c)
  (lambda (x)
    (+ c (* x (+ b (* x (+ a x)))))))
 
;; 1.41
; double函数
(define (double f)
  (lambda (x)
    (f (f x))))
 
;; (((double (double double)) inc) 5) 的值为21。因为 (double double) 得到一个把参数过程应用四次的函数，而 (double (double double)) 事实上是将“把参数过程应用四次”的过程应用两次，也就是一个将参数过程应用十六次的函数。
 
;; 1.42
(define (compose f g)
  (lambda (x) (f (g x))))
 
;; 1.43
(define (repeated f n)
  (if (= 1 n)
      f
      (compose f (repeated f (- n 1)))))
 
;; 1.44
(define (n-times-smooth f dx n)
  ((repeated (lambda (f) (smooth f dx)) n) f))
 
;; 1.45
(define (calc-nth-root-with-t-average-damps x n t)
  (fixed-point ((repeated average-damp t) (lambda (y) (/ x (fast-expt y (- n 1))))) 1.0))
 
;; 通过实验，得到的规律是，当 2^t>=n 时，用 t 次平均阻尼求 n 次方根是可行的，于是有下面的程序。
(define (nth-root x n)
  (define (minimal-t n)
    (if (= 1 n)
        0
        (+ 1 (minimal-t (quotient n 2)))))
  (calc-nth-root-with-t-average-damps x n (minimal-t n)))
 
;; 1.46
(define (iterative-improve guess improve good-enough?)
  (if (good-enough? guess)
      guess
      (iterative-improve (improve guess) improve good-enough?)))
 
(define (sqrt x)
  (define (improve y)
    (/ (+ x (square y)) (* 2 y)))
  (define (good-enough? y)
    (> tolerance (abs (- (square y) x))))
  (iterative-improve 1.0 improve good-enough?))
 
(define (fixed-point f first-guess)
  (define (improve x)
    (f x))
  (define (good-enough? x)
    (> tolerance (abs (- (f x) x))))
  (iterative-improve first-guess improve good-enough?))

;; 1.1-2 略
 
;; 1.3
(define (greater-two a b c)
  (-
   (+ a b c)
   (min a b c)))
; 或
(define (greater-two a b c)
  (cond ((and (> b a) (> c a))
         (+ b c))
        ((and (> a b) (> c b))
         (+ a c))
        (else (+ a b))))
 
;; 1.4 (if (> b 0) + -) 根据b的正负性返回函数+或-。
 
;; 1.5 函数p的定义 (define (p) (p)) 是不断递归调用自己，所以欲对其进行求值/展开会产生死循环。调用 (test 0 (p)) 时，若采用应用序求值，会先对函数的参数，包括 (p) 求值，因而产生死循环，无法输出结果；若采用正则序求值，则由于 (p) 的值事实上不会被展开，故会正常返回0。
 
;; 1.6 将在调用函数 new-if 时，应用序要求先算出其所有参数的值，new-if 的后两个参数——代表 if 的两个分支的代码都将被执行。所以 (sqrt-iter guess x) 必然需要调用 (sqrt-iter (improve guess x) x)，这导致死循环。
 
;; 1.7
(define (sqrt x)
  (define (sqrt-iter guess)
    (define (good-enough?)
      (< (abs (/ (- (* guess guess) x) x)) 0.001))
    (define (improve)
      (define (average a b)
        (/ (+ a b) 2))
      (average guess (/ x guess)))
    (if (good-enough?)
        guess
        (sqrt-iter (improve))))
  (sqrt-iter 1.0))
 
;; 1.8
(define (cube-root x)
  (define (iter guess)
    (define (good-enough?)
      (< (abs (/ (- (* (* guess guess) guess) x) x)) 0.001))
    (define (improve)
      (/ (+ ( / x (* guess guess)) (* 2 guess)) 3))
    (if (good-enough?)
        guess
        (iter (improve))))
  (iter 1.0))
 
;; 1.9 第一个过程是递归的，表达式被递归地逐渐展开再合并；第二个过程中的递归是尾递归，不妨理解为迭代的。
 
;; 1.10 (f n)是n的2倍，(g n)是2的n次方，(h n)是2的(h (- n 1))次方。
 
;; 1.11
; 递归方式
(define (f n)
  (if (< n 3) n
      (+ (f (- n 1))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3))))))
 
; 迭代方式
 
(define (f n)
  (define (iter a b c i)
    (if (= i n) c
        (iter b c
              (+ (* 3 a) (* 2 b) c)
              (+ i 1))))
  (if (< n 3) n
      (iter 0 1 2 2)))
 
;; 1.12
(define (C n i)
  (if (or (= i 0) (= i n))
      1
      (+ (C (- n 1) (- i 1)) (C (- n 1) i))))
 
;; 1.13 可利用归纳法和定义直接证。
 
;; 1.14 空间复杂度为 O(amount)，因为任何时刻调用链的长度（栈上的函数数量）不超过 amount+1；时间复杂度为 O(amount * result)，因为每得到一种方案都调用一次 (cc 0 kinds-of-coins)。
 
;; 1.15 空间与时间复杂度均为O(log a)。
 
;; 1.16 prod*a^m是不变量。
(define (fast-expt b n)
  (define (iter prod a m)
    (if (= 0 m) prod
        (if (= 0 (remainder m 2))
            (iter prod (* a a) (/ m 2))
            (iter (* prod a) (* a a) (/ (- m 1) 2)))))
  (iter 1 b n))
 
;; 1.17
(define (fast-multi a b)
  (if (= 1 a) b
      (if (= 0 (remainder a 2))
          (double (fast-multi (halve a) b))
          (+ b (double (fast-multi (halve (- a 1)) b))))))
 
;; 1.18
(define (fast-multi a b)
  (define (iter sum i n)
    (if (= 0 n) sum
        (if (= 0 (remainder n 2))
            (iter sum (double i) (halve n))
            (iter (+ sum i) (double i) (halve (- n 1))))))
  (iter 0 a b))
 
;; 1.19 p’ = pp + qq，q’ = qq + 2pq。
 
;; 1.20 应用序需要4次；正则序需要更多，没仔细数，因为gcd函数体中出现了三处b，当b是调用remainder的形式时，它需要被展开若干次。
 
;; 1.21 略。
 
;; 1.22-24 我用的DrScheme没有定义runtime……555
 
;; 1.25 如果不在计算乘幂时随时取模，每次乘法将由于被乘数位数的迅速增长而不能被看做单位时间的原子操作。
 
;; 1.26 每次(expmod base exp m)当exp为正偶数时会调用两次而非一次(expmod base exp m)，f(N)=2*f(N/2)+Θ(1)导致f(N)=Θ(N)，而原始版本的f(N)=f(N/2)+Θ(1)导致f(N)=Θ(log N)。
 
;; 1.27 以下程序中，(find-carmichael n)找出不超过n的Carmichael数
 
(define (prime? n)
  (define (iter i)
    (cond
      ((> (square i) n) true)
      ((= 0 (remainder n i)) false)
      (else (iter (+ i 1)))))
  (iter 2))
 
(define (carmichael? n)
  (define (iter i)
    (cond
      ((= i n) true)
      ((not (= i (expmod i n n))) false)
      (else (iter (+ i 1)))))
  (and (not (prime? n)) (iter 2)))
 
(define (find-carmichael n)
  (define (iter i)
    (cond ((carmichael? i) (display i) (display "\n")))
    (cond ((< i n) (iter (+ i 1)))))
  (iter 2))
 
;; 1.28
(define (miller-rabin n)
  (define (exp-iter prod base exp)
    (cond ((and (< 1 prod) (< prod (- n 1)) (= (remainder (* prod prod) n) 1)) 0)
          ((= 0 exp) prod)
          (else (if (even? exp)
                    (exp-iter
                     prod
                     (remainder (* base base) n)
                     (/ exp 2))
                    (exp-iter
                     (remainder (* prod base) n)
                     (remainder (* base base) n)
                     (/ (- exp 1) 2))))))
  (define (check i)
    (= 1 (exp-iter 1 i (- n 1))))
  (define (check-iter i)
    (cond ((= i 0) true)
          (else (if (check (+ 2 (random (- n 3))))
                    (check-iter (- i 1)) false))))
  (or (= 2 n) (= 3 n)
      (and (< 2 n) (= 1 (remainder n 2)) (check-iter 20))))