莊周夢蝶

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

習題1.35，證明黃金分割率φ是變換x->x+1/x的不動點，并利用這個事實通過過程fixed-point計算出φ 值。

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

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

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

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

看看結果：

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

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

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


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

OK,其中combiner是進行累積的操作，而null-value值基本值。現在改寫sum和product過程，對于sum過程來說，累積的操作就是加法，而基本值當然是0了：

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

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

上面的accumulate過程是遞歸版本，對應的迭代版本也很容易改寫了：

再看習題1.33，在accumulate的基礎上多增加一個filter的參數（也是一個過程，用于判斷項是否符合要求），在accumulate的基礎上稍微修改下，在每次累積之前進行判斷即可：


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

測試一下：

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

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

(sum 1 10)：
=》 55

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

    復用sum過程，也可以這樣寫：

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

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

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

;; 直接定義(expmod base exp m)為base^exp基于m的模(modulo)
;; (define (expmod base exp m)
;;   (remainder (fast-expt base exp) m))
;; 在理想情況下是正確的，在語義上與原定義是等價的，甚至遞歸層數
;; 都是一樣的，而且更加直觀。
;;
;; 但在實踐中，這樣的定義是不可行的，這也是為什么我們要采用原文中的定義
;; 的原因：因為base^exp很可能是一個非常大的數。比如，當我們取第二個
;; 測試例子中的n=1000000時，base是[1,999999]區間中的任意
;; 隨機數，它的平均取值為50000，而exp=1000000。50000^1000000是一個大得
;; 驚人的數，無論是fast-expt的層層函數調用計算，還是用remainder對其取模，
;; 計算量都是很大的。
;;
;; 而相反，原始的expmod函數
;; (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)，使得每層遞歸
;; 調用的計算參數和返回值總是小于n (x mod n < n)，即便是計算過程中出現
;; 的最大數(a mod n) * (b mod n) 也依然是要小于n^2, 相對于前者n^n的數
;; 量級，實在是小得多，這樣就避免了大數的計算問題。
;;
;; 比如經測試，在使用新的expmod的情況下，1009的驗證需要1.2ms的時間，
;; 1000003的驗證需要 93680ms，遠高于原來的expmod函數。
;;
;; 這也同時印證了我們在1.24題中的分析，同樣的操作在不同字長的數字上的
;; 代價是不同的。1000000的驗證時間現在是1000的8000多倍，遠不再是2倍左右
;; 的關系。在1.24中的，因為expmod算法的控制，操作數最多是n^2級的，字長
;; 所引起的差距并不明顯，只在10^6-10^12間產生了一點點階躍；而這里的算法
;; 中, 操作數可以達到n^n級，當n=1000時，1000^1000的字長大約在10000位(二
;; 進制數)左右，而n=1000000時1000000^1000000的字長則達到在20000000位(二
;; 進制數)左右，這字長的巨大差距導致了我們在1.24中已經發現的問題更加明顯。

    盡管兩個過程在語義和原理是相通的，但因為在不同的場景中使用，所碰到的情況就截然不同了，算法在不同場景下的表現差異明顯，還需仔細斟酌。

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

習題1.17:
已知兩個過程,double過程可以求出一個整數的兩倍，而halve過程將一個偶數除以2;要求寫出一個過程，只用對數個步驟計算兩個整數的乘積。

解答:
計算a*b，考慮兩種情況：
1)當b是偶數時：
a*b=2(a*(b/2))
2)當b是奇數時：
a*b=a*(b-1)+a

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

習題1.18:將1.17的遞歸過程改寫為迭代過程，保持對數個步驟

分析：遞歸轉化為迭代，關鍵是要抓住狀態遷移間的不變量，我們給它一個狀態變量c，問題歸結為如何保持c+a*b不變。
1)當b是偶數：
c+a*b=c+(2a)*(b/2))
在此過程中的狀態變換：

2)當b是奇數:
c+a*b=(c+a)+a*(b-1)
回溯此狀態轉換：

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

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

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


2)當n是奇數：
(ab)b^(n-1) = abⁿ
回溯狀態的變遷：

就此可以寫出lisp過程了:

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

    本小節主要介紹了階的概念，與算法中計算時間和空間復雜度類似。給了一個過程：
    這個過程用于求弧度的正弦值
a)在求值(sine 12.15)時，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被調用了5次

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

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

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

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

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

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

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

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

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

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

寫幾個過程測試一下：
結果一切正常，但是，當這3個參數是過程的時候會發生什么情況呢？在這3個參數如果存在遞歸調用等情況下，解釋器也將陷入無限循環導致棧溢出！比如書中的求平方根過程用new-if改寫：

因為解釋器是應用序求值，將對new-if過程的3個參數求值，其中第三個參數也是一個過程(sqrt_iter (improve guess x) x)) 遞歸調用自身，導致無限循環直到棧溢出。