Последовательность Фибоначчи

Решение: Последовательность Фибоначчи

Описание задачи

Требуется реализовать функцию для вычисления N-го числа последовательности Фибоначчи (Fibonacci sequence). Последовательность Фибоначчи — это математическая последовательность, где каждое число является суммой двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34... Эта классическая задача часто встречается в алгоритмическом тестировании, демонстрирует понимание различных подходов оптимизации (рекурсия, динамическое программирование, матричные методы) и полезна для тестирования обработки последовательностей данных.

Решение на Python

def fibonacci(n):
    """
    Возвращает N-е число последовательности Фибоначчи.
    Итеративный подход — оптимален по времени и памяти.
    
    Args:
        n: индекс числа Фибоначчи (0-indexed)
    
    Returns:
        N-е число последовательности Фибоначчи
    """
    if n < 0:
        raise ValueError('N должно быть неотрицательным')
    
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    prev, curr = 0, 1
    
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    
    return curr

Альтернативные подходы

1. Простая рекурсия (неэффективная)

def fibonacci_recursive(n):
    """
    Простой рекурсивный подход.
    НЕЭФФЕКТИВНО: O(2^n) временная сложность!
    Использовать только для демонстрации.
    """
    if n < 0:
        raise ValueError('N должно быть неотрицательным')
    
    if n <= 1:
        return n
    
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

2. Рекурсия с мемоизацией

def fibonacci_memoized(n, memo={}):
    """
    Рекурсия с кешированием результатов.
    O(n) временная сложность, хорошо показывает динамическое программирование.
    """
    if n < 0:
        raise ValueError('N должно быть неотрицательным')
    
    if n in memo:
        return memo[n]
    
    if n <= 1:
        return n
    
    memo[n] = fibonacci_memoized(n - 1, memo) + fibonacci_memoized(n - 2, memo)
    return memo[n]

3. Динамическое программирование (табуляция)

def fibonacci_dp(n):
    """
    Динамическое программирование «снизу вверх».
    O(n) время, O(n) память.
    """
    if n < 0:
        raise ValueError('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]

4. Матричное возведение в степень

def fibonacci_matrix(n):
    """
    Использует матричное возведение в степень.
    O(log n) временная сложность — самый быстрый метод!
    Используется для очень больших n.
    """
    if n < 0:
        raise ValueError('N должно быть неотрицательным')
    
    if n <= 1:
        return n
    
    def matrix_mult(a, b):
        """Умножение двух матриц 2x2"""
        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(m, exp):
        """Возведение матрицы в степень"""
        if exp == 1:
            return m
        
        if exp % 2 == 0:
            half = matrix_pow(m, exp // 2)
            return matrix_mult(half, half)
        else:
            return matrix_mult(m, matrix_pow(m, exp - 1))
    
    base_matrix = [[1, 1], [1, 0]]
    result = matrix_pow(base_matrix, n)
    
    return result[0][1]

5. Генератор для последовательности

def fibonacci_generator(n):
    """
    Генератор для получения первых n чисел Фибоначчи.
    Полезен для работы с большими последовательностями.
    """
    a, b = 0, 1
    count = 0
    
    while count < n:
        yield a
        a, b = b, a + b
        count += 1

# Использование:
# for fib_num in fibonacci_generator(10):
#     print(fib_num)

Тестовые примеры

import unittest

class TestFibonacci(unittest.TestCase):
    
    def test_basic_case(self):
        # Базовый случай из условия
        assert fibonacci(6) == 8
    
    def test_zero(self):
        # Первое число Фибоначчи
        assert fibonacci(0) == 0
    
    def test_one(self):
        # Второе число Фибоначчи
        assert fibonacci(1) == 1
    
    def test_sequence(self):
        # Проверка первых чисел последовательности
        expected = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
        for i, expected_val in enumerate(expected):
            assert fibonacci(i) == expected_val, f'fibonacci({i}) должно быть {expected_val}'
    
    def test_larger_numbers(self):
        # Тестирование больших чисел
        assert fibonacci(10) == 55
        assert fibonacci(15) == 610
        assert fibonacci(20) == 6765
    
    def test_negative_input(self):
        # Отрицательный индекс должен вызвать ошибку
        with self.assertRaises(ValueError):
            fibonacci(-1)
    
    def test_two(self):
        # Третье число
        assert fibonacci(2) == 1
    
    def test_three(self):
        # Четвёртое число
        assert fibonacci(3) == 2

# Тестирование производительности разных методов
class TestFibonacciPerformance(unittest.TestCase):
    
    def test_performance_iterative_vs_dp(self):
        # Оба должны давать одинаковый результат
        for i in range(30):
            assert fibonacci(i) == fibonacci_dp(i)
    
    def test_performance_iterative_vs_memoized(self):
        # Для больших чисел итеративный метод должен быть быстрее
        assert fibonacci(25) == fibonacci_memoized(25)

Анализ сложности

Применение в QA Automation

• Функциональное тестирование — проверка корректности алгоритмов обработки последовательностей
• Performance тестирование — сравнение различных подходов реализации
• Граничные случаи — тестирование n=0, n=1, отрицательные числа
• Генерация тестовых данных — автоматическое создание последовательностей для тестов
• Мемори-тестирование — проверка потребления памяти разными методами

Рекомендация

Для стандартного использования в QA рекомендуется итеративный метод — он оптимален по времени O(n) и памяти O(1). Для интервью и демонстрации знания алгоритмов используйте мемоизацию, так как она показывает понимание динамического программирования. Для очень больших n (миллиарды) используйте матричный метод, но это редко требуется в QA.