過程與它們所產(chǎn)生的計算
1.1節(jié)描述了程序設(shè)計的基本元素并聚焦在過程上崖堤，因此1.2就開始討論過程與他們所產(chǎn)生的計算眉枕。這一節(jié)主要有兩個主題：一是考察計算過程的“形狀”；二是研究過程消耗的計算資源速率愕乎。
通常搪花，我們定義一個過程是為了在某種場景下可重復(fù)地計算一系列值，用書中的話說叫做“描述了一個計算過程的局部演化方式”刨啸，而所謂的局部演化就是指計算過程中的每一步都是基于前面的步驟建立的艘包，經(jīng)典例子就是階乘n! = n * (n - 1) * (n - 2) ...3 * 2 * 1的計算猫牡，在我上學(xué)的時候，課上就講過用遞歸和迭代兩種方式實現(xiàn)徒欣，遞歸實現(xiàn)如下，利用代換模型展開后可以發(fā)現(xiàn)它的計算過程所呈現(xiàn)的形狀是先展開再收縮楼吃，這是遞歸計算過程所特有的形狀始花。
(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
再來看運(yùn)用迭代方式實現(xiàn)的階乘計算妄讯，所謂迭代方式就是通過循環(huán)（如下）實現(xiàn)，觀察循環(huán)可以發(fā)現(xiàn)這個過程中有兩個因素起了作用酷宵，一個是i亥贸，它扮演了控制步進(jìn)的角色，即i ← i + 1浇垦；另一個是res炕置，它扮演了控制器結(jié)果的作用res ← res * (i + 1)，而要驅(qū)動這個循環(huán)生效只需要給定上述因素初始值男韧，也就是書中所說的“狀態(tài)可由固定數(shù)目的狀態(tài)變量描述朴摊，并且描述了狀態(tài)變化時，變量的更新方式”此虑。
def factorial(n):
res = 1
for i in range(n):
res = res * (i + 1)
return res
按照這個結(jié)論甚纲，我們可以得到下面的過程定義并利用代換模型展開，對比上面遞歸計算過程形狀可以發(fā)現(xiàn)迭代方式并沒有呈現(xiàn)出先收縮再展開并且計算次數(shù)與輸入?yún)?shù)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
按照“自己調(diào)用自己”的遞歸通俗化定義介杆，觀察這一過程不難發(fā)現(xiàn)這個所謂的迭代實質(zhì)上也是一種遞歸，完全不同于我們遇到高級語言中各種循環(huán)結(jié)構(gòu)（如do...while韭寸，for等）春哨，造成這種差異的原因是高級語言中的“實現(xiàn)設(shè)計對于遞歸過程的解釋，所需消耗的存儲量總與過程調(diào)用數(shù)目成正比恩伺，即使它的計算過程的原理是迭代的悲靴，導(dǎo)致這些語言描述迭代過程必須借助特殊的‘循環(huán)結(jié)構(gòu)’”。所以我們所說的”自己調(diào)用自己“的遞歸定義實際上描述的是語法形式莫其，而不是計算過程的進(jìn)展方式（或者可以簡單地理解為形狀），識別的關(guān)鍵在于是否存在變量存儲狀態(tài)的變化耸三，存在變量存儲即為迭代計算過程乱陡，而不存在變量完全依賴解釋器則是遞歸計算過程，可見即使是同一求值問題的不同的計算過程實現(xiàn)對解釋器而言是不同的仪壮，從這個意義上我們有必要探討計算效率與資源憨颠，F(xiàn)ibonacci就是一個極佳的例子。
觀察Fibonacci數(shù)列的樹形遞歸計算可以發(fā)現(xiàn)整個過程存在不少重復(fù)計算积锅，比如fib(0)和fib(1)爽彤，其計算步驟隨著輸入增長而指數(shù)性地增長（練習(xí)1.13證明），而在空間上卻是線性增長缚陷。參考上面的迭代計算過程适篙，也可以通過一個變換規(guī)則來描述：設(shè)fib(n)為a、fib(n - 1)為b箫爷，則根據(jù)Fibonacci的定義可以得到a ← a + b嚷节，b ← a聂儒，而其驅(qū)動的初始值就是fib(1) = 1、fib(0) = 0硫痰。
(define (fib-iter a b n)
(if (= n 0)
b
(fib-iter (+ a b) a (- n 1))))
從這個計算過程不難看出衩婚，計算步驟是隨著n線性變化的而空間則是固定的，這只是實現(xiàn)過程本身帶來的計算消耗的變化效斑，而從這里往后的幾個小節(jié)將討論不同算法（同一計算過程）對計算消耗資源的影響非春，為了清楚討論需要引入增長階的概念R(n) = θ(f(n))用來表示計算資源消耗速率（注意：θ(f(n))的含義是用一個f(n)來描述計算增長的變化情況），顯然前面討論遞歸計算過程中階乘的計算步驟與空間需求增長階顯然是θ(n)缓屠，而迭代計算過程中的階乘計算步驟則是θ(n)奇昙，空間需求增長階為θ(1)，同理可得Fibonacci的樹型遞歸計算步驟增長階是θ(φn)空間需求增長階是θ(n)藏研。增長階提供了粗略描述計算過程在資源需求上的差異敬矩，這在幫助我們選擇合適的算法時是很有意義的。
考察求冪問題bn = b * b(n-1)蠢挡，b0 = 1弧岳，這種計算方式可以進(jìn)一步優(yōu)化為bn = (bn/2)2，即先計算b的n/2次方后再計算平方业踏，再結(jié)合奇偶數(shù)的差異禽炬，可以得到如下過程。
(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多了一步腹尖，在數(shù)學(xué)上計算指數(shù)n所需要的乘法次數(shù)的增長大約就是以2為底n的對數(shù)值，所以其增長階可記作θ(㏒ n)伐脖，對比之前的計算過程就能發(fā)現(xiàn)即使在相同的計算過程中热幔，不同的算法會對計算資源消耗產(chǎn)生明顯的影響，這也是算法會成為很多領(lǐng)域追尋的關(guān)鍵原因讼庇。
后面最大公約數(shù)和素數(shù)檢測的介紹非常有意思绎巨，讀書的時候數(shù)學(xué)不是我的強(qiáng)項，但通過這兩個內(nèi)容的介紹卻感受到算法為計算機(jī)求解帶來的質(zhì)的變化蠕啄，描述一個數(shù)學(xué)概念相對容易场勤，但轉(zhuǎn)換為一種具體的算法卻復(fù)雜了很多，數(shù)學(xué)中的奧妙太多了＜吒：拖薄！
如何判斷素數(shù)哈街？在我以前的知識體系中知道素數(shù)是指一個數(shù)除了1和本身外不能被其他自然數(shù)整除留瞳，也就是說我可能要計算n次才能知道n是不是素數(shù)，后來知道不需要計算到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)))
除了上面這種直接的計算過程帝牡，書中介紹了費(fèi)馬小定理來求解素數(shù)往毡，即利用an/n = a/n = a來判斷n是否為素數(shù)，這里的a是小于n的隨機(jī)正整數(shù)靶溜，前面提到過求冪的優(yōu)化是an = (an/2)2开瞭，所以得到an模n的計算過程（與書中過程不同但比較直接，書中不使用這種方式的原因見習(xí)題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))
引用費(fèi)馬定理解決素數(shù)判斷的問題過程中，由于我們通過隨機(jī)數(shù)的方式進(jìn)行采樣所以存在概率問題瓷炮，當(dāng)我們擁有更多的樣本時我們對最終結(jié)果的判斷一定是更加準(zhǔn)確的葱色，這也從另一個方面說明了概率算法的價值。
練習(xí)
1.9 此題是對1.2.1節(jié)知識的實踐娘香，另外注意對代換模型的運(yùn)用苍狰，求解過程如下：
過程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
從上述構(gòu)成執(zhí)行的形狀看，過程1是遞歸而過程2是迭代
1.10 此題可以用代換模型展開分析計算過程烘绽，將(A 1 10)展開后可以觀察到其計算過程是計算2的10次方淋昭，因此(A 1 n)的結(jié)果是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))可以復(fù)用上面的(A 1 n)是計算2的n次方的結(jié)論安接，即要計算2的(A 2 3)次方 翔忽，繼續(xù)展開如下≌甸埽可以推論得到(A 2 n)的數(shù)學(xué)表達(dá)式是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節(jié)有關(guān)遞歸和迭代實現(xiàn)胡野，其中遞歸方式比較簡單贬丛，按照題目描述就能得到：
(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的變換規(guī)則可以得到a ← a + 2b + 3c, b ← a, c ← b额获，因此迭代方式實現(xiàn)的過程如下：
(define (f-iter a b c n)
(if (= n 2)
a
(f-iter (+ a (* 2 b) (* 3 c)) a b (- n 1))))
1.12 帕斯卡三角（也叫楊輝三角）是一個很經(jīng)典的題够庙，初學(xué)編程的時候肯定會遇到這個題目。在這里實際上還是考察對于迭代中變換規(guī)則的提煉抄邀，從題中可知邊界上的數(shù)都是1耘眨，而內(nèi)部的數(shù)都是上面兩個數(shù)之和。我們可以定義一個過程叫pascal-triangle-iter境肾，以行（row）剔难、列（col）為入?yún)⒌ㄓ欤腥缦乱?guī)則col=0輸出1，col=row輸出1偶宫，否則p(row, col) = p(row - 1, col -1) + p(row - 1, col)非迹，直接實現(xiàn)如下所示，但這是一個遞歸過程纯趋。
(define (pascal row column)
(if (or (= column 0)(= column row))
1
(+ (pascal (- row 1) (- column 1))
(pascal (- row 1) column))))
基于上面的變換規(guī)則很難實現(xiàn)迭代版本憎兽，不過可以根據(jù)網(wǎng)上的帕斯卡三角資料找到另一種計算方法即row! / (col! * (row - col)!)，這樣就是通過迭代方式實現(xiàn)階乘吵冒，實現(xiàn)如下：
(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 此題的作用不在于練習(xí)求冪而是掌握其提示的方法纯命，按照提示存在a使得從一個狀態(tài)轉(zhuǎn)移至另一狀態(tài)的a*bn不變，令a = 1并在計算完成時將a作為結(jié)果痹栖。實際上利用bn = (b2)n/2 = (bn/2)2進(jìn)行演化亿汞，我們可以設(shè)一個過程(f b n a) = (f b2 n/2 a)，而當(dāng)n為奇數(shù)時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的演化，運(yùn)用一個最早學(xué)習(xí)乘法的方法图甜，即乘法可看作是連續(xù)加法碍粥，顯然a * b = 2a * (b/2)，再結(jié)合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運(yùn)用迭代進(jìn)行實現(xiàn)黑毅，實現(xiàn)的方法與1.16相同如下嚼摩，與1.16唯一的區(qū)別是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規(guī)則對(a, b)進(jìn)行兩次變換如下：
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的變換規(guī)則
1.20 此題還是考察應(yīng)用、正則序理解缚去，但請注意對if的描述潮秘。當(dāng)采用應(yīng)用序展開時：
(gcd 206 40)
(gcd 40 (r 206 40))
(gcd 6 (r 40 6))
(gcd 4 (r 6 4))
(gcd 2 (r 4 2))
2
而當(dāng)采用應(yīng)用序時如下所示，相比起來數(shù)量非常之多
(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 此題初看內(nèi)容很多但實際上可以進(jìn)行分解易结，首先看要求找出大于1000枕荞、大于10000和大于1000000的三個最小素數(shù)，實際上由于偶數(shù)都能被2整除搞动，所以偶數(shù)就被排除了躏精，所以范圍可以縮小到奇數(shù)；其次最小素數(shù)是指按從小到達(dá)順序找到的前三個素數(shù)鹦肿，所以挨個取奇數(shù)檢驗即可矗烛；最后結(jié)合1.2.6的素數(shù)檢查過程，可以得到如下箩溃。
(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知識點再學(xué)習(xí)一下可以從中找到影子瞭吃，這是兩種不同的計算方式碌嘀，fast-expt是計算冪值后再取模，而expmod則是通過計算模歪架，每次計算的值都不會太大股冗，有些類似GCD過程。采用fast-expt在理論上沒問題而且有容易理解的優(yōu)點牡拇，但問題出在我們要檢測的素數(shù)是一個什么樣的數(shù)魁瞪，當(dāng)這個數(shù)非常非常大時，那么我們?nèi)〉降碾S機(jī)數(shù)也可能是個非常巨大的數(shù)惠呼，比如求某幾億的幾億次方导俘，顯然計算就會非常慢極容易因為設(shè)備的限制（溢出）而無法進(jìn)行。
1.26 盡管(square x) = (* x x)剔蹋，但當(dāng)你真的在計算過程中顯式地用兩者相乘時是有差別的旅薄。(square x)是指計算square的值、計算x的值泣崩，再將square應(yīng)用到x上少梁，x只會被計算一次；(* x x)則明顯要進(jìn)行兩次x的計算矫付】Γ考慮下expmod中當(dāng)遇到偶數(shù)時就會減少一半的計算量，因而取得了增長階θ(㏒ n)买优，而現(xiàn)在的寫法在遇到偶數(shù)時計算量又翻倍了妨马。
1.28 Miller-Rabin檢查是對費(fèi)馬小定理的變形，根據(jù)提示需要在expmod中增加對“1取模n的非平凡平方根”的檢查杀赢，即a != 1烘跺、a != n - 1、a2/n = 1脂崔，此外Miller-Rabin變形考察的是an-1與1模n同余滤淳，因此原來的try-it中也要進(jìn)行調(diào)整，得到如下砌左，輸入Carmichael數(shù)進(jìn)行驗證脖咐。
(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)))
