斐波那契数列的四种实现
source link: https://zhuanlan.zhihu.com/p/104862616
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
斐波那契数列的四种实现
孔乙己自己知道不能和他们谈天，便只好向 Intern 说话。有一回对我说道，“你写过代码么？”我略略点一点头。他说，“写过代码，……我便考你一考。斐波那契数列的输出，怎样实现？”我想，讨饭一样的人，也配考我么？便回过脸去，不再理会。孔乙己等了许久，很恳切的说道，“不能写罢？……我教给你，记着！这些代码应该记着。将来做 Leader 的时候，开发项目要用。”我暗想我和 Leader 的等级还很远呢，而且我们 Leader 也从不在项目里写斐波那契；又好笑，又不耐烦，懒懒的答他道，“谁要你教，不是递归么？”孔乙己显出极高兴的样子，将两个指头的长指甲敲着键盘，点头说，“对呀对呀！……斐波那契有四样写法，你知道么？”我愈不耐烦了，努着嘴走远。孔乙己刚在命令行打开 Vim，想在里面写代码，见我毫不热心，便又叹一口气，显出极惋惜的样子。
（改编自 鲁迅《孔乙己》）
在家闲着也是闲着，不如我们来看看，如何写一个输出斐波那契数列的代码吧。
先说下，什么是斐波那契数列？
斐波那契（Fibonacci）数列，又称黄金分割数列，因数学家列昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：
1、1、2、3、5、8、13、21、34……
在数学上，斐波那契数列以如下被以递推的方法定义：
F(1) = 1
F(2) = 1
F(n) = F(n - 1) + F(n - 2) （n ≥ 3，n ∈ N*）
简单来讲就是：数列中某一项的值，等于它的前一项加上前前一项的和。
在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。（摘自 百度百科）
我曾经也把手写斐波那契作为面试题之一。
1. 递归
在编程教程中提到斐波那契数列，通常都是用来讲解递归函数。当一个关于 N 的问题可以转换为关于 N - k 的同样问题时，它就可以尝试用递归的思路来解决。
def fib_1(n):
if n <= 1:
return 1
return fib_1(n-1) + fib_1(n-2)
for i in range(20):
print(fib_1(i), end=' ')2. 循环
但斐波那契并非一定要用递归实现。事实上，所有的递归都可以用循环来实现。
def fib_2(n):
a, b = 0, 1
for i in range(n):
print(b, end=' ')
a, b = b, a + b
fib_2(20)3. 生成器
用生成器的思路本质来说和上面的循环是一样的，只是实现的时候用了 yield。
def fib_3(n):
a, b = 0, 1
while n > 0:
yield b
a, b = b, a + b
n -= 1
for i in fib_3(20):
print(i, end=' ')4. 矩阵相乘
此方法的原理是利用二阶矩阵的相乘：
import numpy as np
def fib_4(n):
for i in range(n):
res = pow(np.matrix([[1, 1], [1, 0]], dtype='int64'), i) * np.matrix([[1], [0]])
print(int(res[0][0]), end=' ')
fib_4(20)上述 4 种方法的输出结果都是：
斐波那契数列的实现方法并不仅这 4 种。如果你有其他的实现，欢迎在留言中补充。
------
一起学，走得远！
欢迎搜索：Crossin的编程教室
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK