【读书笔记】算法漫步 第1章

问题 22 斐波那契数列

问题：斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为：1、1、2、3、5、8、13、21、34……在数学上，这一数列以如下递推的方法定义：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）【摘自百度百科】

斐波那契数列现在还有名，一是它本身有许多特别的数学性质，至今很多数学竞赛还可以以此出新题；二是科学家发现很多实际的结构的数学表述都与斐波那契数列有关，比如黄金分割系数。

求解斐波那契数几个层次

层次一，从递归算法开始的不断优化，直至设计出线性复杂度的迭代算法。

斐波那契数列是一个经典的递推公式，F(n)=F(n - 1)+F(n - 2)（数学知识），利用这个递推公式（算法逻辑），就可以求第n个斐波那契数。

利用递推公式，写一个递归算法（程序与数据结构），是最直接的（为什么，这需要去学习 递归算法；其实每本讲述递归的教材，都会用斐波那契数列举例）。

而且，这个算法，还可以优化，这也是讲述算法优化的教材，都会用求解斐波那契数列算法优化举例，直至设计出线性复杂度的迭代算法。

层次二，计算机实际运行上述算法设计的程序时，会因为硬件约束，出现结果“溢出”现象。也就是斐波那契数的数值，超过了计算机存储空间能表示的整数的最大允许范围。（这是一个数学，算法，和程序，三者之间的一个很有意思的认知，也是一个具有计算思维的IT人应该知道的元认知）

层次三，不用递推，直接用以n为变量显示地定义（计算）第n个斐波那契数的代数表达式，即斐波那契数通项公式（数学知识）就可以突破溢出问题（当然，也可以利用数组模拟加法长式计算来实现不受硬件环境影响的斐波那契数算法）

【作者感受】

斐波那契数列基本是每本程序设计语言，数据结构或算法教材必有的例题，因为它来源一个数学公式（公式不复杂，没有学习难度，关键是还有现实实用价值，可以说是完美的例题来源），求解斐波那契数列的算法，可以不断优化，这对初学者感受“算法之美”是很有冲击力的。

求解斐波那契数列的程序可以从递归优化到迭代，还涉及计算机表示的变量的“溢出”这一计算机运行的独特现象。

简单说，斐波那契数列，教材喜欢用，教师喜欢用，初学者也喜欢学，而且这个看起来简单的东西，其实深究起来，对编程高手都有不断品味的价值。