当前位置: 欣欣网 > 办公

斐波那契数列的四种实现

2024-07-07办公

孔乙己自己知道不能和他们谈天,便只好向 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 + bfib_2(20)

3. 生成器

用生成器的思路本质来说和上面的循环是一样的,只是实现的时候用了 yield

def fib_3(n): a, b = 0, 1 while n > 0: yield b a, b = b, a + b n -= 1for i in fib_3(20): print(i, end=' ')

4. 矩阵相乘

此方法的原理是利用二阶矩阵的相乘:

import numpy as npdef 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 种方法的输出结果都是:

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

斐波那契数列的实现方法并不仅这 4 种。如果你有其他的实现,欢迎在留言中补充。


作者:Crossin的编程教室

Crossin的新书【 码上行动:用ChatGPT学会Python编程 】已经上市了。 本书以ChatGPT为辅助,系统全面地讲解了如何掌握Python编程,适合Python零基础入门的读者学习。

购买后可加入读者交流群,Crossin为你开启陪读模式,解答你在阅读本书时的一切疑问。

添加微信 crossin123 ,加入编程教室共同学习 ~

感谢 转发 点赞 的各位~