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

Question

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

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 个数字，即

list(fib(n))[-1]

但是，如所讨论的那样，有更高效的程序可以仅生成第 N 个斐波那契数 here

一个这样的例子是来自该来源的第 6 个程序，即：

# Python 3 Program to find n'th fibonacci Number in 
# with O(Log n) arithmatic operations 
MAX = 1000

# Create an array for memoization 
f = [0] * MAX

# Returns n'th fuibonacci number using table f[] 
def fib(n) : 
    # Base cases 
    if (n == 0) : 
        return 0
    if (n == 1 or n == 2) : 
        f[n] = 1
        return (f[n]) 

    # If fib(n) is already computed 
    if (f[n]) : 
        return f[n] 

    if( n & 1) : 
        k = (n + 1) // 2
    else :  
        k = n // 2

    # Applyting above formula [Note value n&1 is 1 
    # if n is odd, else 0. 
    if((n & 1) ) : 
        f[n] = (fib(k) * fib(k) + fib(k-1) * fib(k-1)) 
    else : 
        f[n] = (2*fib(k-1) + fib(k))*fib(k) 

    return f[n] 


# Driver code 
n = 9
print(fib(n)

输出

相对于已发布代码的优势

这种方法的优点是第 n 个斐波那契数的复杂度为 O(log(n))，而问题中发布的代码的复杂度为 O(n) .

Answer 3

一种天真的方法是生成所有 n 斐波那契数和 return 最后一个元素，这需要 O(n) 时间。您可以在 O(1) 中计算 N^thFibonacci 数 （假设 math.pow 需要 O(1) 时间）使用 Binet's Formula.

比奈公式：

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

在哪里

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

数学证明与计算器here.

Answer 4

您可以使用 memoization

的递归计算第 N 个斐波那契数

为什么？

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

这样我们将把 fibonacci(k) 的每个计算存储在 dict 上，并且我们会在每次调用之前检查它是否存在于字典中，return 如果 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 秒。

Answer 5

@DarK_FirefoX 使用 memoization within the built-in function lru_cache 的概念发布的答案的另一种方法是：

Decorator to wrap a function with a memoizing callable that saves up to the maxsize most recent calls. It can save time when an expensive or I/O bound function is periodically called with the same arguments.

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)

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

fibonacci specific number generator python

python

list

fibonacci

python-3.x