fibonacci.md

Вычисление n-числа Фибоначчи

| Главная | Алгебра |

Числа Фибоначчи (вариант написания — Фибоначи) — элементы числовой последовательности, в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи).

Формула вычисления {F_n} задаётся линейным рекуррентным соотношением:

F0 = 0	F1 = 1	Fn = Fn - 1 + Fn - 2

Реализация

• С использованием дополнительной памяти

Время	Память
O(n)	O(n)

def fib(n):
    seq = [0, 1, 1]    
    if n < 3:
        return seq[n]
    for i in range(3, n + 1):
        seq.append(seq[i - 1] + seq[i - 2])
    return seq[n]


print(fib(5)) 

• Без использования дополнительной памяти

Время	Память
O(n)	O(1)

def fib(n):    
    if n == 0:
        return 0
    x1 = 1
    x2 = 1
    for i in range(3, n + 1):
        x1, x2 = x2, x1 + x2
    return x2


print(fib(5))