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

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

Описание

Последовательность Фибоначчи — это классическая задача программирования, где каждое число равно сумме двух предыдущих. Это отличный пример для демонстрации различных подходов к решению: от наивного рекурсивного решения до оптимизированных методов.

Решение 1: Рекурсивный подход (простой, но неэффективный)

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

# Примеры
print(fib(0))   # 0
print(fib(1))   # 1
print(fib(6))   # 8
print(fib(10))  # 55

Проблемы: временная сложность O(2^n), многократное вычисление одних и тех же значений.

Решение 2: Рекурсия с мемоизацией (оптимальный баланс)

def fib(n, memo=None):
    if memo is None:
        memo = {}
    
    if n in memo:
        return memo[n]
    
    if n <= 1:
        return n
    
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

# Или с использованием decorator
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Преимущества: O(n) временная сложность, ясная рекурсивная логика.

Решение 3: Итеративный подход (самый эффективный)

def fib(n):
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    
    return curr

# Примеры
print(fib(0))   # 0
print(fib(1))   # 1
print(fib(6))   # 8
print(fib(10))  # 55

Преимущества: O(n) время, O(1) память, очень быстро.

Решение 4: Динамическое программирование (табуляция)

def fib(n):
    if n <= 1:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

Преимущества: явное динамическое программирование, легко понять логику.

Решение 5: Матричное возведение в степень (для больших n)

def matrix_mult(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 matrix_pow(matrix, n):
    if n == 1:
        return matrix
    
    if n % 2 == 0:
        half = matrix_pow(matrix, n // 2)
        return matrix_mult(half, half)
    else:
        return matrix_mult(matrix, matrix_pow(matrix, n - 1))

def fib(n):
    if n <= 1:
        return n
    
    base_matrix = [[1, 1], [1, 0]]
    result = matrix_pow(base_matrix, n)
    return result[0][1]

Преимущества: O(log n) временная сложность, подходит для очень больших n.

Сравнение подходов

Рекомендуемое решение

Для интервью рекомендуется итеративный подход — он показывает понимание проблемы, является эффективным и кратким:

def fib(n: int) -> int:
    """Возвращает n-ое число Фибоначчи за O(n) время и O(1) память."""
    if n <= 1:
        return n
    
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    
    return b