|
|
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]
可以看出需要調用 remainder 共 1+2+4+7+4 = 18 次。
應用序計算過程如下：
(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
計算過程的樹如下：
很容易看出，計算過程的空間需求，也就是樹的深度，取決于最左邊的子樹，即(n 1)，它的深度是n+6，O(n).
然后對于計算步數，也就是樹的節點數，我們知道對于一個二叉樹，樹的節點數 = 左子樹節點數 + 右子樹節點數 + 1.
先來看 (n 1) 子樹，設它的節點數是f(n), 而且總有，非葉節點左子樹節點數為1
當 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) 子樹，設它的節點數 g(n), 設 ┌ 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)
依此類推，可以得出結論 (n 5) 的計算步數增長的階 為 O(n^5)
1.15
a) 12.15 連除 5次 3 小于 0.1 ，所以是 5次
b) 可以看出每調用一次 p 過程，需要遞歸1次 sine ，空間加1，計算步數加2，關鍵是p的次數：
對于a，調用次數t，那么 a*3^(-t) < 0.1 , 即 10a < 3^t ==> lg(10a)/lg3 < t,
所以增長階 空間和時間 都為 O(log a)
我為什么推薦 SICP？
向大家推薦 SICP，不知道有多少人看了，也不知道有多少人明白了，更不知道有多少人驚嘆了。或者你根本不屑一顧，或者你看見 Lisp 那層層括號心生畏懼，又或者你了了一瞥，覺得沒什么精彩之處。那我真的很失望。
我為什么要推薦SICP，而且為什么如此執著？這本不算厚的書帶給我的觀念，是從未有過的，是關乎于軟件本質的。曾幾何時，我覺得我看到了計算機編程書中沒有的哲學觀，但這一次我的夢破滅了，那些已經被寫進書里差不多快 30 年了。
對于 SICP，我真正算看完的，恐怕只有第一章。我現在就來談談我的心得，以再次向你展現這本書的魔力。
第一章作為基礎，作者并沒有象后續章節寫太多的軟件思想，主要還是介紹 Scheme 語言，所以草草看去，沒什么精辟之處。不過在第一章中，作者用了大量的篇幅來探討數學問題，因為他想向你揭示程序設計中的核心哲學：抽象。而數學無疑是最好的例子。
了解數學史的人，應該知道整個數學史，就是一個不斷抽象的歷史。古希臘人將字母引入計算，使數學不再只是算術，而且具有表達抽象規則的能力。近代數學對函數和微積分的探求中，用 f(x) 替代了多項式表達式，函數更一般了，然后 n 維空間、復分析、映射、泛函，抽象代數、群論，等等等等，直到集合論，摧毀了數學的基石，使數學界再次陷入沉思。
構造程序的方法也是抽象。從最簡單的元素開始，基本元素(自演算表達式，包括數字，字符串和布爾值），然后定義基本過程（基本運算符，四則運算和布爾運算），進一步，自定義標識符（如同代數），再自定義過程（函數），再將過程作為值參與運算（高階過程）。一步步的抽象，形成了整個程序的結構。而我們編程，無非就是從現實世界抽象出模型，再將模型不斷的提煉抽象，屬性、方法、類、繼承、層次、框架。
編程就是一個不斷抽象的過程。我再次把作者在第一章末寫下的結論抄在這里，作為最后的注腳。
“作為編程者，我們應該對這類可能性保持高度敏感，設法從中設別出程序中的基本抽象，基于它們去進一步構造，并推廣它們以創建威力更強大的抽象。當然，這并不是說總應該采用盡可能抽象的方式去寫程序，程序設計專家們知道如何根據工作中的情況，去選擇合適的抽象層次。但是，能基于這種抽象去思考確實是最重要的，只有這樣才可能在新的上下文中去應用它們。高階過程的重要性，就在于我們能顯式地用程序設計語言的要素去描述這些抽象，使我們能像操作其他計算元素一樣去操作它們。”
1.11
遞歸計算過程為
(define func-recu
(lambda(n)
(cond ((< n 3) n)
(else (+ (func-recu (- n 1))
(* 2 (func-recu (- n 2)))
(* 3 (func-recu (- n 3))))))))
迭代計算過程為
(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
中文版原題翻譯有誤，應為計算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的整數。
首先，可以寫出這個函數的函數式：
0, y = 0;
f(x,y) = 2y, x = 0;
2, y = 1;
f(x-1, f(x, y-1));
那么，對于 f(0,n), n>=0
當 n >= 1 時， f(0,n) = 2n ，
而當 n = 0 時， f(0,0) = 0 = 2*0， 也滿足 2n ，
故 f(0,n) = 2n, n>=0.
對于f(1,n), n>=1
當 n > 1 時，有 f(1,n) = f(0, f(1, n-1)) = 2*f(1,n-1),
設 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),
設 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)
---------------------------------------------
在網上可以找到關于 Ackermann 函數的討論，主要是針對這個雙遞歸如何用迭代來實現，Ackermann 函數是 德國數學家W.Ackermann 在1928年提出的。在 WikiPedia 英文版上可以搜索 Ackermann function
詞條，有詳細介紹，不過這個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)))
目前為止，程序的表現形式是對過程的敘述，順序、分支、循環結構是最基本的原子形式。而面向過程的分析和設計無疑是最自然的框架結構，它將過程形式的代碼段再次迭代的以過程形式組合，形成整個程序。就像將句子連成段，將段連成章，將章連成篇，將篇連成書。這也是最符合閱讀者思維的形式，整個程序就像一個內含超鏈接的文本小說，主體上是流暢的，符合連續思維的。
面向對象程序不能說是顛覆性改變，它的原子表現形式仍然是順序、分支和循環。而由于依賴于過程性系統的裝載，其整體的最外層仍然是一個過程性的函數。它與面向過程在其表現形式上的不同，僅僅存在于中間層。
面向對象程序的表現形式是詞條式的，至少是傳記體的，而不是編年史。你可以想象，一部小說，作者首先把所有的故事按照角色重新歸類，再分割為一個個小故事，可以想象是這樣的：
——傳記式：
《張三傳》
張三，秦人，少年，虬髯黑臉，為人仗義。
逸事一：若傍晚時訪之，必留宿，夜必邀相飲。三十三年春，李四自華陰來，……
《李四傳》
李四，中原人，白臉壯年書生，十六歲舉秀才。
逸事一：其人好游，某年遇張三……
——詞條式：
醉酒： 張三與李四飲酒，大醉……
舉秀才： 李四，十六時……
張三其人： 秦人，少年，虬髯黑臉，為人仗義……
巧遇： 三十三年，李四巧遇張三……
仗義好客： 張三好客，若傍晚時訪之，必留宿，夜必邀相飲……
這種表現形式是某種詞條式的分裂，故事被不斷的片段化，一個比較好的面向對象程序一般會有大量的細粒度對象，對象的屬性和方法都不多，方法都很短。雖然這種表現形式能解決一些過程性敘述的不足，但無疑過分的碎片化會帶來理解上困難，傳記式尚好，詞條式就很難了。這就是面向對象程序在形式上出現的弱點。分析設計時，需時時腦中回想整體結構，以防偏離。而閱讀維護時，需要把這些片段慢慢織起來，連成一個故事。
----------------------------------------------
將SICP的注腳240記在這里：
對象模型對世界的近似在于將其分割為獨立的片斷，函數式模型則不是沿著對象間的邊界去做模塊化，當“對象”之間不共享的狀態遠遠大于它們所共享的狀態時，對象模型就特別好用。這種對象觀點失效的一個地方就是量子力學，在那里，將物體看作獨立的粒子就會導致悖論和混亂。將對象觀點與函數式觀點合并可能與程序設計的關系不大，而是與基本認識論有關的論題。
對于正文中的 good-enough? 謂詞，設所求 x 的真實平方根為 xt，那么我們的依據是當 guess 從 1 趨向與 xt 的平方差 小于 c(0.001) 時，guess 近似于 xt。實際當 xt^2 也就是 x 足夠小時， guess 會 逐漸穩定在 √c 附近。從下面實驗可以看出：
> (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
>
因為 guess^2 < c + x
, 當 x < c 時，guess 就更多的依賴于 c 了。
對于特別大的數，由于浮點數在特別大時，離散性非常明顯，相鄰的兩個數之間的差距會非常大，導致 |guess^2 - x| 始終 大于 c，計算便進入了 無限循環。
比如計算 (sqrt 1e300)
使用變化率改進后的代碼如下：
(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))
可以測算幾個數，驗證結果還是比較好的。
> (sqrt-new (square 1e150))
1.0000000000084744e+150
> (sqrt-new (square 1e-150))
1.0000000000084744e-150
|