斐波那契数列通项的Python实现
斐波那契数列的递推定义
序列
https://gitee.com/hrh233/my-pics/raw/master/pics/fib1.jpg
称为斐波那契数列
由此定义,我们可以得出一个简单的Python程序
def fibonacci_1(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci_1(n - 1) + fibonacci_1(n - 2)
利用lambda表达式略微简化代码可得
fibonacci_2 = (lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args))))(
lambda f: lambda n: 0 if n == 0 else (1 if n == 1 else f(n - 1) + f(n - 2))
)
当你使用了这个函数,你会发现当输入数据过大会导致内存溢出,因为函数的递归调用会占用大量的内存,所以我们需要一种方法来避免这种问题
明显公式
除递推定义外,有一个斐波那契数列的明显公式
https://gitee.com/hrh233/my-pics/raw/master/pics/fib2.jpg
由此,我们能给出简单的代码
import math
def fibonacci_3(n):
return (math.sqrt(5) / 5) * (
((1 + math.sqrt(5)) / 2) ** n - ((1 - math.sqrt(5)) / 2) ** n
)
当你使用时,你会发现输出的并不是整数，这是常见的浮点数精度bug;同时,我们会发现当数据很大时会出现OverFlow Error,因此代码需要完善,比如:
import decimal
def fibonacci_4(n):
decimal.getcontext().prec = 1000 # 这里精度越大程序越精确,相应地,占用和速度也会收到影响
s5 = decimal.Decimal(5).sqrt()
result = (s5 / 5) * (((1 + s5) / 2) ** n - ((1 - s5) / 2) ** n)
result = int(round(result, 0))
return result
这样我们就用decimal库解决了精度问题,同时,我们使用round函数将结果四舍五入,这样就能够输出更好的结果了.
矩阵快速幂
很明显地,当n特别巨大时,像前面那样计算会非常缓慢,因此,我们需要使用矩阵快速幂来计算,这样,时间复杂度就能变为O(logn),能在短时间内计算出结果,就像这样:
class Matrix:
def __init__(self, a, b, c, d):
self.a = a
self.b = b
self.c = c
self.d = d
def __mul__(self, other):
return Matrix(
self.a * other.a + self.b * other.c,
self.a * other.b + self.b * other.d,
self.c * other.a + self.d * other.c,
self.c * other.b + self.d * other.d,
)
def fast_power(A, n):
if n == 0:
return Matrix(1, 0, 0, 1)
elif n == 1:
return A
elif n % 2 == 0:
return fast_power(A * A, n // 2)
else:
return A * fast_power(A * A, (n - 1) // 2)
def fibonacci_5(n):
if n < 0:
return "Invalid input"
elif n == 0:
return 0
elif n == 1:
return 1
else:
A = Matrix(0, 1, 1, 1)
return fast_power(A, n).b
发表于 2023-8-7 14:43
