斐波那契特定数生成器

Question

有没有办法显示N^thFibonacci数？e、 我想要第15个Fibonacci数，但这只是一个列表

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

将fib()的结果转换为列表，并将其索引到-1：

print(list(fib(a))[-1])

>> Enter N Number: 15
>> [610]

Answer 2

一种简单的方法是生成所有n斐波那契数并返回花费O(n)时间的最后一个元素。您可以使用Binet's Formula.

比奈公式：

^{pr1}$

在哪里

• Phi=(1+√5)/2= and -Phi=(1-√5)/2
• (1+√5)/2也称为Golden Ratio.

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 3

可以使用带memoization的递归计算第n个斐波那契数

为什么？

例如：假设您要计算fibonacci(5)，那么您需要计算fibonacci(4)和fibonacci(3)。但是现在，对于fibonacci(4)，您需要计算fibonacci(3)和fibonacci(2)，依此类推。但是等等，当您完成计算fibonacci(4)分支时，您已经计算了3和2的所有斐波那契，因此当您从第一个递归调用返回到另一个分支（fibonacci(3)）时，您已经计算了它。那么，如果有一种方法可以存储这些计算，以便更快地访问它们呢？您可以使用Decorators创建memoize类（某种内存以避免重复计算）：

这样，我们将把fibonacci(k)的每次计算都存储在dict上，每次调用之前我们都会检查它是否存在于字典中，如果True返回，或者计算它。这种方法更快、更准确

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秒