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函数求φ，这就简单了