斐波那契特定数字生成器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 个斐波那契数并返回最后一个需要O(n)时间的元素。你可以计算ň^个Fibonacci数的O(1)（假设math.pow需要O(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

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