斐波那契特定数字生成器 python

Question

有没有办法显示^第N个斐波那契数列？例如，我想要第15^个斐波那契数列，但这只给出了一个列表。

a = int(input('Enter N Number: '))

def fib(n):

    a = b = 1

    for i in range(n):

        yield a

        a, b = b, a + b

print(fib(a))

Answer 1

一种幼稚的方法是生成所有n个斐波那契数列并返回最后一个需要时间的元素。您可以使用Binet公式计算第N个斐波那契数列（假设需要时间）。O(n)O(1)math.powO(1)比奈公式：Fib(n) =(Phin − (−Phi)−n)/√5哪里Phi=(1+√5)/2= and -Phi=(1-√5)/2(1+√5)/2也被称为黄金比例。import mathdef fib(n):    phi=1.61803398874989484820    return round(((math.pow(phi,n))-(math.pow(-(1-phi),n)))/math.sqrt(5))fib(15)# 610fib(10)# 55数学证明和计算器在这里。

Answer 2

将 的结果转换为列表，并在 以下位置为其编制索引：fib()-1print(list(fib(a))[-1]) >> Enter N Number: 15 >> [610]

Answer 3

您可以使用递归和记忆来计算第N个斐波那契数列为什么？例如：假设您要计算，因此您需要计算和.但是现在，对于你需要计算和，等等。但是等等，当你完成计算分支时，你已经计算了3和2的所有斐波那契，所以当你从第一个递归调用回到另一个分支（）时，你已经计算了它。那么，如果有一种方法可以存储这些计算，以便我可以更快地访问它们，该怎么办？您可以使用装饰器来创建一个memoize类（某种内存以避免重复计算）：fibonacci(5)fibonacci(4)fibonacci(3)fibonacci(4)fibonacci(3)fibonacci(2)fibonacci(4)fibonacci(3)这样，我们将把每个计算都存储在 a 上，每次调用之前，我们都会检查它是否存在于字典上，如果返回，或者计算它。这种方式更快，更准确。fibonacci(k)dictTrueclass memoize:&nbsp; &nbsp; def __init__(self, function):&nbsp; &nbsp; &nbsp; &nbsp; self.f = function&nbsp; &nbsp; &nbsp; &nbsp; self.memory = {}&nbsp; &nbsp; def __call__(self, *args):&nbsp; &nbsp; &nbsp; &nbsp; if args in self.memory:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return self.memory[args]&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; value = self.f(*args)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self.memory[args] = value&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return value@memoizedef fib(n):&nbsp; if n <= 1:&nbsp; &nbsp; return n&nbsp; else:&nbsp; &nbsp; return fib(n-1) + fib(n-2)r = fib(300)print(r)输出：222232244629420445529739893461909967206666939096499764990979600它只花了几秒钟。0.2716239

Answer 4

发布的答案的另一种方法是使用内置函数中的memoization概念lru_cache这是一个：装饰器，用于使用记忆可调用来包装函数，该可调用将最大大小保存到最大最近的调用。当使用相同的参数定期调用昂贵的或 I/O 绑定的函数时，它可以节省时间。from functools import lru_cache&nbsp;@lru_cache()&nbsp;def fib(n):&nbsp;&nbsp; &nbsp; if n <= 1:&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; return n&nbsp;&nbsp; &nbsp; return fib(n-1) + fib(n-2)print(fib(300))# 222232244629420445529739893461909967206666939096499764990979600奖金：$> %timeit fib(300)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;78.2 ns ± 0.453 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)