SICP
过程与它们所产生的计算
1.1节描述了程序设计的基本元素并聚焦在过程上，因此1.2就开始讨论过程与他们所产生的计算。这一节主要有两个主题：一是考察计算过程的“形状”；二是研究过程消耗的计算资源速率。
通常，我们定义一个过程是为了在某种场景下可重复地计算一系列值，用书中的话说叫做“描述了一个计算过程的局部演化方式”，而所谓的局部演化就是指计算过程中的每一步都是基于前面的步骤建立的，经典例子就是阶乘n! = n * (n - 1) * (n - 2) ...3 * 2 * 1的计算，在我上学的时候，课上就讲过用递归和迭代两种方式实现，递归实现如下，利用代换模型展开后可以发现它的计算过程所呈现的形状是先展开再收缩，这是递归计算过程所特有的形状。
(define (factorial-recu n)
(if (= n 1)
1
(* n (factorial-recu (- n 1)))))
(factorial-recu 5)
(* 5 (factorial-recu 4))
(* 5 (* 4 (factorial-recu 3)))
(* 5 (* 4 (* 3 (factorial-recu 2))))
(* 5 (* 4 (* 3 (* 2 (factorial-recu 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (* 3 2)))
(* 5 (* 4 6))
(* 5 24)
120
再来看运用迭代方式实现的阶乘计算，所谓迭代方式就是通过循环（如下）实现，观察循环可以发现这个过程中有两个因素起了作用，一个是i，它扮演了控制步进的角色，即i ← i + 1；另一个是res，它扮演了控制器结果的作用res ← res * (i + 1)，而要驱动这个循环生效只需要给定上述因素初始值，也就是书中所说的“状态可由固定数目的状态变量描述，并且描述了状态变化时，变量的更新方式”。
def factorial(n):
res = 1
for i in range(n):
res = res * (i + 1)
return res
按照这个结论，我们可以得到下面的过程定义并利用代换模型展开，对比上面递归计算过程形状可以发现迭代方式并没有呈现出先收缩再展开并且计算次数与输入参数n成正比。
(define (factorial n)
(define (factorial-iter i result)
(if (> i n)
result
(factorial-iter (+ i 1) (* i result))))
(factorial-iter 1 1))
(factorial 5)
(factorial (+ 1 1) (* 1 1))
(factorial (+ 2 1) (* 2 1))
(factorial (+ 3 1) (* 3 2))
(factorial (+ 4 1) (* 4 6))
(factorial (+ 5 1) (* 5 24))
120
按照“自己调用自己”的递归通俗化定义，观察这一过程不难发现这个所谓的迭代实质上也是一种递归，完全不同于我们遇到高级语言中各种循环结构（如do...while，for等），造成这种差异的原因是高级语言中的“实现设计对于递归过程的解释，所需消耗的存储量总与过程调用数目成正比，即使它的计算过程的原理是迭代的，导致这些语言描述迭代过程必须借助特殊的‘循环结构’”。所以我们所说的”自己调用自己“的递归定义实际上描述的是语法形式，而不是计算过程的进展方式（或者可以简单地理解为形状），识别的关键在于是否存在变量存储状态的变化，存在变量存储即为迭代计算过程，而不存在变量完全依赖解释器则是递归计算过程，可见即使是同一求值问题的不同的计算过程实现对解释器而言是不同的，从这个意义上我们有必要探讨计算效率与资源，Fibonacci就是一个极佳的例子。
观察Fibonacci数列的树形递归计算可以发现整个过程存在不少重复计算，比如fib(0)和fib(1)，其计算步骤随着输入增长而指数性地增长（练习1.13证明），而在空间上却是线性增长。参考上面的迭代计算过程，也可以通过一个变换规则来描述：设fib(n)为a、fib(n - 1)为b，则根据Fibonacci的定义可以得到a ← a + b，b ← a，而其驱动的初始值就是fib(1) = 1、fib(0) = 0。
(define (fib-iter a b n)
(if (= n 0)
b
(fib-iter (+ a b) a (- n 1))))
从这个计算过程不难看出，计算步骤是随着n线性变化的而空间则是固定的，这只是实现过程本身带来的计算消耗的变化，而从这里往后的几个小节将讨论不同算法（同一计算过程）对计算消耗资源的影响，为了清楚讨论需要引入增长阶的概念R(n) = θ(f(n))用来表示计算资源消耗速率（注意：θ(f(n))的含义是用一个f(n)来描述计算增长的变化情况），显然前面讨论递归计算过程中阶乘的计算步骤与空间需求增长阶显然是θ(n)，而迭代计算过程中的阶乘计算步骤则是θ(n)，空间需求增长阶为θ(1)，同理可得Fibonacci的树型递归计算步骤增长阶是θ(φn)空间需求增长阶是θ(n)。增长阶提供了粗略描述计算过程在资源需求上的差异，这在帮助我们选择合适的算法时是很有意义的。
考察求幂问题bn = b * b(n-1)，b0 = 1，这种计算方式可以进一步优化为bn = (bn/2)2，即先计算b的n/2次方后再计算平方，再结合奇偶数的差异，可以得到如下过程。
(define (even? n)
(= (remainder n 2) 0))
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
从过程上我们可以观察一个显著的变化，即计算b2n时只比bn多了一步，在数学上计算指数n所需要的乘法次数的增长大约就是以2为底n的对数值，所以其增长阶可记作θ(㏒ n)，对比之前的计算过程就能发现即使在相同的计算过程中，不同的算法会对计算资源消耗产生明显的影响，这也是算法会成为很多领域追寻的关键原因。
后面最大公约数和素数检测的介绍非常有意思，读书的时候数学不是我的强项，但通过这两个内容的介绍却感受到算法为计算机求解带来的质的变化，描述一个数学概念相对容易，但转换为一种具体的算法却复杂了很多，数学中的奥妙太多了！！！
如何判断素数？在我以前的知识体系中知道素数是指一个数除了1和本身外不能被其他自然数整除，也就是说我可能要计算n次才能知道n是不是素数，后来知道不需要计算到n，只要考察1到√n就可以了，所以最直接的计算过程如下，那么这个计算过程的增长阶明显就是θ(√n)。
(define (smallest-divisor n)
(find-divisor n 2))
(define (divide? a b)
(= (remainder b a) 0))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divide? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (prime? n)
(= n (smallest-divisor n)))
除了上面这种直接的计算过程，书中介绍了费马小定理来求解素数，即利用an/n = a/n = a来判断n是否为素数，这里的a是小于n的随机正整数，前面提到过求幂的优化是an = (an/2)2，所以得到an模n的计算过程（与书中过程不同但比较直接，书中不使用这种方式的原因见习题1.25），显然采用这种方式的增长阶是θ(㏒ n)。
(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 (expmod a exp m)
(remainder (fast-expt a exp) m))
引用费马定理解决素数判断的问题过程中，由于我们通过随机数的方式进行采样所以存在概率问题，当我们拥有更多的样本时我们对最终结果的判断一定是更加准确的，这也从另一个方面说明了概率算法的价值。
练习
1.9 此题是对1.2.1节知识的实践，另外注意对代换模型的运用，求解过程如下：
过程1
(+ 4 5)
(inc (+ (dec 4) 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9
过程2
(+ 4 5)
(+ (dec 4) (inc 5))
(+ (dec 3) (inc 6))
(+ (dec 2) (inc 7))
(+ (dec 1) (inc 8))
9
从上述构成执行的形状看，过程1是递归而过程2是迭代
1.10 此题可以用代换模型展开分析计算过程，将(A 1 10)展开后可以观察到其计算过程是计算2的10次方，因此(A 1 n)的结果是2的n次方
(A 1 10)
(A 0 (A 1 9)
(A 0 (A 0 (A 1 8)))
(A 0 (A 0 (A 0 (A 1 7))))
(A 0 (A 0 (A 0 (A 0 (A 1 6)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
(A 0 (A 0 (A 0 (A 0 (A 0 32)))))
(A 0 (A 0 (A 0 (A 0 64))))
(A 0 (A 0 (A 0 128)))
(A 0 (A 0 256))
(A 0 512)
1024
再来考察(A 2 4)，它展开后为(A 1 (A 2 3))可以复用上面的(A 1 n)是计算2的n次方的结论，即要计算2的(A 2 3)次方 ，继续展开如下。可以推论得到(A 2 n)的数学表达式是2的n-1次二次幂，即(A 2 4)等于2 ^ (2 ^ (2 ^ 2))。
(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 4))
(A 1 16)
65536
以此类推(A 3 3)可以得到如下：
(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
(A 2 4)
65536
1.11 考察的是1.2.2节有关递归和迭代实现，其中递归方式比较简单，按照题目描述就能得到：
(define (f n)
(if (< n 3)
n
(+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))
对于迭代方式，我们可以看到f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)，所以要得到f(n)需要三个输入，套用fib的变换规则可以得到a ← a + 2b + 3c, b ← a, c ← b，因此迭代方式实现的过程如下：
(define (f-iter a b c n)
(if (= n 2)
a
(f-iter (+ a (* 2 b) (* 3 c)) a b (- n 1))))
1.12 帕斯卡三角（也叫杨辉三角）是一个很经典的题，初学编程的时候肯定会遇到这个题目。在这里实际上还是考察对于迭代中变换规则的提炼，从题中可知边界上的数都是1，而内部的数都是上面两个数之和。我们可以定义一个过程叫pascal-triangle-iter，以行（row）、列（col）为入参，它有如下规则col=0输出1，col=row输出1，否则p(row, col) = p(row - 1, col -1) + p(row - 1, col)，直接实现如下所示，但这是一个递归过程。
(define (pascal row column)
(if (or (= column 0)(= column row))
1
(+ (pascal (- row 1) (- column 1))
(pascal (- row 1) column))))
基于上面的变换规则很难实现迭代版本，不过可以根据网上的帕斯卡三角资料找到另一种计算方法即row! / (col! * (row - col)!)，这样就是通过迭代方式实现阶乘，实现如下：
(define (factorial n)
(define (factorial-iter i result)
(if (> i n)
result
(factorial-iter (+ i 1) (* i result))))
(factorial-iter 1 1))
(define (pascal-iter row column)
(/ (factorial row) (* (factorial column) (factorial (- row column)))))
1.16 此题的作用不在于练习求幂而是掌握其提示的方法，按照提示存在a使得从一个状态转移至另一状态的a*bn不变，令a = 1并在计算完成时将a作为结果。实际上利用bn = (b2)n/2 = (bn/2)2进行演化，我们可以设一个过程(f b n a) = (f b2 n/2 a)，而当n为奇数时n ← n - 1，a ← a * b。
(define (expt b n)
(cond ((= n 0) 1)
((even? n) (expt (square b) (/ n 2)))
(else (* b (expt b (- n 1))))))
(define (expt-iter b n a)
(cond ((= n 0) a)
((even? n) (expt-iter (square b) (/ n 2) a))
(else (expt-iter b (- n 1) (* b a)))))
1.17 此题是对求幂过程fast-expt的演化，运用一个最早学习乘法的方法，即乘法可看作是连续加法，显然a * b = 2a * (b/2)，再结合fast-expt的范例可以得到
(define (multi a b)
(cond ((= b 0) 0)
((even? b) (multi (double a) (halve b)))
(else (+ a (multi a (- b 1))))))
1.18 此题实际是将1.17运用迭代进行实现，实现的方法与1.16相同如下，与1.16唯一的区别是result这里不能取1而是0
(define (multi a b result)
(cond ((= b 0) result)
((even? b) (multi (double a) (halve b) result))
(else (multi a (- b 1) (+ result a)))))
1.19 先完成p'和q'的计算，按照a←bq + aq + ap、b←bp + aq规则对(a, b)进行两次变换如下：
a←bq + a(p + q)
b←bp + aq
a←(bp + aq)q + (bq + a(p + q))(p + q) = bpq + aqq + bpq + bqq + app + 2apq + aqq
b←(bp + aq)p + (bq + a(p + q))q=bpp + apq + bqq + apq + aqq
a←b(2pq + qq) + a(qq + pp + qq + 2pq)
b←b(pp+qq) + a(2pq + qq)
可以得到p' = q2 + 2pq, q' = p2 + q2，这即是p和q的变换规则
1.20 此题还是考察应用、正则序理解，但请注意对if的描述。当采用应用序展开时：
(gcd 206 40)
(gcd 40 (r 206 40))
(gcd 6 (r 40 6))
(gcd 4 (r 6 4))
(gcd 2 (r 4 2))
2
而当采用应用序时如下所示，相比起来数量非常之多
(gcd 206 40)
(gcd 40 (r 206 40))
(gcd (r 206 40) (r 40 (r 206 40)))
(gcd (r 40 (r 206 40)) (r (r 206 40) (r 40 (r 206 40))))
(gcd (r (r 206 40) (r 40 (r 206 40))) (r (r 40 (r 206 40)) (r (r 206 40) (r 40 (r 206 40)))))
1.22 此题初看内容很多但实际上可以进行分解，首先看要求找出大于1000、大于10000和大于1000000的三个最小素数，实际上由于偶数都能被2整除，所以偶数就被排除了，所以范围可以缩小到奇数；其次最小素数是指按从小到达顺序找到的前三个素数，所以挨个取奇数检验即可；最后结合1.2.6的素数检查过程，可以得到如下。
(define (next-odd n)
(if (even? n)
(+ n 1)
(+ n 2)))
(define (find-prime from count)
(cond ((= count 0) (display "find all"))
((prime? from)
(display from)
(newline)
(find-prime (next-odd from) (- count 1)))
(else (find-prime (next-odd from) count))))
1.25 此题建议将1.2.5知识点再学习一下可以从中找到影子，这是两种不同的计算方式，fast-expt是计算幂值后再取模，而expmod则是通过计算模，每次计算的值都不会太大，有些类似GCD过程。采用fast-expt在理论上没问题而且有容易理解的优点，但问题出在我们要检测的素数是一个什么样的数，当这个数非常非常大时，那么我们取到的随机数也可能是个非常巨大的数，比如求某几亿的几亿次方，显然计算就会非常慢极容易因为设备的限制（溢出）而无法进行。
1.26 尽管(square x) = (* x x)，但当你真的在计算过程中显式地用两者相乘时是有差别的。(square x)是指计算square的值、计算x的值，再将square应用到x上，x只会被计算一次；(* x x)则明显要进行两次x的计算。考虑下expmod中当遇到偶数时就会减少一半的计算量，因而取得了增长阶θ(㏒ n)，而现在的写法在遇到偶数时计算量又翻倍了。
1.28 Miller-Rabin检查是对费马小定理的变形，根据提示需要在expmod中增加对“1取模n的非平凡平方根”的检查，即a != 1、a != n - 1、a2/n = 1，此外Miller-Rabin变形考察的是an-1与1模n同余，因此原来的try-it中也要进行调整，得到如下，输入Carmichael数进行验证。
(define (invalid-test? a n)
(and (not (= a 1))
(not (= a (- n 1)))
(= 1 (remainder (square a) n))))
(define (expmod base exp m)
(cond ((= exp 0) 1)
((invalid-test? base m) 0)
((even? exp)
(remainder (square (expmod base (/ exp 2) m)) m))
(else
(remainder (* base (expmod base (- exp 1) m)) m))))
(define (miller-rabin-test n)
(define (try-it a)
(= (expmod a (- n 1) n) 1))
(try-it (+ 1 (random (- n 1)))))
(define (fast-prime? n times)
(cond ((= times 0) n)
((miller-rabin-test n) (fast-prime? n (- times 1)))
(else false)))
网友评论