莊周夢(mèng)蝶

    本節(jié)內(nèi)容介紹了將高階過程用于一般性過程，舉了兩個(gè)例子：區(qū)間折半查找方程根和找出函數(shù)不動(dòng)點(diǎn)。習(xí)題也是圍繞這兩個(gè)問題展開。今天工作上遇到了比較郁悶的事情，這周末確定要加班，心情實(shí)在糟糕!-_-，先做兩題吧，有空再繼續(xù)。

習(xí)題1.35，證明黃金分割率φ是變換x->x+1/x的不動(dòng)點(diǎn)，并利用這個(gè)事實(shí)通過過程fixed-point計(jì)算出φ 值。

這道題目很簡單了，根據(jù)黃金分割的定義，φ滿足方程：φ的平方=φ+1；兩邊同除以φ，得到方程：
φ=φ+1/φ。根據(jù)函數(shù)不動(dòng)點(diǎn)定義f(x)=x，可以得到φ就是變換x->x+1/x的不動(dòng)點(diǎn)。利用fixed-point過程寫出：

習(xí)題1.36解答：
首先修改fixed-point過程，使它輸出每次猜測的近似值：
使用了newline和display基本過程，然后要求x->log(1000)/log(x)的不動(dòng)點(diǎn)，并比較平均阻尼方式和非平均阻尼方式的計(jì)算步數(shù)。
首先，請(qǐng)看非平均阻尼方式(直接看截圖了)，我們以2作為初始猜測值：

可以看到，非平均阻尼方式執(zhí)行了33步才計(jì)算出了x值。

再看平均阻尼方式，方程x=log(1000)/log(x)可以轉(zhuǎn)化為：
x=(1/2)(x+log(1000)/log(x))

看看結(jié)果：

僅僅執(zhí)行了9步就完成了計(jì)算，大概是非平均阻尼方式的1/3(在不同機(jī)器上可能結(jié)果不同，可平均阻尼一定快于不用平均阻尼）。

由此可見：使用平均阻尼技術(shù)比不用平均阻尼技術(shù)收斂的快得多。

    此題與1.32、1.33是一個(gè)系列題，沒什么難度，只不過把sum的加改成乘就可以了，遞歸與迭代版本相應(yīng)修改即可：
   分號(hào)注釋的是遞歸版本。利用product過程生成一個(gè)計(jì)算pi的過程，也是很簡單，通過觀察公式的規(guī)律即可得出：
測試一下:


再來看習(xí)題1.32，如果說sum和product過程是一定程度的抽象，將對(duì)累積項(xiàng)和下一項(xiàng)的處理抽象為過程作為參數(shù)提取出來，那么這個(gè)題目要求將累積的操作也作為參數(shù)提取出來，是更高層次的抽象，同樣也難不倒我們：

OK,其中combiner是進(jìn)行累積的操作，而null-value值基本值。現(xiàn)在改寫sum和product過程，對(duì)于sum過程來說，累積的操作就是加法，而基本值當(dāng)然是0了：

而對(duì)于product，累積操作是乘法，而基本值是1，因此：

測試一下過去寫的那些測試程序，比如生成pi的過程，可以驗(yàn)證一切正常！

上面的accumulate過程是遞歸版本，對(duì)應(yīng)的迭代版本也很容易改寫了：

再看習(xí)題1.33，在accumulate的基礎(chǔ)上多增加一個(gè)filter的參數(shù)（也是一個(gè)過程，用于判斷項(xiàng)是否符合要求），在accumulate的基礎(chǔ)上稍微修改下，在每次累積之前進(jìn)行判斷即可：


比如，求a到b中的所有素?cái)?shù)之和的過程可以寫為（利用以前寫的prime?過程來判斷素?cái)?shù)):

測試一下：

    這節(jié)開始介紹將用高階函數(shù)做抽象的技術(shù)，比如將過程作為參數(shù)、返回值等等。習(xí)題1.30要求將書中的sum遞歸過程改造為迭代版本，解答如下：

測試一下，比如求pi的過程：

(sum 1 10)：
=》 55

    再提下1.29的題目，使用辛普森規(guī)則計(jì)算定積分，一開始我沒有使用sum過程，自己寫了遞歸：

    復(fù)用sum過程，也可以這樣寫：

    這一題不是我獨(dú)立想出來的咯,比較遺憾，沒有認(rèn)真讀書中的注解，通過google解決的，一搜索才發(fā)現(xiàn)網(wǎng)上已經(jīng)有很多的scip習(xí)題的解答，我這個(gè)倒是畫蛇添足了!-_-。想一想還是有寫下去的必要，盡管牛人多如牛毛，自己還是潛下心來一步一步向前。
   來自http://dev.csdn.net/develop/article/64/64485.shtm

; ======================================================================
;
;          Structure and Interpretation of Computer Programs
;                  (trial answer to excercises)
;
;                  計(jì)算機(jī)程序的構(gòu)造和解釋(習(xí)題試解)
;
;                                             created: code17 02/28/05
;                                             modified:
; (保持內(nèi)容完整不變前提下，可以任意轉(zhuǎn)載)
; ======================================================================

;; SICP No.1.25
;; 本題為理解題

;; 直接定義(expmod base exp m)為base^exp基于m的模(modulo)
;; (define (expmod base exp m)
;;   (remainder (fast-expt base exp) m))
;; 在理想情況下是正確的，在語義上與原定義是等價(jià)的，甚至遞歸層數(shù)
;; 都是一樣的，而且更加直觀。
;;
;; 但在實(shí)踐中，這樣的定義是不可行的，這也是為什么我們要采用原文中的定義
;; 的原因：因?yàn)閎ase^exp很可能是一個(gè)非常大的數(shù)。比如，當(dāng)我們?nèi)〉诙€(gè)
;; 測試?yán)又械膎=1000000時(shí)，base是[1,999999]區(qū)間中的任意
;; 隨機(jī)數(shù)，它的平均取值為50000，而exp=1000000。50000^1000000是一個(gè)大得
;; 驚人的數(shù)，無論是fast-expt的層層函數(shù)調(diào)用計(jì)算，還是用remainder對(duì)其取模，
;; 計(jì)算量都是很大的。
;;
;; 而相反，原始的expmod函數(shù)
;; (define (expmod base exp m)
;;   (cond ((= exp 0) 1)
;;         ((even? exp)
;;          (remainder (square (expmod base (/ exp 2) m))
;;                     m))
;;         (else
;;          (remainder (* base (expmod base (- exp 1) m))
;;                     m))))
;; 通過分解(a*b mod n) 為 ((a mod n) * (b mod n) mod n)，使得每層遞歸
;; 調(diào)用的計(jì)算參數(shù)和返回值總是小于n (x mod n < n)，即便是計(jì)算過程中出現(xiàn)
;; 的最大數(shù)(a mod n) * (b mod n) 也依然是要小于n^2, 相對(duì)于前者n^n的數(shù)
;; 量級(jí)，實(shí)在是小得多，這樣就避免了大數(shù)的計(jì)算問題。
;;
;; 比如經(jīng)測試，在使用新的expmod的情況下，1009的驗(yàn)證需要1.2ms的時(shí)間，
;; 1000003的驗(yàn)證需要 93680ms，遠(yuǎn)高于原來的expmod函數(shù)。
;;
;; 這也同時(shí)印證了我們?cè)?.24題中的分析，同樣的操作在不同字長的數(shù)字上的
;; 代價(jià)是不同的。1000000的驗(yàn)證時(shí)間現(xiàn)在是1000的8000多倍，遠(yuǎn)不再是2倍左右
;; 的關(guān)系。在1.24中的，因?yàn)閑xpmod算法的控制，操作數(shù)最多是n^2級(jí)的，字長
;; 所引起的差距并不明顯，只在10^6-10^12間產(chǎn)生了一點(diǎn)點(diǎn)階躍；而這里的算法
;; 中, 操作數(shù)可以達(dá)到n^n級(jí)，當(dāng)n=1000時(shí)，1000^1000的字長大約在10000位(二
;; 進(jìn)制數(shù))左右，而n=1000000時(shí)1000000^1000000的字長則達(dá)到在20000000位(二
;; 進(jìn)制數(shù))左右，這字長的巨大差距導(dǎo)致了我們?cè)?.24中已經(jīng)發(fā)現(xiàn)的問題更加明顯。

    盡管兩個(gè)過程在語義和原理是相通的，但因?yàn)樵诓煌膱鼍爸惺褂茫龅降那闆r就截然不同了，算法在不同場景下的表現(xiàn)差異明顯，還需仔細(xì)斟酌。

    這兩道題目沒什么難度了，冪運(yùn)算是連續(xù)乘，乘法運(yùn)算就是連續(xù)加，改造一下書中的例子和習(xí)題1.16就可以了，還是分析一下。

習(xí)題1.17:
已知兩個(gè)過程,double過程可以求出一個(gè)整數(shù)的兩倍，而halve過程將一個(gè)偶數(shù)除以2;要求寫出一個(gè)過程，只用對(duì)數(shù)個(gè)步驟計(jì)算兩個(gè)整數(shù)的乘積。

解答:
計(jì)算a*b，考慮兩種情況：
1)當(dāng)b是偶數(shù)時(shí)：
a*b=2(a*(b/2))
2)當(dāng)b是奇數(shù)時(shí)：
a*b=a*(b-1)+a

通過遞歸直接得到lisp過程，很好理解了，預(yù)先定義了兩個(gè)已知過程double和halve：

習(xí)題1.18:將1.17的遞歸過程改寫為迭代過程，保持對(duì)數(shù)個(gè)步驟

分析：遞歸轉(zhuǎn)化為迭代，關(guān)鍵是要抓住狀態(tài)遷移間的不變量，我們給它一個(gè)狀態(tài)變量c，問題歸結(jié)為如何保持c+a*b不變。
1)當(dāng)b是偶數(shù)：
c+a*b=c+(2a)*(b/2))
在此過程中的狀態(tài)變換：

2)當(dāng)b是奇數(shù):
c+a*b=(c+a)+a*(b-1)
回溯此狀態(tài)轉(zhuǎn)換：

由此可以得到該過程的迭代版本，兩個(gè)已知過程與上同：

    此題充分展示了如何將遞歸轉(zhuǎn)化為迭代的技巧：定義一個(gè)不變量，要求它在迭代狀態(tài)之間保持不變！題目如下：
寫一個(gè)過程求平方，并且只用對(duì)數(shù)個(gè)步驟。

解答：
考慮一個(gè)附加狀態(tài)a，如何保持ab**n(b**n表示b的n次方）在狀態(tài)改變間保持不變.
1)當(dāng)n是偶數(shù)：
a(b²)^n/2 = abⁿ
bⁿ = (b^n/2)² = (b²)^n/2
在這個(gè)過程中回溯狀態(tài)的遷移：


2)當(dāng)n是奇數(shù)：
(ab)b^(n-1) = abⁿ
回溯狀態(tài)的變遷：

就此可以寫出lisp過程了:

這道題目一開始我的解答完全錯(cuò)了！-_-，我理解錯(cuò)了題意，一直將指數(shù)對(duì)半折，這樣的步驟是n/2步而不是對(duì)數(shù)步驟，階仍然是(theta)(n)：

    本小節(jié)主要介紹了階的概念，與算法中計(jì)算時(shí)間和空間復(fù)雜度類似。給了一個(gè)過程：
    這個(gè)過程用于求弧度的正弦值
a)在求值(sine 12.15)時(shí)，p過程將被使用多少次？
答：
(sine 12.15)->(p (sine 4.05))
            ->(p (p (sine 1.35)))
            ->(p (p (p (sine 0.45))))
            ->(p (p (p (p (sine 0.15)))))
            ->(p (p (p (p (p (sine 0.05))))))
顯而易見，p被調(diào)用了5次

b)由過程sine所產(chǎn)生的計(jì)算過程使用的空間和步數(shù)增長的階是多少？
從上面的分析可以看出，空間和步數(shù)的增長都跟p的調(diào)用次數(shù)成正比，也就是與遞歸次數(shù)是線性關(guān)系。
當(dāng)|a|<0.1時(shí)，遞歸次數(shù)為0
當(dāng)|a|>0.1時(shí)，遞歸的最大次數(shù)滿足條件：|a|/3**num<0.1，這里的3**num采用ruby記法表示3的num次方，此時(shí)遞歸次數(shù)num<log3(10a)
因此，對(duì)于空間和步數(shù)的階應(yīng)該為:R(n)=(theta)lg(n)

    這個(gè)小節(jié)主要講解了迭代與樹形遞歸，遞歸比起迭代更易于理解和直觀，而迭代相比于遞歸則效率更高，一般計(jì)算機(jī)的遞歸實(shí)現(xiàn)都是使用堆棧結(jié)構(gòu)實(shí)現(xiàn)的，當(dāng)遞歸層次太深的時(shí)候容易導(dǎo)致棧溢出，而迭代則沒有這樣的問題。
習(xí)題1.11是這樣的：
    如果n<3，那么f(n)=n;如果n>=3，那么f(n)=f(n-1)+2f(n-2)+3f(n-3)，請(qǐng)寫一個(gè)采用遞歸計(jì)算過程f的過程，再改寫一個(gè)采用迭代計(jì)算過程計(jì)算f的過程。

解答：
1.采用遞歸的話就很簡單了，可以將條件直接描述為一個(gè)lisp過程，沒什么好解釋的：
2。迭代就相對(duì)麻煩點(diǎn)，將遞歸轉(zhuǎn)化為迭代，關(guān)鍵在于找出迭代每一步之間的差異，這個(gè)差異就是每次迭代變化的量，找出這個(gè)固定編號(hào)的量就是問題的關(guān)鍵。很容易就可以看出f(n)和f(n-1)之間的差距就是：2f(n-2)+3f(n-3)。這就提示我們需要保持3個(gè)順序的狀態(tài)變量：f(n-2)、 f(n-1) 、f(n)，迭代向前一步的時(shí)候：f(n-2)被f(n-1)取代，f(n-1)被f(n)取代，將f(n)+2f(n-2)+3f(n-3)做為新的f(n)。迭代是自底向上，初始化的3個(gè)變量就是0、1、2，這樣就可以相應(yīng)地寫出一個(gè)迭代版本的解答：

可以測試一下，在n數(shù)目比較大的時(shí)候，遞歸版本速度明顯變慢甚至棧溢出，而迭代版本就比較快了。

習(xí)題1.12：用遞歸過程描述帕斯卡三角（或者說楊輝三角）
根據(jù)楊輝三角的特點(diǎn)，x行y列的數(shù)字等于x-1行y列的數(shù)字和x-1行y-1列的數(shù)字之和，就可以解決這個(gè)問題：

    綜合了習(xí)題1.6提出的誤差過大問題，采用相對(duì)誤差進(jìn)行求值，題目是要求使用牛頓近似求立方根公式寫出scheme過程：
測試一下：

    這是《計(jì)算機(jī)程序的構(gòu)造與解釋》中的一道習(xí)題，如何去判斷一個(gè)scheme解釋器是采用什么方式進(jìn)行求值的？應(yīng)用序 or 正則序。應(yīng)用序是先對(duì)參數(shù)求值而后應(yīng)用，而正則序則相反——完全展開而后歸約求值。正則序相比于應(yīng)用序，會(huì)部分存在重復(fù)求值的情況。習(xí)題是這樣的：
    Ben Bitdiddle發(fā)明了一種檢測方法，能夠確定解釋器究竟采用的哪種序求值，是采用正則序，還是采用應(yīng)用序，他定義了下面兩個(gè)過程：
  
    而后他求值下列的表達(dá)式：
   如果解釋器采用的是應(yīng)用序求值，ben將會(huì)看到什么情況？如果是正則序呢？

    分別分析下這兩種情況下解釋器的求值過程：
1.如果解釋器是應(yīng)用序，將先對(duì)過程test的參數(shù)求值，0仍然是0，(p)返回的仍然是(p)，并且將無窮遞歸下去直到棧溢出，顯然，在這種情況下，解釋器將進(jìn)入假死狀態(tài)沒有輸出。

2.如果解釋器是正則序，完全展開test過程：
接下來再進(jìn)行求值，顯然0=0，結(jié)果將返回0。

    一般lisp的解釋器都是采用應(yīng)用序進(jìn)行求值。這個(gè)問題在習(xí)題1.6中再次出現(xiàn)。我們知道scheme已經(jīng)有一個(gè)cond else的特殊形式，為什么還需要一個(gè)if else的特殊形式呢？那么我們改寫一個(gè)new-if看看：

寫幾個(gè)過程測試一下：
結(jié)果一切正常，但是，當(dāng)這3個(gè)參數(shù)是過程的時(shí)候會(huì)發(fā)生什么情況呢？在這3個(gè)參數(shù)如果存在遞歸調(diào)用等情況下，解釋器也將陷入無限循環(huán)導(dǎo)致棧溢出！比如書中的求平方根過程用new-if改寫：

因?yàn)榻忉屍魇菓?yīng)用序求值，將對(duì)new-if過程的3個(gè)參數(shù)求值，其中第三個(gè)參數(shù)也是一個(gè)過程(sqrt_iter (improve guess x) x)) 遞歸調(diào)用自身，導(dǎo)致無限循環(huán)直到棧溢出。