发表于   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2014/01/20/2014-01-20-练习1.23-练习1.30/

访问原文「练习1.23-练习1.30」

1.练习1.23
改后的代码如下：

1
2
3
4
5
6
7
8
9
(define (find-divisor-better n a)
  (cond ((> (square a) n) n)
	((divides?-better n a) a)
	(else (find-divisor-better n (next-2 a)))))
(define (next-2 n)
  (if (= 2 n)
      (+ 1 n)
      (+ 2 n)))
1
2
3
4
5
6
7
(define (find-min-prime-since-better n start-time number)
  (cond ((= number 0) (display-info start-time (real-time-clock)))
	((prime? n) (begin
		      (format #t "~S~%" n)
		      (find-min-prime-since-better (+ n (next-plus n)) start-time (- number 1))))
	(else (find-min-prime-since-better (+ n (next-plus n)) start-time number)))
  #f)
1
2
3
4
(define (next-plus n)
  (if (even? n)
      1
      2))

电脑跑这些代码的时候，没有固定的运行时间，一直在变。不过结果是改后的基本是没改前的0.5，也可能0.6左右。
2.练习1.24
代码就不贴出来了，只是将上一题中的判断是否为素数的方法改为费马方法。
在检测接近1000000的素数和接近1000的素数时，接近1000000的素数在时间上应该为(log1000000)=6应该大于接近1000的3的素数检查，比值为2:1，实验中计算从1000和1000000开始的1000个素数，1000开始的时间为695，而从1000000开始的时间为1470，比值接近于1:2， 与假设基本相同。
但是在帖子，那我猜，可能是64位和32位的不同了。
3.练习1.25
先求次方的结果会导致一个很大的数求余数，这样的时间消耗会很大。
4.练习1.26
不使用square的结果是每次减半的expmod操作没有了简版的效果，所以时间复杂度会变回O(n) 。
5.练习1.27

1
2
3
4
5
6
7
8
9
10
(define (try-it a n)
    (= (expmod a n n) a))
(define (carmichael-test n number)
  (cond ((= number 0) true)
	((try-it number n) (carmichael-test n (- number 1)))
	(else false)))
(define (car-prime? n)
  (carmichael-text n (- n 1)))

6.练习1.28

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
(define (new-expmod base exp m)
  (define tmpbase 100)
  (cond ((= exp 0) 1)
	((even? exp) (begin
		      (set! tmpbase (new-expmod base (/ exp 2) m))
		      (if (and (not (= tmpbase (- m 1)))
			       (not (= tmpbase 1))
			       (= (remainder (square tmpbase)
					       m) 1))
			   0
			   (remainder (square tmpbase)
					 m))))
	(else (remainder (* base (new-expmod base (- exp 1) m))
			 m))))
(define (new-try-it n a)
  (new-expmod a (- n 1) n))
(define (new-fermat-test n start)
  (cond ((= start 1) true)
	((= (new-try-it n start) 0) false)
	(else (new-fermat-test n (- start 1)))))
(define (really-prime? n)
 (new-fermat-test n (if (even? n)
			(/ n 2)
			(/ (- n 1) 2))))

没有进行优化，但本身也有可能会有更好的方法吧

发表于   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2014/01/20/2014-01-20-练习2.41-练习2.47/

访问原文「练习2.41-练习2.47」

1.练习2.41

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(define (seprate-except x except)
  (filter (lambda (couple) 
            (let ((first (car couple))
                  (second (cadr couple)))
            (and (not (= first except))
                 (not (= second except))
                 (not (= first second)))))
          (map (lambda (n) (list n (- x n)))
               (enumerate-interval 1 (- x 1)))
          )
  )
(define (flatmap proc seq)
  (accumulate append '() (map proc seq)))
(define (seprate-to-three n)
  (flatmap (lambda (x) 
             (map (lambda (y) (cons x y)) 
                  (seprate-except (- n x) x)))
           (enumerate-interval 1 (- n 1)))
  )

2.练习2.42

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
(define empty-board '())
(define (adjoin-position new-row k rest-of-queens)
  (cons (list k new-row) rest-of-queens))
(define (safe? k positions)
  (define (check-safe col row rest-positions)
    (if (null? rest-positions)
        true
        (let ((first-position-col (car (car rest-positions)))
              (first-position-row (cadr (car rest-positions)))
              (remain-positions (cdr rest-positions)))
          (and (not (= col first-position-col))
               (not (= row first-position-row))
               (not (= (abs (- col first-position-col))
                       (abs (- row first-position-row))))
               (check-safe col row remain-positions)))))
  (if (null? positions)
      true
      (let ((col (car (car positions)))
            (row (cadr (car positions)))
            (rest (cdr positions)))
        (if (null? rest)
            true
            (check-safe col row rest)))))

3.练习2.43
因为重复计算k-1的皇后问题。
4.练习2.44

1
2
3
4
5
6
7
(require (planet "sicp.ss" ("soegaard" "sicp.plt" 2 1)))
(define (up-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (up-split painter (- n 1))))
        (below painter (beside smaller smaller)))))

5.练习2.45

1
2
3
4
5
6
(define (split action1 action2)
  (lambda (painter n)
    (if (= n 0)
        painter
        (let ((smaller ((split action1 action2) painter (- n 1))))
          (action1 painter (action2 smaller smaller))))))

6.练习2.46

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(define (make-vect x y)
  (cons x y))
(define (xcor-vect v)
  (car v))
(define (ycor-vect v)
  (cdr v))
(define (add-vect v1 v2)
  (make-vect (+ (xcor-vect v1)
                (xcor-vect v2))
             (+ (ycor-vect v1)
                (ycor-vect v2))))
(define (sub-vect v1 v2)
  (make-vect (- (xcor-vect v1)
                (xcor-vect v2))
             (- (ycor-vect v1)
                (ycor-vect v2))))
(define (scale-vect v s)
  (make-vect (* s (xcor-vect v))
             (* s (ycor-vect v))))

7.练习2.47

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(define (make-frame-list origin edge1 edge2)
  (list origin edge1 edge2))
(define (make-frame-cons origin edge1 edge2)
  (cons origin (cons edge1 edge2)))
(define (origin-frame-list frame)
  (car frame))
(define (edge1-frame-list frame)
  (cadr frame))
(define (edge2-frame-list frame)
  (caddr frame))
(define (origin-frame-cons frame)
  (car frame))
(define (edge1-frame-cons frame)
  (cadr frame))
(define (edge2-frame-cons frame)
  (cddr frame))

发表于   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2014/01/17/2014-01-17-练习2.11-练习2.20/

访问原文「练习2.11-练习2.20」

1.练习2.11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(define (mul-interval x y)
  (let ((x1 (lower-bound x))
	(x2 (upper-bound x))
	(y1 (lower-bound y))
	(y2 (upper-bound y)))
    (let
	((zzx (and (>= x1 0) (>= x2 0)))
	 (zzy (and (>= y1 0) (>= y2 0)))
	 (fzx (and (< x1 0) (>= x2 0)))
	 (fzy (and (< y1 0) (>= y2 0)))
	 (ffx (and (< x1 0) (< x2 0)))
	 (ffy (and (< y1 0) (< y2 0))))
      (cond (zzy (cond (zzx (make-interval (* x1 y1) (* x2 y2)))
		       (fzx (make-interval (* x1 y2) (* x2 y2)))
		       (ffx (make-interval (* x1 y2) (* x2 y1)))))
	    (fzy (cond (zzx (make-interval (* x2 y1) (* x2 y2)))
		       (fzx (make-interval (min (* x1 y2) (* x2 y1))
					   (max (* x1 y1) (* x2 y2))))
		       (ffx (make-interval (* x1 y2) (* x1 y1)))))
	    (ffy (cond (zzx (make-interval (* x2 y1) (* x1 y2)))
		       (fzx (make-interval (* x2 y1) (* x1 y1)))
		       (ffx (make-interval (* x2 y2) (* x1 y1)))))))))

2.练习2.12

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(define (mul-interval x y)
  (let ((x1 (lower-bound x))
	(x2 (upper-bound x))
	(y1 (lower-bound y))
	(y2 (upper-bound y)))
    (let
	((zzx (and (>= x1 0) (>= x2 0)))
	 (zzy (and (>= y1 0) (>= y2 0)))
	 (fzx (and (< x1 0) (>= x2 0)))
	 (fzy (and (< y1 0) (>= y2 0)))
	 (ffx (and (< x1 0) (< x2 0)))
	 (ffy (and (< y1 0) (< y2 0))))
      (cond (zzy (cond (zzx (make-interval (* x1 y1) (* x2 y2)))
		       (fzx (make-interval (* x1 y2) (* x2 y2)))
		       (ffx (make-interval (* x1 y2) (* x2 y1)))))
	    (fzy (cond (zzx (make-interval (* x2 y1) (* x2 y2)))
		       (fzx (make-interval (min (* x1 y2) (* x2 y1))
					   (max (* x1 y1) (* x2 y2))))
		       (ffx (make-interval (* x1 y2) (* x1 y1)))))
	    (ffy (cond (zzx (make-interval (* x2 y1) (* x1 y2)))
		       (fzx (make-interval (* x2 y1) (* x1 y1)))
		       (ffx (make-interval (* x2 y2) (* x1 y1)))))))))

3.练习2.13中文的翻译太差了，句中的“两个被乘区间的误差”应该是“被乘区间的百分比误差”吧，很生气。。。
4.练习2.14
5.练习2.15
因为引入的误差少，所以更精确
6.练习2.16
设计一种好难啊
7.练习2.17

1
2
3
4
5
6
7
(define (last-pair items)
  (let ((len (length items)))
    (define (last-pair-iter item tmplen)
      (if (= tmplen 1)
	  item
	  (last-pair-iter (cdr item) (- tmplen 1))))
    (last-pair-iter items len)))

8.练习2.18

1
2
3
4
5
6
7
(define (reverse items)
  (define (reverse-iter tmpitems result)
    (if (null? tmpitems)
	result
	(reverse-iter (cdr tmpitems)
		      (cons (car tmpitems) result))))
  (reverse-iter items '()))

9.练习2.19

1
2
3
4
5
6
7
8
(define (first-denomination list1)
  (car list1))
(define (except-first-denomination list1)
  (cdr list1))
(define (no-more? list1)
  (null? list1))

10.练习2.20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define (same-parity . other)
  (define (even-number? number)
    (= (remainder number 2) 0))
  (define (same-parity-recur even items)
    (if (null? items)
	'()
	(let ((now-even (even-number? (car items)))
	      (next (same-parity-recur even (cdr items))))
	  (if (or (and even now-even)
		  (and (not even) (not now-even)))
	      (cons (car items) next)
	      next))))
  (let ((evenodds (even-number? (car other))))
    (same-parity-recur evenodds other)))

发表于   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2014/01/15/2014-01-15-练习2.2-练习2.10/

访问原文「练习2.2-练习2.10」

1.练习2.2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(define (make-segment start end)
  (cons start end))
(define (start-segment seg)
  (car seg))
(define (end-segment seg)
  (cdr seg))
(define (make-point x y)
  (cons x y))
(define (x-point p)
  (car p))
(define (y-point p)
  (cdr p))
1
2
3
4
5
(define (midpoint-segment seg)
  (make-point (/ (+ (x-point (start-segment seg))
		    (x-point (end-segment seg))) 2)
	      (/ (+ (y-point (start-segment seg))
		    (y-point (end-segment seg))) 2)))

2.练习2.3首次定义：

1
2
3
4
5
6
7
8
(define (make-rect start end)
  (cons start end))
(define (start-rect seg)
  (car seg))
(define (end-rect seg)
  (cdr seg))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(define (width rect)
  (abs (- (y-point (end-rect rect))
	  (y-point (start-rect rect)))))
(define (length rect)
  (abs (- (x-point (end-rect rect))
	  (x-point (start-rect rect)))))
(define (girth rect)
  (* (+ (width rect)
	(length rect))
     2))
(define (area rect)
  (* (width rect)
     (length rect)))

二次定义：

1
2
3
4
5
6
7
8
9
10
11
12
(define (make-rect start length width)
  (cons start
	(cons length width)))
(define (start-rect seg)
  (car seg))
(define (end-rect seg)
  (cons (+ (x-point (start-rect seg))
	   (car (cdr seg)))
	(+ (y-point (start-rect seg))
	   (cdr (cdr seg)))))

3.练习2.4

1
2
3
4
5
6
7
8
(define (cons x y)
  (lambda (m) (m x y)))
(define (car z)
  (z (lambda (p q) p)))
(define (cdr z)
  (z (lambda (p q) q)))

4.练习2.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(define (cons a b)
  (* (pow 2 a)
     (pow 3 b)))
(define (car c)
  (define (iter n result)
    (if (not (= (remainder n 2) 0))
	result
	(iter (/ n 2) (+ result 1))))
  (iter c 0))
(define (cdr c)
  (define (iter n result)
    (if (not (= (remainder n 3) 0))
	result
	(iter (/ n 3) (+ result 1))))
  (iter c 0))

5.练习2.6

1
2
3
4
5
(define one
  (lambda (f) (lambda (x) (f x))))
(define two
  (lambda (f) (lambda (x) (f (f x)))))
1
2
(define (add a b)
  (lambda (f) (lambda (x) ((b f) ((a f) x)))))

6.练习2.7

1
2
3
4
5
6
7
8
(define (make-interval x y)
  (cons x y))
(define (upper-bound c)
  (cdr c))
(define (lower-bound c)
  (car c))

7.练习2.8

1
2
3
4
5
(define (sub-interval x y)
  (let ((a (- (lower-bound x) (lower-bound y)))
	(b (- (upper-bound x) (upper-bound y))))
    (make-interval (min a b)
		   (max a b))))

8.练习2.9

1
2
3
4
(define (width-interval a)
  (/ (- (upper-bound a)
	(lower-bound a))
     2))

9.练习2.10

1
2
3
4
5
6
(define (div-interval x y)
  (if (and (<= (lower-bound y) 0) (>= (upper-bound y) 0))
      (error "ERROR!!!")
      (mul-interval x
		       (make-interval (/ 1.0 (upper-bound y))
				      (/ 1.0 (lower-bound y))))))

发表于   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2014/01/14/2014-01-14-练习2.1/

访问原文「练习2.1」

1.练习2.1

1
2
3
4
5
6
7
8
9
10
11
12
(define (check-pos-neg a b)
  (or (and (not (< a 0)) (> b 0))
      (and (not (> a 0)) (< b 0))))
(define (make-rat n d)
  (let ((g (gcd (abs n) (abs d)))
	(posi (check-pos-neg n d)))
    (cons (/ (if posi
		 (abs n)
		 (- (abs n)))
	     g)
	  (/ (abs d) g))))

发表于   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2014/01/13/2014-01-13-练习1.40-练习1.46/

访问原文「练习1.40-练习1.46」

1.练习1.40

1
2
3
4
5
6
7
8
(define (cubic a b c)
  (define (cube x)
    (* x x x))
  (lambda (x)
    (+ (cube x)
       (* a (square x))
       (* b x)
       c)))
1
2
3
4
(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))
(newtons-method (cubic 1 0 0) 1)

2.练习1.41

1
2
3
4
(define (double f)
  (lambda (x) (f (f x))))
(((double (double double)) (lambda (x) (+ x 1))) 5)

结果是21，真的很不想解释。(double double)展开是(f (f (f (f x))))
(double (double double))展开是(f’ (f‘ (f’ (f‘ x)))))))，每个f‘为(f (f (f (f x))))，一共是16个f，所以结果是5+16=21
3.练习1.42

1
2
(define (compose f g)
  (lambda (x) (f (g x))))

4.练习1.43

1
2
3
4
(define (repeated f n)
  (if (= n 1)
      (lambda (x) (f x))
      (lambda (x) (f ((repeated f (- n 1)) x)))))

5.练习1.44这个有点儿直接了，没有简化

1
2
3
4
5
6
7
8
9
10
(define (smooth f)
  (let ((dx 0.0000001))
    (lambda (x) (/
		 (+
		  (f (- x dx))
		  (f x)
		  (f (+ x dx)))
		 3))))
(((repeated smooth 6) square) 2)

6.练习1.45也是没有简化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(define (average-dump-time n)
  (floor (/ (log n) (log 2))))
(define (cifanggen x n)
  (define (product term a next b)
    (if (> a b)
	1
	(* (term a)
	   (product term (next a) next b)))) 
  (define (cifang x n)
    (product (lambda (i) x)
	     1
	     (lambda (i) (+ i 1))
	     n))
  (fixed-point ((repeated average-dump (average-dump-time n)) (lambda (i) (/ x (cifang i (- n 1)))))
	       n))

7.练习1.46

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define (iterative-improve good-enough? improve)
   (lambda (a) (if (good-enough? a (improve a))
		   (improve a)
		   ((iterative-improve good-enough? improve) (improve a)))))
(define (fixed-point f guess)
  (define (good-enough1? a b)
    (let ((tolerance 0.000001))
      (< (abs (- a b)) tolerance)))
  ((iterative-improve good-enough1? f) guess))
(define (sqrt n)
  (fixed-point (lambda (y) (/ (+ y (/ n y)) 2))
	       1.0))

发表于   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2014/01/11/2014-01-11-练习1.35-练习1-38/

访问原文「练习1.35-练习1-38」

1.练习1.35

1
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)

2.练习1.36不用平均阻尼方式：

1
(fixed-point-display (lambda (x) (/ (log 1000) (log x))) 2.0)

结果为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2.
9.965784284662087
3.004472209841214
6.279195757507157
3.759850702401539
5.215843784925895
4.182207192401397
4.8277650983445906
4.387593384662677
4.671250085763899
4.481403616895052
4.6053657460929
4.5230849678718865
4.577114682047341
4.541382480151454
4.564903245230833
4.549372679303342
4.559606491913287
4.552853875788271
4.557305529748263
4.554369064436181
4.556305311532999
4.555028263573554
4.555870396702851
4.555315001192079
4.5556812635433275
4.555439715736846
4.555599009998291
4.555493957531389
4.555563237292884
4.555517548417651
4.555547679306398
4.555527808516254
4.555540912917957
;Value: 4.555532270803653

平均阻尼的方法：

1
(fixed-point-display (lambda (x) (/ (+ (/ (log 1000) (log x)) x) 2.0)) 2.0)

结果是：

1
2
3
4
5
6
7
8
9
10
2.
5.9828921423310435
4.922168721308343
4.628224318195455
4.568346513136242
4.5577305909237005
4.555909809045131
4.555599411610624
4.5555465521473675
;Value: 4.555537551999825

3.练习1.37a）

1
2
3
4
5
6
(define (cont-frac n d k)
  (define (cont-prac-recur n d a k)
    (if (= a k)
	(/ (n k) (d k))
	(/ (n a) (+ (d a) (cont-prac-recur n d (+ a 1) k)))))
  (cont-prac-recur n d 1 k))

k为11时得到的近似值具有十进制的4位精度b）
迭代计算过程：

1
2
3
4
5
6
(define (cont-frac n d k)
  (define (cont-prac-iter a result)
    (cond ((= a k) (cont-prac-iter (- a 1) (/ (n k) (d k))))
	  ((= a 0) result)
	  (else (cont-prac-iter (- a 1) (/ (n a) (+ result (d a)))))))
  (cont-prac-iter k 0))

4.练习1.38

1
2
3
4
5
6
7
(define (dfc-k k)
  (+ (cont-frac (lambda (i) 1.0)
(lambda (i) (if (= (remainder i 3) 2)
(* (+ (floor (/ i 3)) 1) 2)
1))
k
) 2))

5.练习1.39

1
2
3
4
5
6
7
(define (tan-cf x k)
  (cont-frac (lambda (i) (if (= i 1)
			     x
			     (- 0 (square x))))
	     (lambda (i) (+ (* (- i 1) 2) 1))
	     k
	     ))

发表于   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2014/01/10/2014-01-10-练习1.31-练习1.34/

访问原文「练习1.31-练习1.34」

最近对于Lisp的强大和高深还是深有体会的，可以将函数作为参数进行调用，这样在很大的程度上可以提高函数的抽象性，即将具有公共模式的函数进行抽象。例如在SICP中，首先将累加和的过程进行了抽象，然后在累加和的基础上抽象出了累乘积，进而又发现了累加和与累乘积的共同点，进一步抽象成了一个叫做accumulate的函数，这个函数的是这样的

1
(accumulate combiner null-value term a next b)

其中combiner为被组合项的组合方式，例如在累加和中可以是“+”，在累乘积中可以是“*”，null-value为默认值，在累加和中为0累乘积中为1，term为函数f，例如在求cube的积分时，f为cube，a为初始值，next为下一次取得值，b为取值的上限。最后在accumulate函数的基础上加上了对数据的filter使得整个过程更加抽象更加一般。
1.练习1.31
a）

1
2
3
4
5
(define (product-recur term a next b)
  (if (> a b)
      1
      (* (term a)
	 (product-recur term (next a) next b))))
1
2
3
4
5
6
7
8
(define (factorial-recur n)
  (define (self n)
    n)
  (define (plus-1 n)
    (+ n 1))
  (if (= n 0)
      1
      (product-recur self 1 plus-1 n)))
1
2
3
4
5
6
7
8
9
10
11
(define (pi-recur n)
  (define (even? n)
    (= (remainder n 2) 0))
  (define (item n)
    (if (even? n)
	(/ (+ 2 n) (+ 1 n))
	(/ (+ 1 n) (+ 2 n))))
  (define (next-1 n)
    (+ n 1.0))
  (* 4.0
     (product-recur item 1.0 next-1 n)))

b）

1
2
3
4
5
6
(define (product-iter term a next b)
  (define (iter a result)
    (if (> a b)
	result
	(iter (next a) (* (term a) result))))
  (iter a 1))

2.练习1.32a）

1
2
3
4
5
(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))))
1
2
3
4
5
(define (sum-accumulate term a next b)
  (accumulate + 0 term a next b))
(define (product-accumulate term a next b)
  (accumulate-iter * 1 term a next b))

b）

1
2
3
4
5
6
(define  (accumulate-iter 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))

3.练习1.33

1
2
3
4
5
6
(define (filtered-accumulate filter combiner null-value term a next b)
  (define (iter a result)
    (cond ((> a b) result)
	  ((filter a) (iter (next a) (combiner (term a) result)))
	  (else (iter (next a) result))))
  (iter a null-value))

a）

1
2
3
4
5
6
(define (prime-sum a b)
  (define (next-1 a)
    (+ a 1))
  (define (self a)
    a)
  (filtered-accumulate prime? + 0 self a next-1 b))

b）

1
2
3
4
5
6
7
8
(define (GCD-1-product n)
  (define (GCD-1-n? a)
    (= (GCD a n) 1))
  (define (next-1 a)
    (+ a 1))
  (define (self a)
    a)
  (filtered-accumulate GCD-1-n? * 1 self 1 next-1 (- n 1)))

4.练习1.34可以这么解释(f f)->(f 2)->(2 2)，最后由于2这个函数没有定义，所以报错结束。

网上发现了这个点击打开链接，很不错，貌似是一些人做的项目，目的是解答SICP上的所有题，貌似很久没有更新了，但以后做了题还是可以和这个上面已有的解答对对了。

发表于   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2014/01/09/2014-01-09-练习1.23-练习1.30/

访问原文「练习1.23-练习1.30」

1.练习1.23
改后的代码如下：

1
2
3
4
5
6
7
8
9
(define (find-divisor-better n a)
  (cond ((> (square a) n) n)
	((divides?-better n a) a)
	(else (find-divisor-better n (next-2 a)))))
(define (next-2 n)
  (if (= 2 n)
      (+ 1 n)
      (+ 2 n)))
1
2
3
4
5
6
7
(define (find-min-prime-since-better n start-time number)
  (cond ((= number 0) (display-info start-time (real-time-clock)))
	((prime? n) (begin
		      (format #t "~S~%" n)
		      (find-min-prime-since-better (+ n (next-plus n)) start-time (- number 1))))
	(else (find-min-prime-since-better (+ n (next-plus n)) start-time number)))
  #f)
1
2
3
4
(define (next-plus n)
  (if (even? n)
      1
      2))

电脑跑这些代码的时候，没有固定的运行时间，一直在变。不过结果是改后的基本是没改前的0.5，也可能0.6左右。
2.练习1.24
代码就不贴出来了，只是将上一题中的判断是否为素数的方法改为费马方法。
在检测接近1000000的素数和接近1000的素数时，接近1000000的素数在时间上应该为(log1000000)=6应该大于接近1000的3的素数检查，比值为2:1，实验中计算从1000和1000000开始的1000个素数，1000开始的时间为695，而从1000000开始的时间为1470，比值接近于1:2， 与假设基本相同。
但是在帖子，那我猜，可能是64位和32位的不同了。
3.练习1.25
先求次方的结果会导致一个很大的数求余数，这样的时间消耗会很大。
4.练习1.26
不使用square的结果是每次减半的expmod操作没有了简版的效果，所以时间复杂度会变回O(n) 。
5.练习1.27

1
2
3
4
5
6
7
8
9
10
(define (try-it a n)
    (= (expmod a n n) a))
(define (carmichael-test n number)
  (cond ((= number 0) true)
	((try-it number n) (carmichael-test n (- number 1)))
	(else false)))
(define (car-prime? n)
  (carmichael-text n (- n 1)))

6.练习1.28

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
(define (new-expmod base exp m)
  (define tmpbase 100)
  (cond ((= exp 0) 1)
	((even? exp) (begin
		      (set! tmpbase (new-expmod base (/ exp 2) m))
		      (if (and (not (= tmpbase (- m 1)))
			       (not (= tmpbase 1))
			       (= (remainder (square tmpbase)
					       m) 1))
			   0
			   (remainder (square tmpbase)
					 m))))
	(else (remainder (* base (new-expmod base (- exp 1) m))
			 m))))
(define (new-try-it n a)
  (new-expmod a (- n 1) n))
(define (new-fermat-test n start)
  (cond ((= start 1) true)
	((= (new-try-it n start) 0) false)
	(else (new-fermat-test n (- start 1)))))
(define (really-prime? n)
 (new-fermat-test n (if (even? n)
			(/ n 2)
			(/ (- n 1) 2))))

没有进行优化，但本身也有可能会有更好的方法吧。。。
7.练习1.29

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (xps f a b n)
  (define h
    (/ (- b a) n))
  (define (f1 k)
    (f (+ a (* k h))))
  (define (f2 k)
    (if (or (= k 0) (= k n))
	(f1 k)
	(if (even? k)
	    (* 2 (f1 k))
	    (* 4 (f1 k)))))
  (define (add-h x)
    (+ x 1))
  (* (/ h 3)
     (sum f2 0 add-h n)))

8.练习1.30

1
2
3
4
5
6
(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
	result
	(iter (next a) (+ (term a) result))))
  (iter a 0))

发表于   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2014/01/08/2014-01-08-练习1.18-练习1.22/

访问原文「练习1.18-练习1.22」

1.练习1.18

1
2
3
4
5
6
7
(define (*-iter a b n)
  (cond ((= n 0) a)
	((even? n) (*-iter a (double b) (halve n)))
	(else (*-iter (+ a b) b (- n 1)))))
(define (* b n)
  (*-iter 0 b n))

Lisp真是强大啊，连 *-iter这种函数名也可以使用！！！
2.练习1.19

1
p=p2+q2
1
q=q2+2pq

完整的函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(define (next-p p q)
  (+ (square p) (square q)))
(define (next-q p q)
  (+ (square q) (* 2 (* p q))))
(define (fib-iter a b p q count)
  (cond ((= 0 count) b)
	((even? count) (fib-iter a
				 b
				 (next-p p q)
				 (next-q p q)
				 (/ count 2)))
	(else (fib-iter (+ (* b q) (* a q) (* a p))
			(+ (* b p) (* a q))
			p
			q
			(- count 1)))))

3.练习1.20

应用序4次,第一次算,但是gcd( 2 0)不算,if判断后就直接返回a,下面不会执行;
正则序18次,
正则代换后,则第n层的a b两个参数对应的remainder的次数分别为a(n), b(n),
则: a(n) = b(n-1);b(n)=a(n-1)+b(n-1)+1;a(0)=0,b(0)=0
总共5层,由于每层的if判断进行了计算,再加上最后一层的a是计算了的,所以最后的结果是:b(0)+b(1)+b(2)+b(3)+b(4)+a(4)=18
按照我的理解：
这道题使用正则序展开的时候会先展开gcd，展开的函数中会有多个remiander函数；使用应用序展开时，会先计算remainder，然后才会展开gcd。
看了很多别人的答案，对于正则序的展开并不是很清楚，我一开始认为也是5次，后来发现不对，我现在的想法是，在if的时候求值，在其他地方正常展开。
4.练习1.21
199，1999，7
5.练习1.22
这道题中，我将(runtime)函数，改为(real-time-clock);
计算结果如下：
1000的时间消耗为1；
10000的时间消耗为2；
100000的时间消耗为3；
1000000的时间消耗为8；
10000000的时间消耗为24。
可一看到，在1000-100000之间的时间的增长阶小于根10，而从100000到10000000之间的时间增长阶与根10相似。