SICP 習題 （1.35）解題總結

sicp 習題 1.35要求我們證明黃金分割率φ 是變換函數 x => 1+ 1/x 的不動點，然後利用這一事實通過過程fixed-point 計算出φ的值。

首先是有關函數的不動點，這個概念需要了解清楚，後面好幾道題都是圍繞函數不動點展開的。作者在這裡設計這些習題的原因也是希望讀者可以關注函數不動點。

其實有關不動點這個東西我在做習題“1.8”的時候就覺得好奇了。為什麼“（x+x/y)/2”會不斷逼近x的平方根呢？又為什麼“(x/y2+2y)/3”會不斷逼近x的立方根呢？

當時隻顧着做題，就沒有深入去考慮，經過1.35開始的幾道題才開始對函數的不動點有了一些了解，反過來就覺得習題“1.8”裡提到的逼近x的立方根的方法比較容易了解了。

要完成這裡的幾道習題，大家首先需要讀完書中的1.3.3這一節，裡面有函數不動點的描述。事實上，1.3.3節中的内容是想說明過程（或者說函數）可以被看作一般性的方法，對過程的通性進行讨論。不過，作者可能覺得用函數不動點這個樣例可以很好地展示過程的通性，是以使用了函數不動點作為樣例。對于函數的不動點，我們可以不管過程的内在實作，而在過程外部通過一個一般性的方法求得這些過程的不動點。當然，不是所有函數都有不動點，是以這個方法并不是對所有函數生效的。

那麼，更進一步需要了解的就是：什麼是函數的不動點？

書中是這樣描述的：

如果有x滿足f(x)=x，那麼x就稱之為函數f()的不動點。

聽起來有點抽象，不太好了解，如果我們用下面的例子可能就比較容易了解了。

我們假設目前流行的南韓整容技術是一個函數，叫“整容（）”，那麼我們很容易了解下面的等式：

整容（醜女）= 美女

就是一個醜女送進手術室，通過“整容”函數的處理，輸出的是一個美女。

但是，事實上的整容沒有那麼容易，需要一點一點去整，是以我們的函數應該像下面這樣：

整容（醜女）= 美一點的醜女

如果我們把“美一點的醜女”送去整容，會有：

整容（美一點的醜女）= 更美一點的醜女

于是乎，如果我們有函數：

整容（整容（整容 ......（整容（整容（整容（整容（醜女）））））））

那麼結果就應該很接近美女了。

最終，如果我們把美女送去整容，出來的還是美女，就是說

整容（美女）= 美女

這個時候就是f(x)=x的時候了，就是說“美女”就是函數“整容”的不動點！

這樣你應該可以了解什麼是函數的不動點了吧？

了解了函數的不動點，我們再來看看如何求出一個函數的不動點。還是用整容的例子，方法比較簡單粗暴，就是把随便一個人送去整容，進去之前和送出來後都拍個照片，如果兩張照片相差比較大，就說明這個人整容的空間還比較大，弄進去再整，直到進去之前和出來之後看不出什麼差别了，那麼這個結果就是“整容”函數的不動點了！

如果說“全智賢”是南韓整容界公認的典型美女的話，你随便抓一個人，不管性别，送去給南韓整容醫生不斷整容，最後出來的都長成“全智賢”那樣。

我們就得出了“南韓整容”函數的不動點，那就是“全智賢”！

進一步考察的話，你會發現這個尋找函數不動點的方法和函數本身沒太大關系，“整容”的函數可以用這個方法，“健身”的函數也一樣，“伺服器調優”的函數也一樣，基本思路就是不斷重複調用這個函數，直到這個函數對目标不再起作用為止。

這樣就可以了解書中的fixed-point函數了：

fixed-point函數的作用就是用first-guess作為初始材料，不斷調用函數f對它進行加工，直到f函數的輸入值和輸出值close-enough為止。

這時候回過來考察1.1.7章的求平方根的函數就有清晰的思路了。

書中提到，如果我們希望求一個數x的平方根，就是要求一個y，使得y^2 = x，由y^2=x推導出一個等式y=x/y，是以我們要求的是變換x => x/y的不動點。

這種描述方式對數學高手們是如此簡單，不過對于我等數學白癡來講還是不好了解。

我對于求平方根的方法的了解過程是這樣的。

首先我們把問題簡化一下，求x的平方根變為求一個已知數的平方根，比如求10的平方根。

這樣的話我們要求的其實是一個x，使x * x =10。

或者說是求x1 * x2= 10，同時x1= x2。

如果要讓x1 * x2=10的條件滿足，那麼就有x1 = 10 / x2，這個簡單的數學轉換就好了解了吧。

接着，如果我們設計一個函數f(x)是這樣的 f(x) = 10/x，上面的等式就可以寫成下面這樣：

x1 = 10 / x2 = f (x2)

也就是 x1 = f (x2)

如果我們找到了函數f(x)的不動點，就有f(x)= x，就是有：

x1=f(x2) = x2

這時候就是x1=x2的時候了。

恭喜一下你自己吧！你找到求10得平方根的方法了！

不過。。。。。可惜的是，就像書中說的，變換x => 10/ x并不收斂！

簡單說就是函數f(x)= 10/x沒有不動點！

如果上面這些x1，x2不對你胃口，你還是不了解的話，想象一下下面的場景：

如果你是一個整容醫生，需要對人的眼睛進行整容，而高手告訴你的秘訣是兩個眼睛長度的乘積等于10的時候就是最美麗的一雙眼睛，你會怎麼做呢？

首先你有個常識，就是左右眼要一樣大才行，不然整成大小眼了。現在你要做的就是按高手的秘籍整，直到兩個眼睛一樣大為止。

好，我們這些笨整容醫師們，開始手術啦！

有個人來了，量量他的左眼，嘻嘻，左眼長度2cm！啊，多麼小的眼睛呀。

那麼，按秘籍算一算右眼應該是多大呢？10/2=5！右眼5cm就好了！

手術過後看看完了！大小眼！左眼2cm，右眼5cm。

這不行，把左眼搞成跟右眼一樣吧，也是5cm！

再按秘籍算一算右眼應該是多長？左眼5cm，10/5=2，右眼2cm就好了！

手術過後再看！還是大小眼！左眼5cm，右眼2cm。

繼續整！

哈！沒完沒了了！人給你整殘了你也做不完！

這就叫一個不收斂的變換！

咋辦哩？

用書上說到的“平均阻尼”術！

如果你發現一個人左眼2cm，右眼5cm，合理的眼睛長度應該是兩個眼睛長度的平均數吧！

應該是(2+5)/2，那就是3.4cm

如果左眼搞成3.4cm長，按秘籍計算的話，右眼應該是10/3.4=2.94左右。

左眼3.4cm，右眼2.94cm，還是大小眼，繼續平均一下，眼睛長度應該是(3.4+2.94)/2 吧，大概是3.17.

這就對了嘛，越來越接近了。

是以 x => (x + x/10)/2 這個變化是收斂的。

我們終于可以整出一對美麗的雙眼了！ （上帝呀，千萬不要讓技術男去做整容醫師呀。）

回到題目的本身，題目是要求我們證明黃金分割率 φ 是變換函數 x => 1+ 1/x 的不動點。

黃金分割率φ是什麼？翻回書上的1.2.2節先看看:

φ=1.6180

他是怎麼求出來的呢，他是按等式φ^2=φ+1求出來的。

也就是說，如果有x^2=x+1，那麼x就是黃金分割率。

各位看官請注意，這是sicp書上說的，你要是去百度查黃金分割率可不是這麼回事，百度告訴我們黃精分割率是0.618!

于是有人還去百度問，到底黃金分割率是1.618還是0.618？

其實兩個都對，所謂黃金分割，就是把一個線段ab分成兩段，分别是ao和ob，如果ab/ao=ao/ob，那麼這個線段ab就被“黃金分割”了，這時候如果我們把黃金分割率記錄成ab/ao就是1.618，反過來如果我們記錄成ao/ab就是0.618，這也是黃金分割率迷人的地方，因為1/1.618=0.618。

好，友善起見，我們就用x^2=x+1這個表達式吧，我們要證明函數1+1/x的不動點x滿足x^2=x+1。

有了上面的一系列分析，你會發現問題不是太難。

我們有一個函數f(x)=1+1/x，還是用x1和x2兩個數，x1表示函數輸出，x2表示函數輸入，就有：

x1=1+1/x2

當我們找到函數f(x)=1+1/x的不動點的時候，意味着f(x)=x，就是說x1=x2。

上面的等式就變為x1=1+1/x1，這時候兩邊都乘以x1，就有x1^2=x1+1。

哈哈，就是說函數f(x)=1+1/x的不動點x滿足方程x^2=x+1，滿足方程x^2=x+1的就是φ！

題目的後半部分還要求我們根據這個事實使用fixed-point函數求φ，這就簡單了