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

Метод 1: рекурсивная функция
Самый простой и интуитивно понятный способ создания последовательности Фибоначчи — использование рекурсивной функции. Функция вызывает себя для вычисления суммы двух предыдущих чисел, пока она не достигнет базового случая.

def fibonacci_recursive(n):
    if n <= 1:
        return n
    else:
        return (fibonacci_recursive(n-1) + fibonacci_recursive(n-2))
# Example usage
print(fibonacci_recursive(10))

Метод 2: итеративный подход
Альтернативой рекурсивной функции является итеративный подход, который использует цикл для итеративного вычисления последовательности Фибоначчи.

def fibonacci_iterative(n):
    if n <= 1:
        return n
    fib_sequence = [0, 1]
    for i in range(2, n+1):
        fib_sequence.append(fib_sequence[i-1] + fib_sequence[i-2])
    return fib_sequence[n]
# Example usage
print(fibonacci_iterative(10))

Метод 3: Мемоизация
Мемоизация – это метод, при котором сохраняются ранее рассчитанные результаты, чтобы избежать избыточных вычислений. Используя мемоизацию, мы можем значительно оптимизировать рекурсивный подход.

fib_cache = {}
def fibonacci_memoization(n):
    if n in fib_cache:
        return fib_cache[n]
    if n <= 1:
        return n
    fib_cache[n] = fibonacci_memoization(n-1) + fibonacci_memoization(n-2)
    return fib_cache[n]
# Example usage
print(fibonacci_memoization(10))

Метод 4: матричное возведение в степень
Другим эффективным подходом является использование матричного возведения в степень. Этот метод использует свойства матриц для вычисления чисел Фибоначчи с логарифмической временной сложностью.

import numpy as np
def fibonacci_matrix(n):
    matrix = np.array([[1, 1], [1, 0]], dtype=object)
    result = np.linalg.matrix_power(matrix, n)
    return result[0][1]
# Example usage
print(fibonacci_matrix(10))

В этой статье мы рассмотрели различные методы расчета последовательности Фибоначчи в Python. Мы обсудили рекурсивный подход, итеративный подход, мемоизацию и возведение матрицы в степень. Каждый метод имеет свои преимущества и недостатки с точки зрения временной сложности и эффективности использования пространства. В зависимости от конкретного варианта использования один метод может оказаться более подходящим, чем другие.