ЕГЭ. Вопрос 16. Рекуррентные функции. Две функции

Задача

Алгоритмы вычисления значения функций F(n) и G(n), где n – целое число, заданы следующими соотношениями:
F(1) = 1,
F(n) = 2 * F(n – 1) + G(n) при n > 1.

G(1) = 2, G(2) = 2,
G(n) = 3 * G(n – 1) – F(n – 1)

Чему равно значение функции F(15)?

Разбор

Особенность: Функции F и G взаимозависимы — каждая вызывает другую, что делает задачу более сложной.

Метод 1: Рекурсивный подход

Принцип: Реализуем обе функции точно по заданным формулам, позволяя им вызывать друг друга​

Структура взаимных вызовов:

F(15) → требует G(15)
  G(15) → требует G(14) и F(14)
    G(14) → требует G(13) и F(13)
      ...
        F(2) → требует F(1) и G(2)
          F(1) = 1 (базовый случай)
          G(2) = 2 (базовый случай)

Проблемы:

• Экспоненциальный рост вычислений: каждый вызов F(n) требует вычисления G(n), которое в свою очередь требует F(n−1) и G(n−1)​

• Повторные вычисления: одни и те же значения F(k) и G(k) вычисляются многократно​

• Риск переполнения стека при больших значениях n​

Недостатки:

• Время работы: O(2ⁿ) без мемоизации

• Неэффективно даже для n=15

Метод 2: Динамическое программирование

Принцип: Последовательно вычисляем значения обеих функций "снизу вверх", сохраняя результаты в массивах​

Формулы перехода:

• F(n)=2⋅F(n−1)+G(n)
• G(n)=3⋅G(n−1)−F(n−1)

Код на Python

Преимущества:

• Время: O(n) — линейная сложность
• Память: O(n) для хранения массивов
• Гарантированная корректность без повторных вычислений
   

Метод 3: Оптимизированное динамическое программирование

Принцип: Поскольку для вычисления F(n) и G(n) нужны только предыдущие значения, можно обойтись без массивов, используя только переменные​

Алгоритм:

1. Храним только текущие и предыдущие значения F и G
2. На каждом шаге обновляем значения последовательно
3. Важно соблюдать порядок: сначала вычисляем новое G, затем новое F​

Код с оптимизацией памяти: