SICP 习题 (1.13) 解题总结

时间:2021-12-10 16:38:00

SICP习题1.13要求证明Fib(n)是最接近φn/√5 的整数,其中φ=(1+√5)/2 。题目还有一个提示,提示解题者利用归纳法和斐波那契数的定义证明Fib(n)=(φn - ψn) / √5 。

说实话,面对这道题我是完败,完全没有思路那种。更加令人恼火的是,我根本不明白题目中所谓的提示是什么意思。那感觉就好像某个土豪朋友对你说,几千万的项目太难的话就先投资个几百万就好了,而你手上只有几百块一样。

不过,也不能全怪我吧,多少和出题目的作者有关系,在讲计算机程序的书里跑出一道纯数学题有点过分了吧!太不把我们这些没有数学天分的程序员当程序员看了!

然后我好长时间没去做这道题,后来有一天手贱翻了翻《算法导论》,才突然发现SICP相比之下是如此平易近人,于是才回过头将就看了一遍这道题的解法。

首先,Fib(n)=Fib(n-1)+Fib(n-2)这种是递推式,按这种方式去计算的话计算Fib(n)需要计算n次,为了简化计算过程,我们需要找一种方法可以一次性根据n计算Fib(n)的方法,这种方法使用的公式叫一个数列的“通项公式”。

当我去百度查到“通项公式”的时候,我似乎回想起来一点点,高中应该是接触过这个概念的。

后面解题过程就变成了求斐波那契数列的通项公式,有关这一点百度百科里有详细说明,包括斐波那契数列通项公式的证明,使用什么等比数列法之类的。就不用我转载了。

总之,我硬着头皮将整个证明过程看了一遍,看的时候好像明白了,一合眼又好像什么都不记得了。

后来,后来就没有后来了,因为我实在没有时间在这里消耗了,如果以后有时间再仔细研究。最近越发觉得应该补一补数学了,刚入手同济大学的《高等数学》,还没来得及看,工作实在太忙。

好消息是如果你像我一样也跳过这道题的话,似乎对解答后面的题影响不大。