Закрытая форма Серия Фибоначчи

Я использую Python для создания Фибоначчи по этой формуле:

введите здесь описание изображения

У меня есть эта рекурсивная функция Фибоначчи:

def recursive_fibonacci(n):
if n <= 1:
    return int((((1 / (5 ** 0.5)) * (1 + (5 ** 0.5))) ** n) - (((1 / (5 ** 0.5)) * (1 - (5 ** 0.5))) ** n))
else:
    return(recursive_fibonacci(n - 1) + recursive_fibonacci(n - 2))

Чтобы отобразить это, я использую это:

nterms = 10

if nterms <= 0:
    print("Please Enter a positive integer")
else:
    print("Recursive Fibonacci Sequence: " ,
        [recursive_fibonacci(i) for i in range(nterms)])
    print("Iterative Fibonacci Sequence: " ,
        [iterative_fib(i) for i in range(nterms)])

Как бы я использовал итеративную функцию с этим Фибоначчи?

Я пробовал использовать это:

def iterative_fib(n):
    equation = lambda n: int((((1 / (5 ** 0.5)) * (1 + (5 ** 0.5))) ** n) - (((1 / (5 ** 0.5)) * (1 - (5 ** 0.5))) ** n))
    if n <= 1:
        return equation(n)
    else:
        a, b = 1, 2
        for i in range(n):
            fn = equation((i-a)+(i-b))
        return fn

Однако эта итеративная функция, похоже, не имеет того же результата, что и рекурсивная функция.

Вывод рекурсивной функции:

Recursive Fibonacci Sequence:  [0, 2, 2, 4, 6, 10, 16, 26, 42, 68]

Вывод итерационной функции:

Iterative Fibonacci Sequence:  [0, 2, 2, 2, 3, 6, 13, 27, 58, 122]

python recursion iteration fibonacci
person Roman Roshchuk    schedule 11.11.2018    source источник
comment
Если у вас есть формула, зачем вам рекурсия или итерация?   -  person Scott Hunter    schedule 11.11.2018
comment
Я думаю (@Roman поправьте меня, если я ошибаюсь), он хочет напечатать все значения f(n), начиная с 0 до n. Вот почему он повторяется.   -  person Sanchit Kumar    schedule 11.11.2018

Ответы (2)


arrow_upward
2
arrow_downward

Уравнение, которое вы пытаетесь реализовать, представляет собой закрытую форму ряд Фибоначчи.

Закрытая форма означает, что оценка является операцией с постоянным временем.

g = (1 + 5**.5) / 2  # Golden ratio.
def fib(N):
    return int((g**N - (1-g)**N) / 5**.5)

Контраст с,

def fib_iterative(N):
    a, b, i = 0, 1, 2
    yield from (a, b)
    while i < N:
        a, b = b, a + b 
        yield b
        i += 1

And we have 

>>> [fib(n) for n in range(10)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
>>> list(fib_iterative(10))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
person cs95    schedule 11.11.2018

arrow_upward
1
arrow_downward

Я думаю, вы неправильно поняли выражение f_n для последовательности Фибоначчи, которое вы упомянули.

Обратите внимание, что это не рекуррентное отношение. Это функция от n, т. е. она предоставляет значение n-го члена, когда задано n.

Следовательно, у вас действительно нет рекурсивного/итеративного решения для создания всей последовательности Фибонначи здесь.

Подстановка n вместо 0, 1, 2, 3.. дает члены ряда 0, 1, 1, 2, ...

Для иллюстрации, когда n = 3, f_3 рассчитывается как - введите здесь описание изображения

person Shash    schedule 11.11.2018