斐波那契数列在Python中的几种实现

练习

Posted by UlyC on June 15, 2018

把一条线分成两部分,其中一部分对于全部之比等于另一部分对于该部分之比,这,就是黄金分割. ———王者荣耀.诸葛亮

斐波那契数列在Python中的几种实现

斐波那契数列(意大利语:Successione di Fibonacci),又译为费波拿契数列、费波那西数列、斐波那契数列、黄金分割数列。

在数学上,费波那契数列是以递归的方法来定义:

F_{0}=0 F_{1}=1} F_{1}=1 F_{n}=F_{n-1}+F_{n-2}} F_{n}=F_+F_(n≧2) 用文字来说,就是费波那契数列由0和1开始,之后的费波那契系数就是由之前的两数相加而得出。首几个费波那契系数是:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……(OEIS中的数列A000045)

特别指出:0不是第一项,而是第零项。

练习斐波那契数列有助于理解迭代器和生成器,写了几种实现如下:

1. 使用for循环

# 1.for


def fibo_seq_for(n):
    f = [1, 1]
    if n > 2:
        for i in range(n-2):
            res = f[i] + f[i+1]
            f.append(res)
        return f
    else:
        return f

2.使用递归函数

# 2. recursive


def fibo_seq_rec(n):
    if n < 2:
        return n
    return fibo_seq_rec(n-1) + fibo_seq_rec(n-2)  

3.使用迭代器

# 3.Iterator


class Fibo_seq_rec_iter(object):
    def __init__(self, n):
        self.n = n
        self.num1 = 0
        self.num2 = 1
        self.i = 0

    def __iter__(self):
        return self

    def __next__(self):
        if self.i < self.n:
            self.num1, self.num2 = self.num2, self.num2 + self.num1
            self.i += 1
            return self.num1
        else:
            raise StopIteration

4.使用生成器

# 4.Generator


def fi_g(n):
    n1 = 0
    n2 = 1
    i = 0
    while i < n:
        n1, n2 = n2, n1 + n2
        i += 1
        yield n1

斐波那契数列还有很多有意思的故事和用处,附上一篇知乎的优秀回答:斐波那契数列为什么那么重要,所有关于数学的书几乎都会提到? - 王希的回答 - 知乎


知识共享许可协议
本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。