python - 斐波那契特定数字生成器 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) 时间。您可以在 O(1) 内计算第 N斐波那契数(假设 math.pow 需要 O (1) 时间)使用 Binet's Formula.

比奈公式:

<b>Fib(n) =(Phi<sup>n</sup> − (−Phi)<sup>−n</sup>)/√5</b>

哪里

• Phi=(1+√5)/2= 和 -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

数学证明和计算器 here.