|
|
1.20
下面用 % 表示過程 remainder，那么正則序的過程如下：
(gcd 206 40)
(if (= 40 0) 206 (gcd 40 (% 206 40)))
(gcd 40 (% 206 40))
(if (= (% 206 40) 0) ;<## 1> [6]
40
(gcd (% 206 40) (% 40 (% 206 40))
(gcd (% 206 40) (% 40 (% 206 40)))
(if (= (% 40 (% 206 40)) 0) ;<## 2> [4]
(% 206 40)
(gcd (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))))
(gcd (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))
(if (= (% (% 206 40) (% 40 (% 206 40))) 0) ;<## 4>[2]
(% 40 (% 206 40))
(gcd (% (% 206 40) (% 40 (% 206 40)))
(% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))
(gcd (% (% 206 40) (% 40 (% 206 40)))
(% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))
(if (= (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))) 0) ;<## 7>[0]
(% (% 206 40) (% 40 (% 206 40)))
(gcd ...)
(% (% 206 40) (% 40 (% 206 40))) ;<## 4>[2]
可以看出需要調(diào)用 remainder 共 1+2+4+7+4 = 18 次。
應(yīng)用序計(jì)算過程如下：
(gcd 206 40)
(if (= 40 0) 206 (gcd 40 (% 206 40))) ;<##>
(gcd 40 6)
(if (= 6 0) 40 (gcd 6 (% 40 6))) ;<##>
(gcd 6 4)
(if (= 4 0) 6 (gcd 4 (% 6 4))) ;<##>
(gcd 4 2)
(if (= 2 0) 4 (gcd 2 (% 4 2))) ;<##>
(gcd 2 0)
(if (= 0 0) 2 (gcd 0 (% 2 0)))
2
可以看出共需 4 次。
1.16
(define (fast-expt x n)
(fast-expt-iter x n 1))
(define (fast-expt-iter x n a)
(cond ((= n 0) a)
((even? n) (fast-expt-iter (square x)
(/ n 2)
a))
(else (fast-expt-iter x
(- n 1)
(* a x)))))
1.17
(define (multi x y)
(if (= y 0)
0
(+ x (multi x (- y 1)))))
(define (fast-multi x y)
(cond ((= y 0) 0)
((even? y) (double (fast-multi x
(half y))))
(else (+ x (fast-multi x (- y 1))))))
(define (double x) (+ x x))
(define (half y) (/ y 2))
1.18
(define (double x) (+ x x))
(define (half y) (/ y 2))
(define (fast-multi x y)
(fast-multi-iter x y 0))
(define (fast-multi-iter x y p)
(cond ((= y 0) p)
((even? y) (fast-multi-iter (double x)
(half y)
p))
(else (fast-multi-iter x (- y 1) (+ p x)))))
1.19
;T(pq):(a,b)=>(bq+aq+ap, bp+aq)
;T(pq):(bq+aq+ap, bp+aq)=>((bp+aq)q + (bq+aq+ap)q + (bq+aq+ap)p,
; (bp+aq)p + (bq+aq+ap)q)
; => (2bpq+2aqq+bqq+2apq+app, bpp+2apq+bqq+aqq)
; => (b(2pq+qq)+a(2pq+qq)+a(qq+pp), b(qq+pp)+a(2pq+qq))
;q' = 2pq+qq
;p' = qq+pp
;
(define (fib n)
(fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
(+ (* p p) (* q q))
(+ (* 2 p q ) (* q q))
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
1.14
計(jì)算過程的樹如下：
很容易看出，計(jì)算過程的空間需求，也就是樹的深度，取決于最左邊的子樹，即(n 1)，它的深度是n+6，O(n).
然后對于計(jì)算步數(shù)，也就是樹的節(jié)點(diǎn)數(shù)，我們知道對于一個二叉樹，樹的節(jié)點(diǎn)數(shù) = 左子樹節(jié)點(diǎn)數(shù) + 右子樹節(jié)點(diǎn)數(shù) + 1.
先來看 (n 1) 子樹，設(shè)它的節(jié)點(diǎn)數(shù)是f(n), 而且總有，非葉節(jié)點(diǎn)左子樹節(jié)點(diǎn)數(shù)為1
當(dāng) n=1，f(1) = 3
n>1, f(n) = 1 + f(n-1) + 1 = f(n-1) + 2 = f(n-2) + 2*2
= f(n-(n-1)) + 2*(n-1) = 2n + 1
= O(n)
再來看 (n 2) 子樹，設(shè)它的節(jié)點(diǎn)數(shù) g(n), 設(shè) ┌ n/5 ┐ = A
g(n) = f(n) + g(n-5) + 1 = f(n) + f(n-5) + g(n-5*2) + 2
= f(n) + ... + f(n-5*(A-1)) + g(n-5*A) + 2A
= O(n^2)
依此類推，可以得出結(jié)論 (n 5) 的計(jì)算步數(shù)增長的階 為 O(n^5)
1.15
a) 12.15 連除 5次 3 小于 0.1 ，所以是 5次
b) 可以看出每調(diào)用一次 p 過程，需要遞歸1次 sine ，空間加1，計(jì)算步數(shù)加2，關(guān)鍵是p的次數(shù)：
對于a，調(diào)用次數(shù)t，那么 a*3^(-t) < 0.1 , 即 10a < 3^t ==> lg(10a)/lg3 < t,
所以增長階 空間和時間 都為 O(log a)
我為什么推薦 SICP？
向大家推薦 SICP，不知道有多少人看了，也不知道有多少人明白了，更不知道有多少人驚嘆了?；蛘吣愀静恍家活?，或者你看見 Lisp 那層層括號心生畏懼，又或者你了了一瞥，覺得沒什么精彩之處。那我真的很失望。
我為什么要推薦SICP，而且為什么如此執(zhí)著？這本不算厚的書帶給我的觀念，是從未有過的，是關(guān)乎于軟件本質(zhì)的。曾幾何時，我覺得我看到了計(jì)算機(jī)編程書中沒有的哲學(xué)觀，但這一次我的夢破滅了，那些已經(jīng)被寫進(jìn)書里差不多快 30 年了。
對于 SICP，我真正算看完的，恐怕只有第一章。我現(xiàn)在就來談?wù)勎业男牡茫栽俅蜗蚰阏宫F(xiàn)這本書的魔力。
第一章作為基礎(chǔ)，作者并沒有象后續(xù)章節(jié)寫太多的軟件思想，主要還是介紹 Scheme 語言，所以草草看去，沒什么精辟之處。不過在第一章中，作者用了大量的篇幅來探討數(shù)學(xué)問題，因?yàn)樗胂蚰憬沂境绦蛟O(shè)計(jì)中的核心哲學(xué)：抽象。而數(shù)學(xué)無疑是最好的例子。
了解數(shù)學(xué)史的人，應(yīng)該知道整個數(shù)學(xué)史，就是一個不斷抽象的歷史。古希臘人將字母引入計(jì)算，使數(shù)學(xué)不再只是算術(shù)，而且具有表達(dá)抽象規(guī)則的能力。近代數(shù)學(xué)對函數(shù)和微積分的探求中，用 f(x) 替代了多項(xiàng)式表達(dá)式，函數(shù)更一般了，然后 n 維空間、復(fù)分析、映射、泛函，抽象代數(shù)、群論，等等等等，直到集合論，摧毀了數(shù)學(xué)的基石，使數(shù)學(xué)界再次陷入沉思。
構(gòu)造程序的方法也是抽象。從最簡單的元素開始，基本元素(自演算表達(dá)式，包括數(shù)字，字符串和布爾值），然后定義基本過程（基本運(yùn)算符，四則運(yùn)算和布爾運(yùn)算），進(jìn)一步，自定義標(biāo)識符（如同代數(shù)），再自定義過程（函數(shù)），再將過程作為值參與運(yùn)算（高階過程）。一步步的抽象，形成了整個程序的結(jié)構(gòu)。而我們編程，無非就是從現(xiàn)實(shí)世界抽象出模型，再將模型不斷的提煉抽象，屬性、方法、類、繼承、層次、框架。
編程就是一個不斷抽象的過程。我再次把作者在第一章末寫下的結(jié)論抄在這里，作為最后的注腳。
“作為編程者，我們應(yīng)該對這類可能性保持高度敏感，設(shè)法從中設(shè)別出程序中的基本抽象，基于它們?nèi)ミM(jìn)一步構(gòu)造，并推廣它們以創(chuàng)建威力更強(qiáng)大的抽象。當(dāng)然，這并不是說總應(yīng)該采用盡可能抽象的方式去寫程序，程序設(shè)計(jì)專家們知道如何根據(jù)工作中的情況，去選擇合適的抽象層次。但是，能基于這種抽象去思考確實(shí)是最重要的，只有這樣才可能在新的上下文中去應(yīng)用它們。高階過程的重要性，就在于我們能顯式地用程序設(shè)計(jì)語言的要素去描述這些抽象，使我們能像操作其他計(jì)算元素一樣去操作它們。”
1.11
遞歸計(jì)算過程為
(define func-recu
(lambda(n)
(cond ((< n 3) n)
(else (+ (func-recu (- n 1))
(* 2 (func-recu (- n 2)))
(* 3 (func-recu (- n 3))))))))
迭代計(jì)算過程為
(define func-iter
(lambda(a b c n)
(if (= n 0)
a
(func-iter b c (+ (* 3 a) (* 2 b) c) (- n 1)))))
(define (func n) (func-iter 0 1 2 n))
1.12
中文版原題翻譯有誤，應(yīng)為計(jì)算pascal三角中的元素。
;pas(n,k)
;if (k=1) or (k=n), then pas(n,k) = 1
;else pas(n,k) = pas(n-1,k-1) + pas(n-1,k)
(define pas (lambda(n k)
(if (or (= k 1) (= k n))
1
(+ (pas (- n 1) (- k 1))
(pas (- n 1) k)))))
1.13
中文版原題翻譯遺漏 提示 ：ψ=(1-√5)/2
已知，φ^2 = φ + 1, 那么 φ^n = φ^(n-1) + φ^(n-2)
同理，ψ^2 = ψ + 1, 那么 ψ^n = ψ^(n-1) + ψ^(n-2)
又 φ-ψ = (1+√5)/2 - (1-√5)/2 = √5
when n=0, Fib(0) = 0 = (φ^0-ψ^0)/√5
when n=1, Fib(1) = 1 = √5/√5 = (φ-ψ)/√5
when n>2, Fib(n) = Fib(n-1) + Fib(n-2) = (φ^(n-1)-ψ^(n-1))/√5 + (φ^(n-2)-ψ^(n-2))/√5
= ((φ^(n-1)+(φ^(n-2))) - (ψ^(n-1)+ψ^(n-2)))/√5
= (φ^n - ψ^n)/√5
又 -1< ψ < 0, 故 -0.5< -1/√5< ψ^n/√5 < 1/√5 <0.5
, 而 φ^n/√5 = ψ^n/√5 + Fib(n)
可知 |φ^n/√5 - Fib(n)| < 0.5, Fib(n)是最接近φ^n/√5的整數(shù)。
首先，可以寫出這個函數(shù)的函數(shù)式：
0, y = 0;
f(x,y) = 2y, x = 0;
2, y = 1;
f(x-1, f(x, y-1));
那么，對于 f(0,n), n>=0
當(dāng) n >= 1 時， f(0,n) = 2n ，
而當(dāng) n = 0 時， f(0,0) = 0 = 2*0， 也滿足 2n ，
故 f(0,n) = 2n, n>=0.
對于f(1,n), n>=1
當(dāng) n > 1 時，有 f(1,n) = f(0, f(1, n-1)) = 2*f(1,n-1),
設(shè) f(1,n) = 2^n
if n = 1, f(1,1) = 2 = 2^1
when n > 1, if f(1,n-1) = 2^(n-1)
then f(1,n) = 2*f(1,n-1) = 2*(2^(n-1)) = 2^n
故 f(1,n) = 2^n, n>0.
對于f(2,n), n>0
if n > 1 ,then f(2,n) = f(1, f(2, n-1)) = 2^f(2,n-1),
設(shè) f(2,n) = 2^(2^(... (n 個 2)
if n = 1, then f(2,1) = 2
when n > 1, if f(2, n-1) = 2^(2^(... (n-1)
then f(2,n) = 2^f(2,n-1) = 2^(2^(
這樣我們對于 (A 1 10) = 2^10 = 1024, (A 2 4) = 2^(2^(2^2)) = 2^16 = 65536
而 (A 3 3) = (A 2 A(3 2)) = A(2 A(2 A(2 1))) = (A 2 4) = 2^16 = 65536
(f n) = (A 0 n) = 2n
(g n) = (A 1 n) = 2^n
(h n) = (A 2 n) = 2^(2^(... (n個2)
---------------------------------------------
在網(wǎng)上可以找到關(guān)于 Ackermann 函數(shù)的討論，主要是針對這個雙遞歸如何用迭代來實(shí)現(xiàn)，Ackermann 函數(shù)是 德國數(shù)學(xué)家W.Ackermann 在1928年提出的。在 WikiPedia 英文版上可以搜索 Ackermann function
詞條，有詳細(xì)介紹，不過這個Ackermann function
略有不同。如下圖：
很顯然，第一個是遞歸的，第二個是迭代的。
(+ 4 5)
(if (= 4 0) 5 (inc (+ (dec 4) 5)))
(inc (+ 3 5))
(inc (if (= 3 0) 5 (inc (+ 2 5))))
(inc (inc (if (= 2 0) 5 (inc (+ 1 5)))))
(inc (inc (inc (if (= 1 0) 5 (inc (+ 0 5))))))
(inc (inc (inc (inc (if (= 0 0) 5 (inc (+ (dec 0) 5)))))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9
(+ 4 5)
(if (= 4 0) 5 (+ 3 6))
(if (= 3 0) 6 (+ 2 7))
(if (= 2 0) 7 (+ 1 8))
(if (= 1 0) 8 (+ 0 9))
(if (= 0 0) 9 (+ (dec 0) (inc 9)))
9
采用1.7中的變化率為終止檢測。
(define (cube-root x)
(cube-root-iter x 1.0 x))
(define (cube-root-iter last-guess guess x)
(if (enuf? last-guess guess)
guess
(cube-root-iter guess (improve guess x) x)))
(define (enuf? x y)
(< (/ (abs (- x y)) y) 0.001))
(define improve (lambda (y x)
(/ (+ (/ x (* y y)) (* 2 y)) 3)))
目前為止，程序的表現(xiàn)形式是對過程的敘述，順序、分支、循環(huán)結(jié)構(gòu)是最基本的原子形式。而面向過程的分析和設(shè)計(jì)無疑是最自然的框架結(jié)構(gòu)，它將過程形式的代碼段再次迭代的以過程形式組合，形成整個程序。就像將句子連成段，將段連成章，將章連成篇，將篇連成書。這也是最符合閱讀者思維的形式，整個程序就像一個內(nèi)含超鏈接的文本小說，主體上是流暢的，符合連續(xù)思維的。
面向?qū)ο蟪绦虿荒苷f是顛覆性改變，它的原子表現(xiàn)形式仍然是順序、分支和循環(huán)。而由于依賴于過程性系統(tǒng)的裝載，其整體的最外層仍然是一個過程性的函數(shù)。它與面向過程在其表現(xiàn)形式上的不同，僅僅存在于中間層。
面向?qū)ο蟪绦虻谋憩F(xiàn)形式是詞條式的，至少是傳記體的，而不是編年史。你可以想象，一部小說，作者首先把所有的故事按照角色重新歸類，再分割為一個個小故事，可以想象是這樣的：
——傳記式：
《張三傳》
張三，秦人，少年，虬髯黑臉，為人仗義。
逸事一：若傍晚時訪之，必留宿，夜必邀相飲。三十三年春，李四自華陰來，……
《李四傳》
李四，中原人，白臉壯年書生，十六歲舉秀才。
逸事一：其人好游，某年遇張三……
——詞條式：
醉酒： 張三與李四飲酒，大醉……
舉秀才： 李四，十六時……
張三其人： 秦人，少年，虬髯黑臉，為人仗義……
巧遇： 三十三年，李四巧遇張三……
仗義好客： 張三好客，若傍晚時訪之，必留宿，夜必邀相飲……
這種表現(xiàn)形式是某種詞條式的分裂，故事被不斷的片段化，一個比較好的面向?qū)ο蟪绦蛞话銜写罅康募?xì)粒度對象，對象的屬性和方法都不多，方法都很短。雖然這種表現(xiàn)形式能解決一些過程性敘述的不足，但無疑過分的碎片化會帶來理解上困難，傳記式尚好，詞條式就很難了。這就是面向?qū)ο蟪绦蛟谛问缴铣霈F(xiàn)的弱點(diǎn)。分析設(shè)計(jì)時，需時時腦中回想整體結(jié)構(gòu)，以防偏離。而閱讀維護(hù)時，需要把這些片段慢慢織起來，連成一個故事。
----------------------------------------------
將SICP的注腳240記在這里：
對象模型對世界的近似在于將其分割為獨(dú)立的片斷，函數(shù)式模型則不是沿著對象間的邊界去做模塊化，當(dāng)“對象”之間不共享的狀態(tài)遠(yuǎn)遠(yuǎn)大于它們所共享的狀態(tài)時，對象模型就特別好用。這種對象觀點(diǎn)失效的一個地方就是量子力學(xué)，在那里，將物體看作獨(dú)立的粒子就會導(dǎo)致悖論和混亂。將對象觀點(diǎn)與函數(shù)式觀點(diǎn)合并可能與程序設(shè)計(jì)的關(guān)系不大，而是與基本認(rèn)識論有關(guān)的論題。
對于正文中的 good-enough? 謂詞，設(shè)所求 x 的真實(shí)平方根為 xt，那么我們的依據(jù)是當(dāng) guess 從 1 趨向與 xt 的平方差 小于 c(0.001) 時，guess 近似于 xt。實(shí)際當(dāng) xt^2 也就是 x 足夠小時， guess 會 逐漸穩(wěn)定在 √c 附近。從下面實(shí)驗(yàn)可以看出：
> (sqrt (square 0.1))
0.10032578510960607
> (sqrt (square 0.05))
0.054237622808967656
> (sqrt (square 0.01))
0.03230844833048122
> (sqrt (square 0.005))
0.031515954454847304
> (sqrt (square 0.001))
0.031260655525445276
> (sqrt (square 0.0001))
0.03125010656242753
>
因?yàn)?guess^2 < c + x
, 當(dāng) x < c 時，guess 就更多的依賴于 c 了。
對于特別大的數(shù)，由于浮點(diǎn)數(shù)在特別大時，離散性非常明顯，相鄰的兩個數(shù)之間的差距會非常大，導(dǎo)致 |guess^2 - x| 始終 大于 c，計(jì)算便進(jìn)入了 無限循環(huán)。
比如計(jì)算 (sqrt 1e300)
使用變化率改進(jìn)后的代碼如下：
(define (sqrt-new x)
(sqrt-iter-new x 1.0 x))
(define (sqrt-iter-new s1 s2 x)
(if (enuf-new? s1 s2)
s2
(sqrt-iter-new s2 (improve s2 x) x)))
(define (enuf-new? s1 s2)
(< (/ (abs (- s1 s2)) s1) 0.001))
可以測算幾個數(shù)，驗(yàn)證結(jié)果還是比較好的。
> (sqrt-new (square 1e150))
1.0000000000084744e+150
> (sqrt-new (square 1e-150))
1.0000000000084744e-150
|