# 定义

[ F_0 = 0\;F_1 =1\;F_i = F_{i-1} + F_{i-2}\;当i \geq 2]

# 递归解法

def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)



# 循环写法，cache结果

def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
elif n == 2:
return 1
else:
n2 = 0
n1 = 1
r = 1
while n > 2:
n2 = n1
n1 = r
r = n2 + n1
n -= 1
return r


# 利用数学结果1

[F_i = \frac{\phi^i-\hat\phi^i}{\sqrt{5}}, 其中\phi=\frac{1+\sqrt{5}}{2}, \hat\phi=\frac{1-\sqrt{5}}{2}]

# 利用数学结果2

[ \begin{pmatrix}
F_{n+1} & F_n \
F_n & F_{n-1}
\end{pmatrix} =
\begin{pmatrix}
1 & 1 \
1 & 0
\end{pmatrix}^n
]

def fib(n):
if n == 0:
return 0
elif n == 1:
return 1

class metrix:
def __init__(self, i1, i2, j1, j2):
self.i1 = i1
self.i2 = i2
self.j1 = j1
self.j2 = j2

def mul(self, another):
i1 = self.i1 * another.i1 + self.i2 * another.j1
i2 = self.i1 * another.i2 + self.i2 * another.j2
j1 = self.j1 * another.i1 + self.j2 * another.j1
j2 = self.j1 * another.i2 + self.j2 * another.j2
return metrix(i1, i2, j1, j2)

def __str__(self):
return "(i1=%ld,i2=%ld,j1=%ld,j2=%ld)" % (
self.i1, self.i2, self.j1, self.j2)

@staticmethod
def mulmetirx(a, b):
return a.mul(b)

def metrix_power(x, n):
if n == 0:
return 1
elif n == 1:
return x
else:
return metrix.mulmetirx(metrix_power(x, int(n/2)),
metrix_power(x, n-int(n/2)))
base = metrix(1, 1, 1, 0)
result = metrix_power(base, n)
return result.i2


Tags: