Python各种方式计算斐波那契数列
斐波那契数列是一个超级神奇的数列！
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。 ——摘自百度百科（baike.baidu.com）
斐波那契数列指的是这样一个数列：
这个数列从第3项开始，每一项都等于前两项之和。
下面我写出所有我知道的能生成斐波那契数列的方法：
递归
def rec(n):
if n <= 0:
return 0
elif n == 1:
return 1
return rec(n - 1) + rec(n - 2)
print(list(map(rec, range(1, 11))))
交换变量
a, b = 0, 1
for i in range(3, 11):
print(b)
a, b = b, a + b
矩阵快速幂运算
A = [
[1, 1],
[1, 0]
]
start = [
[1, 0]
]
def mat(m1, m2):
res = [[0 for i in range(len(m2[0]))] for j in range(len(m1))]
for i in range(len(m1)):
for j in range(len(m2[0])):
for k in range(len(m1[0])):
res[i][j] += m1[i][k] * m2[k][j]
return res
def quickMat(m1, n):
res = [[0] * len(m1[0]) for i in range(len(m1))]
for i in range(len(res)):
res[i][i] = 1
tmp = m1.copy()
while n != 0:
if n & 1 != 0:
res = mat(res, tmp)
tmp = mat(tmp, tmp)
n = n >> 1
return res
def getFibonacci(n):
return mat(start, quickMat(A, n - 1))[0][0]
print(list(map(getFibonacci, range(1, 11))))