斐波那契特定数字生成器 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 + bprint(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 math

def fib(n):

    phi=1.61803398874989484820

    return round(((math.pow(phi,n))-(math.pow(-(1-phi),n)))/math.sqrt(5))

fib(15)

# 610

fib(10)

# 55

数学证明和计算器在这里。

Answer 2

将 的结果转换为列表，并在 以下位置为其编制索引：fib()-1

print(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)dictTrue

class memoize:

    def __init__(self, function):

        self.f = function

        self.memory = {}

    def __call__(self, *args):

        if args in self.memory:

            return self.memory[args]

        else:

            value = self.f(*args)

            self.memory[args] = value

            return value

@memoize

def fib(n):

  if n <= 1:

    return n

  else:

    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 

@lru_cache() 

def fib(n): 

    if n <= 1: 

        return n 

    return fib(n-1) + fib(n-2)

print(fib(300))

# 222232244629420445529739893461909967206666939096499764990979600

奖金：

$> %timeit fib(300)                                                        

78.2 ns ± 0.453 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)