1. 斐波那契数列应用广泛,对此数列的更好理解有助于我们算法的更进一步,并降低程序的时间复杂度,提高运行效率.
2. 斐波那契数列的应用(4种):
2.1 排列组合----经典例子:爬楼梯
"""
有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第10级台阶有几种不同的走法?
这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种登法……
1，2，3，5，8，13……所以，登上十级，有89种走法。
类似的，一枚均匀的硬币掷10次，问不连续出现正面的可能情形有多少种？
答案是（1/√5)*{[(1+√5)/2]^(10+2) - [(1-√5)/2]^(10+2)}=144种。
求递推数列a⑴=1，a(n+1)=1+1/a(n）的通项公式
由数学归纳法可以得到：a(n)=F(n+1)/F(n），将斐波那契数列的通项式代入，化简就得结果。
"""
2.2 兔子数列----兔子繁殖问题
"""
斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。
一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？
我们不妨拿新出生的一对小兔子分析一下：
第一个月小兔子没有繁殖能力，所以还是一对
两个月后，生下一对小兔对数共有两对
三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对 幼仔对数=前月成兔对数
成兔对数=前月成兔对数+前月幼仔对数
总体对数=本月成兔对数+本月幼仔对数
可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点，那是：前面相邻两项之和，构成了后一项。
这个数列是意大利中世纪数学家斐波那契在<算盘全书>中提出的，这个级数的通项公式，除了具有a(n+2)=an+a(n+1)的性质外，
还可以证明通项公式为：an=(1/√5)*{[(1+√5)/2]^n-[(1-√5)/2]^n}（n=1,2,3,...）
"""
2.3 数列与矩阵(现在的我暂时用不上)
"""
对于斐波那契数列1、1、2、3、5、8、13、……。有如下定义
F(n)=F(n-1)+F(n-2)
F(1)=1
F(2)=1
对于以下矩阵乘法
F(n+1) = (1,1 ) (F(n),F(n-1))T
F(n) =(1,0 ) (F(n),F(n-1))T
它的运算就是右边的矩阵 (1,1)乘以矩阵(F(n),F(n-1))，右边的矩阵(1,0 ) 乘以矩阵(F(n),F(n-1))，得到：
F(n+1)=F(n)+F(n-1)
F(n)=F(n)
可见该矩阵的乘法完全符合斐波那契数列的定义
设矩阵A=第一行（1，1）第二行（1，0） 迭代n次可以得到：F(n+1) =A^(n) *（ F(2)，F(1))T= A^(n)*(1,1)T
这就是斐波那契数列的矩阵乘法定义。
另矩阵乘法的一个运算法则A^n(n为偶数) = A^(n/2)* A^(n/2)，这样我们通过二分的思想，可以实现对数复杂度的矩阵相乘。
因此可以用递归的方法求得答案。 数列值的另一种求法：
F(n) = [ (( sqrt ( 5 ) + 1 ) / 2) ^ n ]
其中[ x ]表示取距离 x 最近的整数。
"""
2.4 斐波那契弧线(暂时用不上)
"""
斐波那契弧线，也称为斐波那契扇形线。第一，此趋势线以二个端点为准而画出，例如，最低点反向到最高点线上的两个点。
然后通过第二点画出一条“无形的（看不见的）”垂直线。然后，从第一个点画出第三条趋势线：38.2%， 50%和61.8%的无形垂直线交叉。 斐波纳契弧线，是潜在的支持点和阻力点水平价格。斐波纳契弧线和斐波纳契扇形线常常在图表里同时绘画出。支持点和阻力点就是由这些线的交汇点得出。
要注意的是弧线的交叉点和价格曲线会根据图表数值范围而改变，因为弧线是圆周的一部分，它的形成总是一样的。
"""
绘制图形如右图:
3. 如何用代码求斐波那契数列(4种方法):
1).递归 效率最低,时间复杂度时间复杂度O（1.618^n）
def fib_recur(n):
assert n >= 0, "n > 0"
if n <= 1:
return n
return fib_recur(n-1) + fib_recur(n-2) for i in range(1, 20):
print(fib_recur(i), end=' ')
PS:递归 进阶版
使用lru_cache可减少重复计算.
from functools import lru_cache class Solution:
@lru_cache(10**8)
def climbStairs(self, n):
"""
:type n: int
:rtype: int
""" if n == 1:
return 1
elif n == 2:
return 2
else:
return self.climbStairs(n - 1) + self.climbStairs(n - 2)
2)循环 也是递推法,递增法,时间复杂度O(n)
def fib_loop(n):
a, b = 0, 1
for i in range(n+1):
a, b = b, a+b
return a for i in range(20):
print(fib_loop(i), end=' ')
3)生成器
def fib_loop_while(max):
a, b = 0, 1
while max > 0:
a, b = b, a+b
max -= 1
yield a for i in fib_loop_while(10):
print(i)
4)类实现内部魔法方法
class Fibonacci(object):
"""斐波那契数列迭代器""" def __init__(self, n):
"""
:param n:int 指 生成数列的个数
"""
self.n = n
# 保存当前生成到的数据列的第几个数据，生成器中性质，记录位置，下一个位置的数据
self.current = 0
# 两个初始值
self.a = 0
self.b = 1 def __next__(self):
"""当使用next()函数调用时，就会获取下一个数"""
if self.current < self.n:
self.a, self.b = self.b, self.a + self.b
self.current += 1
return self.a
else:
raise StopIteration def __iter__(self):
"""迭代器的__iter__ 返回自身即可"""
return self if __name__ == '__main__':
fib = Fibonacci(15)
for num in fib:
print(num)
5) 矩阵 时间复杂度为 O(log n) (矩阵的话不太好理解,需要先提高数学素养)
import numpy
def fib_matrix(n):
res = pow((numpy.matrix([[1, 1], [1, 0]])), n) * numpy.matrix([[1], [0]])
return res[0][0]
for i in range(10):
print(int(fib_matrix(i)), end=' ') ### 2
# 使用矩阵计算斐波那契数列
def Fibonacci_Matrix_tool(n):
Matrix = npmpy.matrix("1 1;1 0")
# 返回是matrix类型
return pow(Matrix, n) # pow函数速度快于 使用双星好 ** def Fibonacci_Matrix(n):
result_list = []
for i in range(0, n):
result_list.append(numpy.array(Fibonacci_Matrix_tool(i))[0][0])
return result_list
# 调用
Fibonacci_Matrix(10)
PS:因为幂运算可以使用二分加速，所以矩阵法的时间复杂度为 O(log n)
用科学计算包numpy来实现矩阵法 O(log n)
6) 公式求解 时间复杂度O(1)
首先,列出公式:
from math import sqrt
def fibonacci(n):
s = int(1/sqrt(5)*(pow(((1+sqrt(5))/2),n)-pow(((1-sqrt(5))/2),n)))
return s for i in range(10):
print(fibonacci(i))
转自:https://baike.baidu.com/item/斐波那契数列/99145?fr=aladdin#5
https://blog.csdn.net/JIEJINQUANIL/article/details/52422141
https://www.cnblogs.com/panlq/p/9307203.html
来自LeetCode的wikizero的回答