все Python 3Алгоритмы и структуры данныхпонятие

Числа Фибоначчи

математика

F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Итеративно O(n), рекурсивно O(2^n), с lru_cache O(n).

Синтаксис

def fib(n): ...

Наивная рекурсия пересчитывает одни и те же значения заново: fib(35) считается секунды, а fib(50) можно не дожидаться — одна строка @lru_cache(maxsize=None) над функцией снимает проблему. У рекурсии есть и второй потолок: около тысячи вложенных вызовов, дальше RecursionError, поэтому для больших n берут цикл, а не память. Формула Бине через float начинает врать примерно с n=71, тогда как целочисленный цикл точен при любом n — у Python длинная арифметика без переполнения.

Примеры

# Итеративно — O(n)
def fib_iter(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a+b
    return b
print([fib_iter(i) for i in range(10)])  # → [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

# Рекурсивно — O(2^n) (медленно!)
def fib_rec(n):
    if n <= 1: return n
    return fib_rec(n-1) + fib_rec(n-2)
print(fib_rec(10))  # → 55 (для малых n)

# С lru_cache — O(n) + мемоизация
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1: return n
    return fib_memo(n-1) + fib_memo(n-2)
print(fib_memo(50))  # → 12586269025

# Генератор Фибоначчи
from itertools import islice
def fib_gen():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a+b
print(list(islice(fib_gen(), 10)))  # → [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
# Матричный метод O(log n)
def mat_mul(A, B):
    return [
        [A[0][0]*B[0][0]+A[0][1]*B[1][0], A[0][0]*B[0][1]+A[0][1]*B[1][1]],
        [A[1][0]*B[0][0]+A[1][1]*B[1][0], A[1][0]*B[0][1]+A[1][1]*B[1][1]],
    ]
def mat_pow(M, n):
    if n == 1: return M
    if n % 2 == 0:
        half = mat_pow(M, n//2)
        return mat_mul(half, half)
    return mat_mul(M, mat_pow(M, n-1))
def fib_matrix(n):
    if n == 0: return 0
    return mat_pow([[1, 1], [1, 0]], n)[0][1]
print(fib_matrix(10))  # → 55

# Числа Фибоначчи, не превышающие N
def fib_until(n):
    a, b = 0, 1
    result = []
    while a <= n:
        result.append(a)
        a, b = b, a+b
    return result
print(fib_until(100))  # → [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

См. также

Открыть в полном глоссарииdocs.python.orgСообщить о неточности