过程与它们所产生的计算

  1. 理解如何编程：
    1. 编程领域中各种有用的常见模式；
    2. 哪些过程值得定义；
    3. 对执行一个过程的效果做出预期：
      1. 学会去看清各种不同种类的过程会产生什么样的计算过程。
  2. 一个过程也就是一种模式，它描述了一个计算过程的局部演化方式，描述了这一计算 过程中的每个步骤是怎样基于前面的步骤建立起来的。

线性的递归和迭代

  1. 递归计算过程（本节中是线性递归过程）
    1. 执行时，这样的计算过程构造起一个推迟进行的操作所形成的链条，链条的长度 也就是为保存其轨迹解释器需要保存的信息量，长度是线性增长的；当链条达到 最大时，收缩阶段开始并表现为这些运算的实际执行；
    2. 这种类型的计算过程由此运算链条所刻画；
    3. 计算步骤线性增长，存储空间线性增长；
    4. 解释器维持着程序变量之外的与计算状态相关的一些隐含信息。
  2. 迭代计算过程（本节中是线性迭代过程）
    1. 没有任何增长或收缩，其计算过程就是那种其状态可以用固定数目的状态变量描 述的计算过程；
    2. 存在这一套固定的法则描述了计算过程从一个状态到下一个状态转换时这些变量 的更新方式（可能还有一个结束检测）；
    3. 计算步骤线性增长，存储空间是常量；
    4. 状态变量提供了计算状态的完整描述。
  3. 递归过程：语法形式；递归计算过程：计算过程的进展方式；
  4. 尾递归：在常量空间种执行迭代型计算过程，即使这一计算是用一个递归过程描述的。

练习 1.9-1.10

1.9

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

;; 第一个是递归计算过程；第二个是迭代计算过程。
;; 使用代换模形，第一个过程：
;; (+ 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
;; 使用代换模形，第二个过程：
;; (+ 4 5)
;; (+ 3 6)
;; (+ 2 7)
;; (+ 1 8)
;; (+ 0 9)
;; 9

1.10

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

(A 1 10)				;1024
(A 2 4)					;65536
(A 3 3)					;65536

(define (f n)
  (A 0 n))				;(* 2 n)

(define (g n)
  (A 1 n))				;(if (= n 0) 0 (expt 2 n))

(define (h n)
  (A 2 n))				;(cond ((= n 0) 0) ((= n 1) 2) (else (expt 2 (expt 2 (expt 2  (- n 2))))))

树形递归

  1. 树形递归的计算步骤增长相对于线性增长来说要快的多，可能极其低效；
  2. 但并不是说树形递归就是没有用的：
    1. 树形递归更容易描述和理解；
    2. 当在层次结构性的数据上操作而不是对数操作时，它是一种自然的威力强大的工 具；
    3. 即使是对于数的计算，树形递归也是具有启发意义的，可以帮助我们理解和设计 程序；

练习 1.11-1.13

1.11

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

(define (func-re n)
  (if (< n 3)
      n
      (+ (func-re (- n 1)) (* 2 (func-re (- n 2))) (* 3 (func-re (- n 3))))))

(define (func-it n)
  (func-iter 2 1 0 0 n))

(define (func-iter a b c i n)
  (if (= i n)
      c
      (func-iter (+ a (* 2 b) (*3 c))
		 a
		 b
		 (+ i 1)
		 n)))

1.12

1
2
3
4
5

(define (pascal-re row col)
  (cond ((> col row) (error "invalid col value"))
	((or (= col 0) ( = row col)) 1)
	(else (+ (pascal-re (- row 1) (- col 1))
		 (pascal-re (- row 1) col)))))

1.13

1

;; 证明跳过

增长的阶

  1. 增长的阶为我们提供了对计算过程行为的一种很粗略的描述；
  2. 增长的阶也为我们在问题规模改变时，预期一个计算过程的行为变化（比如占用资 源）提供了有用的线索。

练习 1.14-1.15

1.14

1
2
3

;; 不画图
;; 空间增长的阶应该是 theta(n)
;; 步数增长的阶不明确，网上的资料各方面也有不同的意见

1.15

1
2

;; a) p 将被调用 5 次
;; b) 空间增长的阶：theta(log a); 步数增长的阶：theta(log a)

求幂

  1. 使用求幂的例子引出增长的阶为对数增长，而不是线性增长的递归计算过程，是对 增长的阶的继续深入和补充。

练习 1.16-1.19

1.16

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

;; 定义一个不变量，要求它在状态之间保持不变，这一技术是思考迭代算法设计问题时的
;; 一种非常强有力的方法
(define (even? n)
  (= (remainder n 2) 0))

(define (fast-expt-it b n a)
  (cond ((= n 0) a)
	((even? n) (fast-expt-it b (/ n 2) (* a (* b b))))
	(else (* b (fast-expt-it b (/ (- n 1) 2) (* a (* b b)))))))

(define (fast-expt b n)
  (fast-expt-it b n 1))

1.17

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

(define (double x)
  (+ x x))

(define (halve x)
  (if (=  (remainder x 2) 0)
      (/ x 2)
      (error "Invalid number")))

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

(define (* x y)
  (cond ((or (= y 0) (= x 0)) 0)
	((= y 1) x)
	((even? y) (* (double x) (/ y 2)))
	(else (+ x (* x (- y 1))))))

1.18

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

(define (double x)
  (+ x x))

(define (halve x)
  (if (=  (remainder x 2) 0)
      (/ x 2)
      (error "Invalid number")))

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

(define (multi-iter x y)
  (cond ((or (= x 0) (= y 0)) 0)
	((= y 1) x)
	((even? y) (multi-iter (double x) (/ y 2)))
	(else (+ x (multi-iter x (- y 1))))))

(define (* x y)
  (multi-iter x y))

1.19

1

;; 证明跳过

最大公约数

  1. 求最大公约数的欧几里得算法及实现，计算步骤对数增长。

练习 1.20

1.20

1
2
3
4

;; 正则序
;; <predicate> 部分 10 次，<alternative> 部分 4 + 4 = 8次，一共18次；
;; 应用序
;; 一共4次

实例：素数检测

  1. 费马检查做素数检测的代码实现是一种概率方法。

练习 1.21-1.28

1.21

1
2
3

;; 199
;; 1999
;; 7

1.22

1
2
3

;; (search-for-primes 1000)....1000 10000 10000 太小了, 打印出来的时间消耗几乎为0。
;; (search-for-primes 1e10) 时间消耗大概是 1e9 的3倍， 差不多是 (sqrt 10)。
;; 所以可以推断出程序在机器上的运行时间正比于计算所需的步数，是线性增长的。

1.23

 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 (next n)
  (if (= n 2)
      (+ n 1)
      (+ n 2)))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
	((divides? test-divisor n) test-divisor)
	(else (find-divisor n (next test-divisor)))))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

;; timed-prime-test 和书上一致

;; 修改之前的运算时间大概是修改之后的1.5倍，而不是2倍，
;; 为什么?
;; 官方回答: 主要是 因为 next 过程里的 if 检测：修改之后确实使检查步数减少一半，
;; 但却要多额外处理 next 过程中的 if 检测。

1.24

1
2

;; 改动就是将 prime? 过程的调用换成 fast-prime? 的的调用；
;; 对 1e24 的计算时间占用大概是 1e12 的2倍，符合预期。

1.25

1
2

;; 直接使用 fast-expt 当然可以计算出一样的结果，但是它会产生大量的中间数据使计算
;; 过程效率降低。

1.26

1
2
3

;; 调用 square 过程时只需要对它的一个参数求值；
;; 不使用 square 过程而是直接用显示乘法的话，乘法运算符的两个运算对象都需要求值；
;; 使一个增长的阶为对数的计算过程变成线性的了。

1.27

1
2
3
4
5
6
7
8
9

(define (full-fermat-test n)
  (define (iter-test n a)
    (if (< a n)
	(if (not  (= (expmod a n n) a))
	    (display "False")
	    (iter-test n (+ a 1)))
	(display "True")))
  (iter-test n 2))
  ;; 用 Carmichael 数调用该过程检查输出就可以了。

1.28

1
2

;; 不知道是不是中文翻译的问题，题目很难完全理解；
;; 实现的过程并不保证正确，需要参考的请去个人 github 主页查看源码。