Задание 16. Вычисление рекуррентных выражений. ЕГЭ 2026 по информатике

За это задание ты можешь получить 1 балл. На решение дается около 5 минут. Уровень сложности: повышенный.
Средний процент выполнения: 54%
Ответом к заданию 16 по информатике может быть цифра (число) или слово.

Алгоритм решения задания 16:

  1. Прочитай рекуррентное определение и выпиши начальные значения.
  2. Определи, для какого номера нужно найти значение (например, A(n) или F(n)).
  3. Создай таблицу значений от начального индекса до нужного.
  4. Последовательно вычисляй значения по рекуррентной формуле, используя уже найденные предыдущие.
  5. Записывай каждое промежуточное значение, чтобы не потерять шаг.
  6. Когда дойдёшь до нужного номера, выпиши полученное значение как ответ.
  7. Проверь вычисления на 1–2 шага назад (подставь в формулу), чтобы убедиться в отсутствии ошибки.

Задачи для практики

Задача 1

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

  • F(n) = 4 * G(n - 6);
  • G(n) = n // 2, если n < 15; (// - целочисленное деление)
  • G(n) = G(n - 7) + 5, если n ≥ 15.

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

Решение
from functools import lru_cache

@lru_cache(maxsize=None)
def F(n):
    return 4 * G(n - 6)

@lru_cache(maxsize=None)
def G(n):
    if n < 15:
        return n // 2
    else:
        return  G(n - 7) + 5

for i in range(9999):
    F(i)

print(F(9999))
Ответ: 28540
Показать решение
Бесплатный интенсив

Задача 2

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

  • F(n) = G(n) + G(n - 2);
  • G(n) = n², если n < 6;
  • G(n) = G(n - 1) + 2, если n ≥ 6.

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

Решение
from functools import lru_cache

@lru_cache(maxsize=None)
def F(n):
    return G(n) + G(n - 2)

@lru_cache(maxsize=None)
def G(n):
    if n < 6:
        return n ** 2
    else:
        return  G(n - 1) + 2

for i in range(777):
    F(i)

print(F(777))
Ответ: 3134
Показать решение
Бесплатный интенсив

Задача 3

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

  • F(n) = G(n) - G(n - 1);
  • G(n) = 3 * n, если n < 9;
  • G(n) = G(n - 3) + 4, если n ≥ 9.

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

Решение
from functools import lru_cache

@lru_cache(maxsize=None)
def F(n):
    return G(n) - G(n - 1)

@lru_cache(maxsize=None)
def G(n):
    if n < 9:
        return 3 * n
    else:
        return G(n - 3) + 4

for i in range(1500):
    F(i)

print(F(1500))
Ответ: -2
Показать решение
Бесплатный интенсив

Задача 4

⚠️ Наивное решение зависнет — числа вырастают до миллионов цифр. Нужна оптимизация.

Алгоритм вычисления значения функции F(n), где n — целое число, задан следующими соотношениями:

  • F(n) = 2, при n < 12;
  • F(n) = (n + 5) × F(n − 6), если n ≥ 12.

Чему равно значение выражения:

(F(398795) / 997 + 83 × F(398783)) / F(398777) ?

В ответе запишите целую часть полученного числа.

Решение

Оптимизация 1 — шаг рекурсии

F(n) всегда вызывает F(n − 6), значит все аргументы лежат в одной цепочке остатков по модулю 6.

  • 398795 % 6 = 5
  • 398783 % 6 = 5
  • 398777 % 6 = 5

Все три аргумента в одной цепочке — прогреваем кэш только по ней:

for i in range(11, 398_796, 6): f(i)

Вместо ~398796 вызовов — только ~66466, то есть в 6 раз меньше.

Оптимизация 2 — ограничение LRU-кэша

Прогрев идёт снизу вверх: f(11) → f(17) → f(23) → ...

При вычислении f(23) = 28 × f(17) нужно только одно предыдущее значение. После этого f(17) больше никогда не понадобится — его можно вытеснить из кэша.

  • Минимально нужно 2 слота: читаем старое + записываем новое.
  • lru_cache(5) — с небольшим запасом надёжности.

Оптимизация 3 — деление нацело

Раскроем F(398795) через рекурсию:

F(398795) = 398800 × F(398789)
           = 398800 × 398794 × F(398783)

Заметим, что 398800 = 997 × 400, значит деление нацело:

F(398795) // 997 = 400 × 398794 × F(398783)

Подставляем в числитель:

F(398783) × (400 × 398794 + 83) = F(398783) × 159517683

Раскроем F(398783):

F(398783) = 398788 × F(398777)

Делим на F(398777) — всё сокращается:

398788 × 159517683 = 63613737768204

Полный код на Python:

from functools import *

@lru_cache(5)
def f(n):
    if n < 12:
        return 2
    return (n + 5) * f(n - 6)

for i in range(11, 398_796, 6): f(i)

print((f(398795) // 997 + 83 * f(398783)) // f(398777))
Ответ: 63613737768204
Показать решение
Бесплатный интенсив

Задача 5

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

  • F(n) = G(n) * G(n - 4);
  • G(n) = 5, если n < 10;
  • G(n) = G(n - 5) + 1, если n ≥ 10.

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

Решение
from functools import lru_cache

@lru_cache(maxsize=None)
def F(n):
    return G(n) * G(n - 4)

@lru_cache(maxsize=None)
def G(n):
    if n < 10:
        return 5
    else:
        return G(n - 5) + 1

for i in range(5000):
    F(i)

print(F(5000))
Ответ: 1007012
Показать решение
Бесплатный интенсив

Задача 6

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

  • F(n) = G(n - 3) + F(n - 1);
  • F(0) = 1, F(1) = 1, F(2) = 2;
  • G(n) = 1, если n < 5;
  • G(n) = G(n - 1) + G(n - 4), если n ≥ 5.

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

Решение
from functools import lru_cache

@lru_cache(maxsize=None)
def F(n):
    if n == 0 or n == 1:
        return 1
    if n == 2:
        return 2
    return G(n - 3) + F(n - 1)

@lru_cache(maxsize=None)
def G(n):
    if n < 5:
        return 1
    else:
        return G(n - 1) + G(n - 4)

for i in range(100):
    F(i)

print(F(100))
Ответ: 54327237184328
Показать решение
Бесплатный интенсив

Задача 7

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

  • F(n) = 3 * G(n - 4);
  • G(n) = n + 1, если n < 8;
  • G(n) = G(n - 3) + n, если n ≥ 8.

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

Решение
from functools import lru_cache

@lru_cache(maxsize=None)
def F(n):
    return 3 * G(n - 4)

@lru_cache(maxsize=None)
def G(n):
    if n < 8:
        return n + 1
    else:
        return  G(n - 3) + n

for i in range(12345):
    F(i)

print(F(12345))
Ответ: 76168650
Показать решение
Бесплатный интенсив

Задача 8

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

  • F(n) = G(n - 1) - G(n - 3);
  • G(n) = 2, если n < 7;
  • G(n) = G(n - 2) + 3, если n ≥ 7.

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

Решение
from functools import lru_cache

@lru_cache(maxsize=None)
def F(n):
    return G(n - 1) - G(n - 3)

@lru_cache(maxsize=None)
def G(n):
    if n < 7:
        return 2
    else:
        return G(n - 2) + 3

for i in range(9000):
    F(i)

print(F(9000))
Ответ: 3
Показать решение
Бесплатный интенсив

Задача 9

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

  • F(n) = G(n - 2) + 5;
  • G(n) = n, если n < 5;
  • G(n) = G(n - 1) - 2, если n ≥ 5.

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

Решение
from functools import lru_cache

@lru_cache(maxsize=None)
def F(n):
    return G(n - 2) + 5

@lru_cache(maxsize=None)
def G(n):
    if n < 5:
        return n
    else:
        return G(n - 1) - 2

for i in range(10001):
    F(i)

print(F(10001))
Ответ: -19981
Показать решение
Бесплатный интенсив

Задача 10

Алгоритм вычисления функций F(n) и G(n), где n — целое число, задан следующими соотношениями:

  • F(n) = F(n − 4) + 3580, если n ≥ 19;
  • F(n) = 6 × (G(n − 7) − 36), если n < 19;
  • G(n) = n / 20 + 28, если n ≥ 248045;
  • G(n) = G(n + 9) − 4, если n < 248045.

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

Решение

Напишем код на Python:

from functools import lru_cache

@lru_cache(None)
def G(n):
    if n >= 248045:
        return n / 20 + 28
    else:
        return G(n + 9) - 4

@lru_cache(None)
def F(n):
    if n >= 19:
        return F(n - 4) + 3580
    else:
        return 6 * (G(n - 7) - 36)


for i in range(250000, 0, -1):
    G(i)
for i in range(1000):
    F(i)
print(F(745))
Ответ: 64487
Показать решение
Бесплатный интенсив

Задача 11

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

  • F(n) = F(n - 1) + G(n - 2);
  • F(0) = 2, F(1) = 3;
  • G(n) = n + 2, если n < 8;
  • G(n) = G(n - 4) + 1, если n ≥ 8.

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

Решение
from functools import lru_cache

@lru_cache(maxsize=None)
def F(n):
    if n == 0:
        return 2
    elif n == 1:
        return 3
    return F(n - 1) + G(n - 2)

@lru_cache(maxsize=None)
def G(n):
    if n < 8:
        return n + 2
    else:
        return G(n - 4) + 1

for i in range(100):
    F(i)

print(F(100))
Ответ: 1809
Показать решение
Бесплатный интенсив

Задача 12

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

  • F(n) = 2 * G(n - 5) + 10;
  • G(n) = n - 4, если n < 12;
  • G(n) = G(n - 4) * 2, если n ≥ 12.

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

Решение
from functools import lru_cache

@lru_cache(maxsize=None)
def F(n):
    return 2 * G(n - 5) + 10

@lru_cache(maxsize=None)
def G(n):
    if n < 12:
        return n - 4
    else:
        return  G(n - 4) * 2

for i in range(20):
    F(i)

print(F(20))
Ответ: 38
Показать решение
Бесплатный интенсив

Задача 13

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

  • F(n) = 2, если n < 20;
  • F(n) = 1 + 2F(n − 17), если 20 ≤ n < 150;
  • F(n) = −3 + F(n − 23), если 150 ≤ n < 1000;
  • F(n) = 2 + F(n − 42), если n ≥ 1000.

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

Решение
def f(n):
    if n < 20:
        return 2
    if 20 <= n < 150:
        return 1 + 2 * f(n - 17)
    elif 150 <= n < 1000:
        return -3 + f(n - 23)
    elif n > 1000:
        return 2 + f(n - 42)
print(f(1150))
Ответ: 280
Показать решение
Бесплатный интенсив

Задача 14

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

  • F(1) = 1, если n < 2;
  • F(n) = F(n/3) − 1, если n ≥ 2 и кратно 3;
  • F(n) = F(n − 1) + 20, если n ≥ 2 и не кратно 3.

Найдите количество значений n на отрезке [1; 100000], для которых F(n) равно 152.

Решение
def f(n):
    if n < 2:
        return 1
    if n >= 2 and n % 3 == 0:
        return f(n//3) - 1
    if n >= 2 and n % 3 != 0:
        return f(n-1) + 20

count = 0
for n in range(1, 100000 + 1):
    if f(n) == 152:
        count += 1
print(count)
Ответ: 5211
Показать решение
Бесплатный интенсив

Задача 15

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

  • F(n) = 3, если n ≤ 30;
  • F(n) = −3 + 2F(n − 29), если 30 < n ≤ 250;
  • F(n) = 2 + F(n − 43), если 250 < n ≤ 900;
  • F(n) = 3 + F(n − 62), если n > 900.

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

Решение
def f(n):
    if n <= 30:
        return 3
    if 30 < n <= 250:
        return -3 + 2 * f(n - 29)
    elif 250 < n <= 900:
        return 2 + f(n - 43)
    elif n > 900:
        return 3 + f(n - 62)

print(f(1400))
Ответ: 58
Показать решение
Бесплатный интенсив

Задача 16

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

  • F(1) = 1;
  • F(2) = 4;
  • F(n) = F(n − 1) + (n − 1) · F(n − 2), если n > 2.

Чему равно значение выражения F(1604) / F(1600)? В ответе укажите только целую часть.

Решение
a = [0] * 1605
a[1] = 1
a[2] = 4
for n in range(3, 1605):
    a[n] = a[n-1] + (n-1) * a[n-2]
print(a[1604]/a[1600])
Ответ: 2697876
Показать решение
Бесплатный интенсив

Задача 17

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

  • F(1) = 1;
  • F(2) = 3;
  • F(n) = F(n − 1) + n · F(n − 2), если n > 2.

Чему равно значение выражения F(1890) / F(1885)? В ответе укажите только целую часть.

Решение
a = [0] * 1891
a[1] = 1
a[2] = 3
for n in range(3, 1891):
    a[n] = a[n-1] + n * a[n-2]
print(a[1890]/a[1885])
Ответ: 164161991
Показать решение
Бесплатный интенсив

Задача 18

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

  • F(1) = 1, если n < 2;
  • F(n) = F(n/3) − 1, если n ≥ 2 и кратно 3;
  • F(n) = F(n − 1) + 20, если n ≥ 2 и не кратно 3.

Найдите количество значений n на отрезке [1; 100000], для которых F(n) равно 151.

Решение
def f(n):
    if n < 2:
        return 1
    if n >= 2 and n % 3 == 0:
        return f(n//3) - 1
    if n >= 2 and n % 3 != 0:
        return f(n-1) + 20

count = 0
for n in range(1, 100000 + 1):
    if f(n) == 151:
        count += 1
print(count)
Ответ: 5510
Показать решение
Бесплатный интенсив

Задача 19

Функция F(n), где n - натуральное число, вычисляется по следующему правилу:

F(n) = 1, при n = 1;

F(n) = F(n-1)*n, при n > 1

Чему равно значение выражения F(2022)/F(2019)?

Решение

Выразим функцию F(2022) через F(2019).

F(2022) = F(2021) * 2022

F(2021) = F(2020) * 2021

F(2020) = F(2019) * 2020

Получается, что F(2022) = F(2020) * 2021 * 2022 = F(2019) * 2020 * 2021 * 2022

F(2022)/F(2019) = F(2019) * 2020 * 2021 * 2022 / F(2019) = 2020 * 2021 * 2022 = 8254653240

Ответ: 8254653240

Ответ: 8254653240
Показать решение
Бесплатный интенсив

Задача 20

Функция F(n), где n - натуральное число, вычисляется по следующему правилу:

F(n) = n, при n < 4;

F(n) = F(n-3)*3, при n > 3 кратном трём;

F(n) = F(n-1)+7, при n > 3, которое даёт остаток 1 при делении на 3;

F(n) = F(n-2)+n, при n > 3, которое даёт остаток 2 при делении на 3.

Чему равно значение выражения F(5000) - 3 * F(4995)?

Решение

Выразим функцию F(5000) через F(4995).

F(5000) = F(4998) + 5000

F(4998) = F(4995) * 3

Получается, что F(5000) = F(4995) * 3 + 5000

F(5000) - 3 * F(4995) = F(4995) * 3 + 5000 - 3 * F(4995) = 5000.

Ответ: 5000

Ответ: 5000
Показать решение
Бесплатный интенсив
Показать еще

Рекомендуемые курсы подготовки

егэ по информатике информатика 10 класс информатика 11 класс информатика с нуля
Популярные материалы
  • Без воды
  • Ламповая атмосфера
  • Крутые преподаватели

ЕГЭ 2027: бесплатный курс
по информатике

На бесплатном демо-курсе ты:
  • 📚 Узнаешь о специфике ЕГЭ на компьютерах
  • 📚 Научишься применять тайм-менеджмент в подготовке
  • 📚 Научишься решать самое интересное задание ЕГЭ из первой части
  • 📚 Отдельно разберём с вами алгебру логики, а также решение 2 задания
Получи бесплатный демо-доступ
Оставь заявку и займи место
на бесплатном курсе Турбо ЕГЭ
Нажимая на кнопку «Отправить», вы принимаете положение об обработке персональных данных.