斐波那契數列的5種python寫法 斐波那契數列（Fibonacci sequence），又稱黃金分割數列、因數學家 列昂納多·斐波那契 （Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”， ...
斐波那契數列的5種python寫法
斐波那契數列（Fibonacci sequence），又稱黃金分割數列、因數學家列昂納多·斐波那契（Leonardoda 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>=2，n∈N*）
斐波那契數列，難點在於演算法，還有如果變成生成器，generator，就要用for迴圈去遍歷可迭代的generator
第一種 遞歸法
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=' ')寫法最簡潔，但是效率最低，會出現大量的重覆計算，時間複雜度O（1.618^n）,而且最深度1000
第二種 遞推法
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=' ')遞推法，就是遞增法，時間複雜度是 O(n)，呈線性增長，如果數據量巨大，速度會越拖越慢
第三種 生成器
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(10):
print(i, end=' ')帶有yield的函數都被看成生成器，生成器是可迭代對象，且具備__iter__ 和 __next__方法， 可以遍歷獲取元素
第四種 類實現內部魔法方法
class Fibonacci(object):
def __init__(self, num):
self.num = num
def __iter__(self):
if self.num < 1:
return 1
a, b = 0, 1
while self.num > 0:
a, b = a + b, a
self.num -= 1
yield a
def __next__(self):
return self.__iter__()
f = Fibonacci(15)
for i in f:
print(i)第五種 矩陣
### 1
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)因為冪運算可以使用二分加速，所以矩陣法的時間複雜度為 O(log n)
用科學計算包numpy來實現矩陣法 O(log n)
