第1章 构造过程抽象

练习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）改进的误差为


其中，
为当前迭代过程中代入的估算值。
为根据这次估算值得到的下一个估算值。求解这两个量的变化量，该变化量为停止迭代的标志。

#lang planet neil/sicp

(define (sqrt-iter guess x)
  (if (good-enough guess x)
      guess
      (sqrt-iter (improve guess x) x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough guess x)
  (< (diff guess x) 0.01))

(define (diff guess x)                                   ;求解误差
  (abs (- 1 (/ (improve guess x) guess))))

(define (sqrt x)
  (sqrt-iter 1.0 x))

(sqrt 0.00009)

练习1.8
答：只修改了如下部分

(define (improve guess x)
  (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))

练习1.9

(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

上述过程有如下特征：
（1）计算过程中，先逐步展开，再收缩；
（2）构造了由一系列推迟进行的操作所形成的链条；
（3）展开过程中，b的值没有发生改变；
（4）存储空间随着a的值成线性增长。
由这四点分析，上述过程是线性递归过程。

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

上述过程有如下特征：
（1）计算过程中，用a和b这两个状态变量描述计算过程；
（2）存在一套规则（a减1，b加1）来描述计算过程从一个状态到另一个状态；
（3）状态变换过程中，a和b两个状态变量都发生变化；
（4）存在一个结束检测（a等于0），用来描述终止条件；
（5）所需的计算步骤与a成线性关系。
由这四点分析，上述过程是线性迭代过程

练习1.10

(A 1 10)
(A 0 (A 1 9))
(* 2 (A 0 (A 1 8)))
(* 2 (* 2 (A 0 (A 1 7))))
(* 2 (* 2 (* 2 (A 0 (A 1 6))))
...
(* 2 ... (* 2 (A 0 (A 1 1))...)
(* 2 ... (* 2 (A 0 2)...)
(* 2 ... (* 2 (* 2 2)...)
> 2^10

(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 (* 2 2)))
(A 1 (A 1 2^2))
(A 1 2^4)
2^(2^4)

(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
(A 2 (A 1 (A 2 1)))
(A 2 (A 1 2))
(A 2 (A 0 (A 1 1)))
(A 2 (A 0 2))
(A 2 4)
2^(2^4)

f = 2*n
g = 2^n
k = ((2^2)^2)...)^2       k个2的平方

练习1.11

递归

#lang planet neil/sicp

(define (fibb n)
  (cond ((<= n 0) 0)
        ((<= n 3) n)
        (else (+ (fibb (- n 1))
                 (* 2 (fibb (- n 2)))
                 (* 3 (fibb (- n 3)))))))

(fibb 7)

迭代

#lang planet neil/sicp

(define (fibb n)
  (fibb-iter 3 2 1 n))

(define (fibb-iter a b c count)
  (if (= count 3)
      a
      (fibb-iter  (+ a (* 2 b) (* 3 c)) a b (- count 1))))

(fibb 7)

练习1.13 想要证明

首先需要证明Fib(1)和Fib(2)满足这个公式。


假设Fib(n)和_Fib(n+1)满足该公式，即

以及

那么

因此，可以推断该公式成立。

练习1.14



显然，空间和步数增长的阶都是

练习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}

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,126评论 6赞 481
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,254评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 152,445评论 0赞 341
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,185评论 1赞 278
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,178评论 5赞 371
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,970评论 1赞 284
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,276评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,927评论 0赞 259
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,400评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,883评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,997评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,646评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,213评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,204评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,423评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,423评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,722评论 2赞 345

推荐阅读更多精彩内容

  • 1.1 程序设计的基本元素
    1.1.1 表达式 数 数是一种最基本的表达式 过程 过程（内置运算符或函数）是另一种基本表达式，例如： + - ...
    勤劳的悄悄阅读 655评论 0赞 0
  • 《SICP》｜ 第一章：构造过程的抽象
    软件工程大师能够组织好自己的程序，预先发现自己程序的行为方式，即使发生问题也能很快的排出错误，就像一部汽车一样，拥...
    唐鱼的学习探索阅读 1,310评论 0赞 2
  • “最喜欢的”。
    今天想说的话题其实不算新鲜，至少我就和朋友多次谈论过。关于你“最喜欢的”。 我们经常碰到这样的问题，可...
    Yeeancy_阅读 248评论 0赞 0
  • 思考者
    有人说，批判性思维不是渴求获得更多更全面的信息，而是在面对每一个信息的时候，愿意多走一步，不被情绪左右，考虑它的合...
    朱六子阅读 170评论 0赞 0
  • 2017年7月22日
    也许还是我不够成熟，一切按照自己的想法来，有时别人也是对的，我不应该进行反驳，迷信也是一种信仰，就像我去了金鸾...
    如此甚好18阅读 178评论 0赞 0