关于python:斐波那契数列的四种实现

46次阅读

共计 1438 个字符,预计需要花费 4 分钟才能阅读完成。

孔乙己本人晓得不能和他们谈天,便只好向 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 种办法的输入后果都是:



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

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

——

一起学,走得远!

欢送搜寻:Crossin 的编程教室

正文完
 0