有趣的算法-斐波那契数列

斐波那契数列（Fibonacci sequence） 1 1 2 3 5 8 13 21 34 55 89 ...

斐波那契数列也称为神秘数列，从第三项开始，各个数列之间相互之间维持着固定的比率，每一项都等于前两项的和。

斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2) （n ≥ 3，n ∈ N*）。

从第三项开始，前一项除以后一项的值会越来越接近0.618这个黄金分割比例。黄金分割也是从斐波那契数列演变而来。

据说，达芬奇著名的蒙娜丽莎，就是符合斐波那契曲线构图的。

据说，很多植物的特征和自然界中都暗合斐波那契数的规律。

使用Scratch求n项斐波那契数列如下：（前20项斐波那契数列放入列表中显示）

Python求解如下：

# 1.递推方法 比递归效率高
a, b = 0, 1
for num in range(1, 101):
    a, b = b, a+b
    print(num, a)

递归方法虽然逻辑清晰，实现相对容易，但是执行上空间复杂度和时间复杂度较高，容易爆函数栈，有兴趣可以查阅相应资料。

# 2.递归方式  效率比较低 如果不优化 计算到100 可能就要5000亿年

def fib(n):
    if n in (1, 2):  # 如何n为第一项或者第二项返回值 1
        return 1
    return fib(n-1)+fib(n-2)

for i in range(1,101):
    print(i, fib(i))

# 3.递归方式优化 用一个字典来存储已经得出的数值 执行效率大为提高，只是相对于递推方式需要额外空间存储已经算出来的值

def fib(n,temp={}):
    if n in (1,2):
        return 1
    if n not in temp:
        temp[n] = fib(n-1)+fib(n-2)
    return temp[n]

for i in range(1,101):
    print(i, fib(i))

---

分享