第1章 构造过程抽象
2016-08-14 本文已影响0人
VictorLiao
练习1.1
#lang planet neil/sicp
10
(+ 5 3 4)
(- 9 1)
(+ (* 2 4) (- 4 6))
(/ 6 2)
(define a 3)
(define b (+ a 1))
(+ a b (* a b))
(= a b)
(if (and (> b a) (< b (* a b)))
b
a)
(cond ((= a 4) 6)
((= b 4) (+ 6 7 a))
(else 25))
(+ 2 (if (> b a) b a))
(* (cond ((> a b) a)
((< a b) b)
(else -1))
(+ a 1))
练习1.2 将下面表达式变换为前缀形式
![][0]
#lang planet neil/sicp
(/ (+ 5 4
(- 2
(- 3
(+ 6
(/ 4 5)))))
(* 3
(- 6 2)
(- 2 7)))
练习1.3 请定义一个过程，它以三个数为参数，返回两个较大数之和。
#lang planet neil/sicp
(define (MaxNumSum x y z)
(cond ((>= x y)
(cond ((>= y z) (+ x y))
((< y z) (+ x z))))
((< x y)
(cond ((>= x z) (+ x y))
((< x z) (+ y z))))))
(MaxNumSum 3 2 2)
练习1.4 请仔细考察上面给出的允许运算符为复合表达式的组合式的求值模型，根据对这一模型的认识描述下面过程的行为：
#lang planet neil/sicp
(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))
(a-plus-abs-b 1 -2)
答：
- 首先定义了一个过程a-plus-abs-b，这个过程套用了if判断语句。
- if判断语句判断b是否大于0
- 若b大于0，执行a+b运算；
- 否则（若b小于等于0），执行a-b运算。
练习1.5 Ben Bitdiddle发明了一种检测方法，能够确定解释器究竟采用哪种序求解，是采用应用序，还是采用正则序。他定义了下面两个过程。
#lang planet neil/sicp
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
(test 0 (p))
答：由书中P10给出的定义，正则序采用“先展开后归约”的过程，而应用序则是先“先求值参数而后应用”的过程。
- 如果是正则序，则求解过程会是：
(test 0 (p)) #第一步
( if (= 0 0) 0 (p)) #第二步，展开test过程，并将(p)过程作为实际参数代入
( if (= 0 0) 0 (p)) #第三步，展开(p)过程，至此全部过程都已展开
(0) #第四步，判断为0，直接输出0，没有求解(p)过程，所以可以求解
- 如果是应用序，则求解过程会是：
(test 0 (p)) #第一步
(test 0 (p)) #第二步，展开(p)过程，并将(p)过程的结果代入test过程。由于(p)过程无法求解，因此求解过程到此结束。
练习1.6 Alyssa P. Hacker看不出为何需要使用将if提供为一种特殊形式，她问：“为什么我不能直接通过cond将它定义为一个常规过程呢？”Alyssa的朋友Eva Lu Ator断言确实可以这样做，并定义了if的一个版本：
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
Eva给Alyssa演示她的程序：
(new-if (= 2 3) 0 5)
> 5
(new-if (= 1 1) 0 5)
> 0
她很高兴地用自己的new-if重写了求平方根的程序：
(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
当Alyssa试着用这个过程去计算平方根时会发生什么事情呢？请给出解释。
答：当Alyssa试着用这个过程去计算平方根是会发生错误，错误原因是递归层数太多，超过了最大递归深度。
原代码使用if语句，现代码使用cond语句，其余代码没有发生变化。发生错误的原因是if和cond的区别。
(cond (<p1> <e1>)
(<p2> <e2>)
.
.
.
(<pn> <en>))
(if <predicate> <consequent> <alternative>)
-
cond
根据书上p11的解释，cond首先会求值谓词<p1>，如果它的值是false，那么就去求解<p2>。这一过程将继续做下去，直到发现某个谓词<pj>的值为真，此时解释器就返回相应子句中的序列表达式<e>的值，以这个值作为整个条件表达式的值。但是，cond会求值所有序列表达式<e1><e2>...<en>，最后返回相应 的序列表达式。（是否会求解全部的谓词呢？）
(new-if #t (display "good") (display "bad"))
> goodbad
-
if
解释器从求值<predicate>部分开始，如果<predicate>为真，则求解<consequent>，否则求解<alternative>。
(if #t (display "good") (display "bad"))
> good
练习1.7
答：
（1）对于很小的数，这个精度太大了，无法用来衡量准确度。对于很大的数，这个精度又太小了，也无法来衡量准确度。
（2）改进的误差为
显然，空间和步数增长的阶都是
练习1.15
（1）p总共被使用5次。
（2）a的数值每增加3倍，sine将会被多调用1次，空间和时间相应增加，因此空间和步数增长的阶是
练习1.16
#lang planet neil/sicp
(define (fast-expt b n)
(expt-iter 1 b n))
(define (expt-iter a product count)
(cond ((< count 0) (/ 1 (expt-iter a product (- 0 count))))
((= count 0) 1)
((= count 1) (* product a))
((even? count) (expt-iter a (* product product) (/ count 2)))
(else (expt-iter (* a product) (* product product) (/ (- count 1) 2)))))
(define (even? count)
(= (remainder count 2) 0))
(fast-expt 2 -3)
练习1.17
#lang planet neil/sicp
(define (fast-times a b)
(cond ((or (= b 0) (= a 0)) 0)
((< b 0) (- 0 (fast-times a (- 0 b))))
((even? b) (double (fast-times a (halve b))))
(else (+ a (fast-times a (- b 1))))))
(define (even? count)
(= (remainder count 2) 0))
(define (double num)
(+ num num))
(define (halve num)
(/ num 2))
(fast-times 2 -7)
练习1.18
#lang planet neil/sicp
(define (fast-times a b)
(times-iter 0 a b))
(define (times-iter rmd a count)
(cond ((< count 0) (- 0 (times-iter rmd a (- 0 count))))
((or (= count 0) (= a 0)) 0)
((= count 1) (+ a rmd))
((even? count) (times-iter rmd (double a) (halve count)))
(else (times-iter (+ rmd a) (double a) (halve (- count 1))))))
(define (even? count)
(= (remainder count 2) 0))
(define (double num)
(+ num num))
(define (halve num)
(/ num 2))
(fast-times 2 9)
练习1.19
题目给出了a 和b 之间的变化规律：
用矩阵形式可以表示为：
继续相乘，得到如下表达式：
为简化表达形式，做出如下表达假设：
因此，上述表达式可以简写如下：
显然，可以得到：
对于给定的 n，可以表示为如下形式
其中
此时表达式可以变换为：
![][23]
那么
****待续****
练习1.20
（1）正则序
(gcd 206 40)
(gcd 40 (remainder 206 40))
(if (= (remainder 206 40) 0))
(if (= 6 0))
(gcd 6 (remainder 40 6))
(if (= (remainder 40 6) 0))
(if (= 4 0))
(gcd 4 (remainder 6 4))
(if (= (remainder 6 4) 0))
(if(= 2 0))
(gcd 2 (remainder 4 2))
(if (= (remainder 4 2) 0))
(if (= 0 0))
2
正则序实际执行了4次remainder操作
（2）应用序
(gcd 206 40)
(gcd 40 (remainder 206 40))
(gcd 40 6)
(if (= 6 0))
(gcd 6 (remainder 40 6))
(gcd 6 4)
(if (= 4 0))
(gcd 4 (remainder 6 4))
(gcd 4 2)
(if (= 2 0))
(gcd 2 (remainder 4 2))
(gcd 2 0)
(if (= 0 0))
2
应用序同样执行了4次remainder操作
练习1.21
199最小公约数199
1999最小公约数1999
19999最小公约数7
练习1.22
#lang planet neil/sicp
(#%require (only racket/base current-inexact-milliseconds))
(define (smallest-prime num count)
(cond ((= count 0)
(display "over")
(newline))
((prime? num 2)
(time-prime-test num)
(smallest-prime (next-odd num) (- count 1)))
(else
(smallest-prime (next-odd num) count))))
(define (next-odd num)
(if (divides? 2 num)
(+ 1 num)
(+ 2 num)))
(define (prime? n test-divisor)
(cond ((> (* test-divisor test-divisor) n) True)
((divides? test-divisor n) False)
(else (prime? n (+ test-divisor 1)))))
(define (divides? a b)
(= (remainder b a) 0))
(define (time-prime-test n)
(display n)
(newline)
(prime-test n (current-inexact-milliseconds)))
(define (prime-test n start-time)
(if (prime? n 2)
(report-prime (- (current-inexact-milliseconds) start-time))))
(define (report-prime elapsed-time)
(display elapsed-time)
(newline)
(display "***")
(newline))
(smallest-prime 100000000000 3)
(smallest-prime 1000000000000 3)
(smallest-prime 10000000000000 3)
输出结果如下所示：
100000000003
46.800048828125
***
100000000019
46.800048828125
***
100000000057
46.800048828125
***
over
1000000000039
140.400390625
***
1000000000061
140.400390625
***
1000000000063
156.000244140625
***
over
10000000000037
592.80126953125
***
10000000000051
436.801025390625
***
10000000000099
421.20068359375
***
over
由于DrRacket的时间函数精确到毫秒，为得到比较精确地时间，特地选择较大的数值，得到的平均时间大致为46.8，145.6，483.6。理论上，三者应该以3.16的倍数增长，但实际增长倍数并不是如此。可以理解为由于内存和CPU的限制，得到的结果时间不一定负荷理论值。而且随着数值的增大，也在增加运行时间。
练习1.23
#lang planet neil/sicp
(#%require (only racket/base current-inexact-milliseconds))
(define (runtime) (current-inexact-milliseconds))
(define (smallest-prime num count)
(cond ((= count 0)
(display "over")
(newline))
((prime? num 2)
(time-prime-test num)
(smallest-prime (next-odd num) (- count 1)))
(else
(smallest-prime (next-odd num) count))))
(define (next-odd num)
(if (divides? 2 num)
(+ 1 num)
(+ 2 num)))
(define (prime? n test-divisor)
(cond ((> (* test-divisor test-divisor) n) True)
((divides? test-divisor n) False)
(else (prime? n (next-divisor test-divisor)))))
(define (next-divisor test-divisor)
(if (= test-divisor 2)
3
(+ test-divisor 2)))
(define (divides? a b)
(= (remainder b a) 0))
(define (time-prime-test n)
(display n)
(newline)
(prime-test n (current-inexact-milliseconds)))
(define (prime-test n start-time)
(if (prime? n 2)
(report-prime (- (current-inexact-milliseconds) start-time))))
(define (report-prime elapsed-time)
(display elapsed-time)
(newline)
(display "***")
(newline))
(smallest-prime 100000000000 3)
(smallest-prime 1000000000000 3)
(smallest-prime 10000000000000 3)
得到的结果如下所示：
100000000003
31.199951171875
***
100000000019
31.199951171875
***
100000000057
31.199951171875
***
over
1000000000039
93.600341796875
***
1000000000061
139.801025390625
***
1000000000063
93.60009765625
***
over
10000000000037
344.213623046875
***
10000000000051
346.02001953125
***
10000000000099
335.01904296875
***
over
得到的平均时间大概为：31.2，109，341.8。对比1.22的时间46.8，145.6，483.6。有明显的减少，但没有减少一半。
练习1.24
#lang planet neil/sicp
(#%require (only racket/base current-inexact-milliseconds random))
(#%require (only racket/math sqr))
(define (smallest-prime num count)
(cond ((= count 0)
(display "over")
(newline))
((fast-prime? num 20)
(time-prime-test num)
(smallest-prime (next-odd num) (- count 1)))
(else
(smallest-prime (next-odd num) count))))
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (sqr (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
(define (next-odd num)
(if (divides? 2 num)
(+ 1 num)
(+ 2 num)))
(define (divides? a b)
(= (remainder b a) 0))
(define (time-prime-test n)
(display n)
(newline)
(prime-test n (current-inexact-milliseconds)))
(define (prime-test n start-time)
(if (fast-prime? n 20)
(report-prime (- (current-inexact-milliseconds) start-time))))
(define (report-prime elapsed-time)
(display elapsed-time)
(newline)
(display "***")
(newline))
(smallest-prime 100 3)
(smallest-prime 1000 3)
(smallest-prime 10000000 3)
由于DrRacket的时间函数至多精确到毫秒，而且由于random函数应用范围有限，不能取太大的数值，所以无法得到每次计算的精确时间。但是，1.22和1.23的时间都与理论不符合，可以理解为由于内存和CPU受限，不可能得到理论精确地时间，但是可以大致估算。
练习1.25
两段代码进行对比
(1) 原来求幂的方法
#lang planet neil/sicp
(#%require (only racket/base random))
(#%require (only racket/math sqr))
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (sqr (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
(expmod 8 10 10)
(2) Alyssa P. Hacker提出的方法
#lang planet neil/sicp
(#%require (only racket/base random))
(#%require (only racket/math sqr))
(define (expmod base exp m)
(remainder (fast-expt base exp) m))
(define (fast-expt base exp)
(cond ((= exp 0) 1)
((even? exp)
(sqr (fast-expt base (/ exp 2))))
(else
(* base (fast-expt base (- exp 1))))))
(expmod 8 10 10)
对于第一个代码，执行的过程如下所示：
(expmod 8 10 10)
(expmod 8 5 10)
(expmod 8 4 10)
(expmod 8 2 10)
(expmod 8 1 10)
(expmod 8 0 10) ;到此为止递归到0，开始代入计算
1 ;exp等于0时，expmod输出1
8 ;执行 remainder(8*1, 10)，得到结果8
4 ;执行 remainder(8*8, 10)，得到结果4
6 ;执行 remainder(4*4, 10)，得到结果6
8 ;执行 remainder(8*6, 10)，得到结果8
4 ;执行 remainder(8*8, 10)，得到结果4
每一步计算都得到余数，计算的数值没有扩大。
对于第二段代码，执行过程如下所示：
(expmod 8 10 10)
(remainder (fast-expt 8 10) 10))
(fast-expt 8 10)
(fast-expt 8 5)
(fast-expt 8 4)
(fast-expt 8 2)
(fast-expt 8 1)
(fast-expt 8 0) ;到此为止递归到0，开始代入计算
1 ;exp等于0时，fast-expt输出1
8 ;执行8*1，得到结果8
64 ;执行8*8，得到结果64
4096 ;执行64*64，得到结果4096
32768 ;执行8*4096，得到结果32768
1073741824 ;执行32768*32768，得到结果1073741824
4 ;执行 (remainder 1073741824 10))，得到结果4
4 ;输出(expmod 8 10 10)结果4
第二段代码不断将结果放大，一方面扩大了内存，放大了数值，另一方面增加了运行时间。当起始数就很大时，会导致溢出。
通过对比可以得到结论：第一段代码效率高，第二段代码数值不断放大，既增加了运行时间，又可能导致数据溢出。
练习1.26
Louis没有使用square，而是将两个过程相乘，相当于多进行了2^n倍递归，因此计算复杂度从log n变为n
练习1.27
#lang planet neil/sicp
(#%require (only racket/math sqr))
(define (carmichael-test n)
(if (= (expmod n 100000007 100000007) n)
(display "Not Carmichael Num")
(display "Carmichael Num")))
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (sqr (expmod base (/ exp 2) m))
m))
(else
(remainder (sqr (expmod base (- exp 1) m))
m))))
(define (even? n)
(= 0 (remainder n 2)))
(define (next-even n)
(if (even? n)
(+ n 2)
(+ n 1)))
练习1.28
#lang planet neil/sicp
(#%require (only racket/math sqr))
(#%require (only racket/base random))
(define (fast-prime? n times)
(cond ((= times 0) (display "Prime"))
((fermat-test n) (fast-prime? n (- times 1)))
(else (display "Not Prime"))))
(define (fermat-test n)
(define (try-it a)
(= (expmod a (- n 1) n) 1))
(try-it (random 2 (- n 1))))
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (sqr (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
练习29
题中给出的辛普森公式为：
可以将该公式修改如下：
因此，公式中存在两个递归过程，分别是：
如下给出了给题的代码实现：
#lang planet neil/sicp
(define (simpson f a b n)
(define deltah (delta a b n))
(define delta2h (delta a b (/ n 2)))
(define (simpson-next x) (+ x delta2h))
(* (+ (f a)
(f b)
(* (sum f (+ a deltah) simpson-next (- b deltah)) 4)
(* (sum f (+ a delta2h) simpson-next (- b delta2h)) 2))
(/ deltah 3)))
(define (delta a b n)
(/ (- b a) n))
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
(define (even? x)
(= (remainder x 2) 0))
(define (cube x) (* x x x))
练习1.30
迭代的过程就是一个累加的过程
(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ (term a) result))))
(iter a 0))
练习1.31
详见《举例分析迭代及递归的复杂度（scheme代码实现）》
练习1.32
(define (accumulte combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a) (accumulte combiner null-value term (next a) next b))))
; add process
(define (add term a next b)
(define (add-combiner x y) (+ x y))
(accumulte add-combiner 0 term a next b))
; product process
(define (product term a next b)
(define (product-combiner x y) (* x y))
(accumulte product-combiner 1 term a next b))
练习1.33
filtered-accumulate就是在上题的基础上加了一个筛选，能够满足筛选的数值就进行组合。
递归形式的filtered-accumulate
#lang planet neil/sicp
(define (filtered-accumulate filter combiner null-value term a next b)
(cond ((> a b) null-value)
((filter a) (combiner (term a) (filtered-accumulate filter combiner null-value term (next a) next b)))
(else (filtered-accumulate filter combiner null-value term (next a) next b))))
; add process
(define (add filter term a next b)
(define (add-combiner x y) (+ x y))
(filtered-accumulate filter add-combiner 0 term a next b))
; product process
(define (product filter term a next b)
(define (product-combiner x y) (* x y))
(filtered-accumulate filter product-combiner 1 term a next b))
迭代形式的filtered-accumulate
(define (filtered-accumulate filter combiner null-value term a next b)
(cond ((> a b) null-value)
((filter a) (filtered-accumulate filter combiner (combiner null-value (term a)) term (next a) next b))
(else (filtered-accumulate filter combiner null-value term (next a) next b))))
; add process
(define (add term a next b)
(define (add-combiner x y) (+ x y))
(filtered-accumulate add-combiner 0 term a next b))
; product process
(define (product filter term a next b)
(define (product-combiner x y) (* x y))
(filtered-accumulate filter product-combiner 1 term a next b))
a)素数相加
#lang planet neil/sicp
(#%require (only racket/math sqr))
(define (prime-num-add a b)
(define (next x) (+ x 1))
(define (term x) x)
(add term a next b))
;;;;;;;;;;;;prime;;;;;;;;;;;;;;;;;;;;
(define (prime? n)
(= n (smallest-divisor n)))
(define (smallest-divisor n)
(find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (sqr test-divisor) n) n)
((divides? n test-divisor) test-divisor)
(else (find-divisor n (+ 1 test-divisor)))))
(define (divides? a b)
(= (remainder a b) 0))
;;;;;;;;;;;add process;;;;;;;;;;;;;;;;
(define (add term a next b)
(define (add-combiner x y) (+ x y))
(filtered-accumulate prime? add-combiner 0 term a next b))
(define (filtered-accumulate filter combiner null-value term a next b)
(cond ((> a b) null-value)
((filter a) (filtered-accumulate filter combiner (combiner null-value (term a)) term (next a) next b))
(else (filtered-accumulate filter combiner null-value term (next a) next b))))
b)互素整数的相乘
#lang planet neil/sicp
(define (n-prime-product n)
(define (next x) (+ 1 x))
(define (term x) x)
(product n-prime? term 1 next n))
;;;;;;;;;;;;;;n-prime?;;;;;;;;;;;;;;;;;;
(define (n-prime? a n)
(if (= (gcd n a) 1)
True
False))
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
;;;;;;;;;;;;product process;;;;;;;;;;;;;;;
(define (product filter term a next b)
(define (product-combiner x y) (* x y))
(filtered-accumulate filter product-combiner 1 term a next b))
(define (filtered-accumulate filter combiner null-value term a next b)
(cond ((> a b) null-value)
((filter a b) (filtered-accumulate filter combiner (combiner null-value (term a)) term (next a) next b))
(else (filtered-accumulate filter combiner null-value term (next a) next b))))
练习1.34
下面是(f f)的计算过程
(f f)
(f 2)
由于2不是一个过程，所以会报错。
1.35
#lang planet neil/sicp
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) 0.00001))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1)
1.36
#lang planet neil/sicp
(#%require (only racket/base log))
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) 0.00001))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(fixed-point (lambda (x) (/ (log 1000) (log x))) 2)
1.37
迭代运算和递归运算都放在下面的程序里边，frac-iter是迭代运算，cont-frac是递归运算。
#lang planet neil/sicp
;;;;;;;;;;;;;;;;;;calculate the real num;;;;;;;;;;;;;;;;;;;;;;;;;
(#%require (only racket/base abs))
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) 0.00001))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(define real-num (/ 1 (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1)))
;;;;;;;;;;;;;;;;;;;;;;frac-iter;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (frac-iter k result)
(if (< (abs (- real-num result)) 0.001)
k
(frac-iter (+ 1 k) (/ 1 (+ 1 result)))))
;(frac-iter 1 1)
;;;;;;;;;;;;;;;;;;;;;;frac-res;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (cont-frac n d k)
(if (< (abs (- (frac-res n d k) real-num)) 0.001)
k
(cont-frac n d (+ k 1))))
(define (frac-res n d k)
(if (= k 1)
(/ n d)
(/ n (+ d (frac-res n d (- k 1))))))
这道题目更适合使用迭代运算，因为该题中迭代/递归次数是变量，求得误差小于0.001时的迭代次数。递归需要先展开再计算，所以递归需要给定递归次数。而迭代每次都会直接计算，所以迭代可以直接求解误差，当误差小于0.001时停止迭代，输出此时的迭代次数。
[0]: http://latex.codecogs.com/svg.latex?\frac{5+4+(2-(3-(6+\frac{4}{5})))}{3(6-2)(2-7)}
[23]: http://latex.codecogs.com/svg.latex?I_{n}=((A{2}){2}...){2}A{t}I_{0}=A_{n}I_{0}
