;;;阶乘factorial
    ;;迭代
    (define (factorial n)
	(fact-iter 1 1 n))

    (define (fact-iter product counter max-count)
	(if (> counter max-count)
	    product 
	    (fact-iter (* counter product)
		       (+ counter 1)
		       max-count)))

    ;;递归
    (define (factorial n)
	(if (= n 1)
	    1
	    (* n (factorial (- n 1)))))

    ;;;菲波纳切数
    ;;树形递归
    (defun fib(n)
      (cond ((= n 1) 1)
	    ((= n 0) 0)
	    (t (+ (fib (1- n)) (- n 2)))))
    ;;线性迭代
    ;;法1
    (defun fib(n)
      (labels ((fib-iter (pa pb counter max-counter)
		 (cond ((> counter max-counter )
			pb)
		       (t (fib-iter pb (+ pa pb) (1+ counter) max-counter)))))
	(fib-iter 0 1 1  n)))
    ;;法2
    (defun fib (n)
      (labels ((fib-iter (b a count)
		 (if (= count 0) 
		     b
		     (fib-iter (+ b a) b (1- count)))))
	(fib-iter 1 0 n)))

    ;;树形递归
    (defun foo (n)
      (cond ((= n 0) 0)
	    ((= n 1) 1)
	    ((= n 2) 2)
	    (t (+ (foo (1- n)) (* 2 (foo (- n 2))) (* 3 (foo (- n 3)))))))
    ;;线性迭代
    (defun foo (n)
      (labels ((iter (c b a i)
		 (if (= i 2) c
		     (iter (+ c (* 2 b) (* 3 a)) c b (1- i)))))
	(iter 2 1 0 n)))


    ;;;SECTION 1.2.3
    ;;EXERCISE 1.15  正统sin(x)的数值计算
    (define (cube x) (* x x x))

    (define (p x) (- (* 3 x) (* 4 (cube x))))

    (define (sine angle)
	(if (not (> (abs angle) 0.1))
	    angle
	    (p (sine (/ angle 3.0)))))



    ;;;SECTION 1.2.4

    ;; Linear recursion
    (define (expt b n)
	(if (= n 0)
	    1
	    (* b (expt b (- n 1)))))


    ;; Linear iteration
    (define (expt b n)
	(expt-iter b n 1))

    (define (expt-iter b counter product)
	(if (= counter 0)
	    product
	    (expt-iter b
		       (- counter 1)
		       (* b product)))) 

    ;; Logarithmic recursion
    (define (fast-expt b n)
	(cond ((= n 0) 1)
	      ((even? n) (square (fast-expt b (/ n 2))))
	      (else (* b (fast-expt b (- n 1))))))

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

    ;;最佳答案
    (define (iter-fast-expt b n) 
	(define (iter N B A) 
	    (cond ((= 0 N) A) 
		  ((even? N) (iter (/ N 2) (square B) A)) 
		  (else (iter (- N 1) B (* B A))))) 
      (iter n b 1)) 

    ;;ex1.17
    (defun mul (a b)
      (labels ((mul-iter (a b c)
		 (cond ((zerop b)   c)
		       ((evenp b)  (mul-iter (dou a) (hal b) c))
		       (t   (mul-iter a  (1- b)  (+ c a)))))
	       (dou (n)
		 (* n 2))
	       (hal (n)
		 (/ n 2)))
	(mul-iter a b 0)))

	;;;1.2
  (defun smallest-divisor  (n)
	     (labels ((find-divisor (n test-divisor)
			(cond ((> (square test-divisor) n) n)
			      ((zerop (mod n test-divisor)) test-divisor)
			      (t (find-divisor n (1+ test-divisor)))))
		      (square (i)
			(* i i)))
	       (find-divisor n 2)))

  (defun prime? (n)
    (if (= 1 n) nil
	(= (smallest-divisor n) n)))

;;判断素数的九行scheme代码
  (define (smallest-div n) 
      (define (divides? a b) 
	  (= 0 (remainder b a))) 
    (define (find-div n test) 
	(cond ((> (sq test) n) n) ((divides? test n) test) 
	      (else (find-div n (+ test 1))))) 
    (find-div n 2)) 

  (define (prime? n) 
      (if (= n 1) false (= n (smallest-div n)))) 

  ;;;ex 1.22
  (let ((n (truncate 1e17)))
	       (loop for i upto 100 do
		 (if (prime? (+ n i))
		    (print (+ n i) )))) ;;=> search a prime number

  (timed-prime-test 99999998430674959 ) ;;=>  elapsed time is 8 second 

  (defun timed-prime-test( n)
	       (print n)
	     (start-prime-test n (get-universal-time)))

  (defun start-prime-test (n start-time)
	     (if (prime? n)
		 (report-prime (- (get-universal-time) start-time))))

  (defun report-prime ( elapsed-time)
	       (print " *** ")
	     (print  elapsed-time))

  ;;;1.2.6 fermat-prime?
  (defun expmod (base exp  m)
	     (labels ((square (i)
			(* i i)))
	       (cond ((zerop exp) 1)
		     ((evenp exp) 
		      (mod (square (expmod base (/ exp 2) m))
			   m))
		     (t  (mod (* base (expmod base (1- exp) m))
			      m)))))

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

  (defun fast-prime? (n times)
	     (cond ((zerop times ) 
		    t)
		   ((fermat-test n)   
		    (fast-prime? n (1- times)))
		   (t nil)))

  (loop repeat 100
	      count (fast-prime? 6 1))   =>58
  ;;数字6被单次的费马测试判断为素数的概率为60%左右。但可以知道数字6被10次的费马测试判断为素数的概率接近于0。同时，对于越大的非素数，一般来说其通过单次费马测试越难，因为相对于大数n，其基本无法找到一个数a<n，使(mod a^n n)= a ，而这为素数的必备。
  ;;大于100的整数被单次费马测试误判为素数的概率接近于0。

;;一个连续求和过程
  (define (sum term a next b) 
      (if (> a b) 
	  0
	  (+ a (sum term (next a) next b))))

  (define (itersum term a next b) 
      (define (iter a result) 
	  (if (> a b) 
	      result 
	      (iter (next a) (+ result (term a))))) 
    (iter a 0)) 
;;用sum过程定义积分integral
;;根据积分的定义可知，只需要对sum过程定义一个较小的步长dx，然后对sum过程得到的值乘以dx即可
(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2)) add-dx b)
     dx))

;: (integral cube 0 1 0.01)



  ;;1.31 定义连乘过程的递归计算过程或迭代计算过程
  (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 x result )
	  (if (> x b)
	      result 
	      (iter (next x) (* x result))))
    (iter 1  1))



  ;;1.32 用更一般的计算过程accumulate 来定义连续加法和连续乘法
  (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 (sum-acc term a next b)
      (define (combiner x y)
	  (+ x y))
    (accumulate combiner 0 term a next b))

  (define (product-acc term a next b)
      (define (combiner x y)
	  (* x y))
    (accumulate combiner 1 term a next b))

  ;;迭代过程
  (define (accumulate combiner null-value term a next b) 
      (define (iter a res) 
	  (if (> a b) res 
	      (iter (next a) (combiner res (term a))))) 
    (iter a null-value)) 

  ;;1.33 含有谓词筛选的连续计算过程filter-accumulate
  (define (filtered-accumulate combiner null-value term a next b filter) 
    (if (> a b) null-value 
	(if (filter a) 
	    (combiner (term a) (filtered-accumulate combiner null-value term (next a) next b filter)) 
	    (filtered-accumulate combiner null-value term (next a) next b filter))))

  ;; ;;两个数的最大公约数的欧几里得算法
  ;;  (define (gcd m n) 
  ;;    (cond ((< m n) (gcd n m)) 
  ;;          ((= n 0) m) 
  ;;          (else (gcd n (remainder m n))))) 

  ;;  (define (relative-prime? m n) 
  ;;  (= (gcd m n) 1)) 

  ;;filter-accumulate 用于计算所有与n互素（且小于n)的数的乘积。
   (define (product-of-relative-primes n) 
     (define (filter x) 
       (relative-prime? x n)) 
   (filtered-accumulate * 1 identity 1 inc n filter)) 

;;练习1.43
;;(repeated f n) 得到单参数过程f重复执行N次的单参数过程。
(define (repeated f n)
	  (cond ((= n 1) (lambda (x) (f x)))
		(else (lambda (x) (f ((repeated f (- n 1)) x))))))
;;((repeated inc  3) 1) => 4

P22页讲述二者区别????插入图片

ex2.38

;; 得到集合s的所有排序
(define (permutations s)
  (if (null? s)                         ; empty set?
      (list nil)                        ; sequence containing empty set
      (flatmap (lambda (x)
                 (map (lambda (p) (cons x p))
                      (permutations (remove x s))))
               s)))
;; (permutations '(1 2)) => ((1 2) (2 1))

(define (remove item sequence)
  (filter (lambda (x) (not (= x item)))
          sequence))

;;Nested mappings P84
;;嵌套映射可以用来枚举区间,有点像嵌套的 do 或者 loop ，不同的是append操作最终将枚举的结果全部放入一个单层表中
;: (accumulate append
;:             nil
;:             (map (lambda (i)
;:                    (map (lambda (j) (list i j))
;:                         (enumerate-interval 1 (- i 1))))
;:                  (enumerate-interval 1 n)))

(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))
;;(flatmap (lambda (i)
;:                    (map (lambda (j) (list i j))
;:                         (enumerate-interval 1 (- i 1))))
;:                  (enumerate-interval 1 3))   => ((2 1) (3 1) (3 2))
;;同样的枚举效果在SBCL中的代码为：
(let (var)
   (loop for i upto 3  do
      (loop for j from 0 upto (1- i) do
         (push (list i j) var)))
  (reverse var))
;;=> ((2 1) (3 1) (3 2))