спецификация Фибоначчи c генератор чисел python - PullRequest
Новая
       20

спецификация Фибоначчи c генератор чисел python

1 голос
/ 09 марта 2020

Есть ли способ показать число Фибоначчи 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))

Ответы [ 4 ]

9 голосов
/ 09 марта 2020

Наивным подходом было бы сгенерировать все n чисел Фибоначчи и вернуть последний элемент, который занимает O(n) времени. Вы можете вычислить N th число Фибоначчи в O(1) (при условии, что math.pow занимает O(1) время), используя формулу B inet.

B inet Формула: 

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

Где 

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

Математическое доказательство и калькулятор здесь.

2 голосов
/ 09 марта 2020

Преобразовать результат fib() в список и индексировать его в -1: 

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

>> Enter N Number: 15
>> [610]
1 голос
/ 30 марта 2020

Вы можете вычислить число N-го Фибоначчи, используя рекурсию с памяткой

Почему?

Например: представьте, что вы должны вычислять fibonacci(5), поэтому вам нужно вычислить fibonacci(4) и fibonacci(3). Но теперь для fibonacci(4) вам нужно вычислить fibonacci(3) и fibonacci(2) и так далее. Но подождите, когда вы закончите sh вычисления fibonacci(4) ветви, вы уже вычислили все Фибоначчи для 3 и 2, поэтому, когда вы go вернетесь к другой ветви (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 сек.

0 голосов
/ 09 марта 2020

Как указано в комментариях, ваша программа может быть использована для генерации N-го числа путем взятия последнего в последовательности, т. Е. 

list(fib(n))[-1]

. Однако существуют более эффективные программы для простого генерирования N-го числа Фибоначчи. как обсуждено здесь

Одним из таких примеров является шестая программа из этого источника, а именно: 

# 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)

Вывод 

34

Преимущество перед отправленным кодом

Преимуществом этого подхода является сложность O (log (n)) для n-го числа Фибоначчи, тогда как опубликованная код из вопроса имеет сложность O (n).

...