Задание 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) = 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
Показать решение
Бесплатный интенсив

Задача 2

Алгоритм вычисления функций 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
Показать решение
Бесплатный интенсив

Задача 3

Алгоритм вычисления функций 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
Показать решение
Бесплатный интенсив

Задача 4

Алгоритм вычисления функций 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
Показать решение
Бесплатный интенсив

Задача 5

Алгоритм вычисления функций 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
Показать решение
Бесплатный интенсив

Задача 6

Алгоритм вычисления функций 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
Показать решение
Бесплатный интенсив

Задача 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) = 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
Показать решение
Бесплатный интенсив

Задача 9

Алгоритм вычисления функций 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
Показать решение
Бесплатный интенсив

Задача 10

Алгоритм вычисления функций 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
Показать решение
Бесплатный интенсив

Задача 11

Алгоритм вычисления значения функции 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
Показать решение
Бесплатный интенсив

Задача 12

Алгоритм вычисления значения функции 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
Показать решение
Бесплатный интенсив

Задача 13

Алгоритм вычисления значения функции 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):
    if f(n) == 152:
        count += 1
print(count)
Ответ: 5211
Показать решение
Бесплатный интенсив

Задача 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) равно 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):
    if f(n) == 151:
        count += 1
print(count)
Ответ: 5510
Показать решение
Бесплатный интенсив

Задача 15

Алгоритм вычисления значения функции 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
Показать решение
Бесплатный интенсив

Задача 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(n) = n, при n < 4;

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

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

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

Чему равно значение выражения F(7000) - 9 * F(6993)?

Решение

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

F(7000) = F(6999) + 7000

F(6999) = F(6996) * 3

F(6996) = F(6993) * 3

Получается, что F(7000) = F(6996) * 3 + 7000 = F(6993) * 3 * 3 + 7000 = F(6993) * 9 + 7000

F(7000) - 9 * F(6993) = F(6993) * 9 - 9 * F(6993) = 7000.

Ответ: 7000

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

Задача 18

Функция 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
Показать решение
Бесплатный интенсив

Задача 19

Функция 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
Показать решение
Бесплатный интенсив

Задача 20

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

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

F(n) = F(n-3)*n, при n > 1 чётном

F(n) = F(n-2)*n, при n > 1 нечётном

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

Ответ округлите до целого.

Решение

Выразить одну функцию через другую не получится, поэтому выразим обе функции через третью.

F(6112) = F(6109)*6112

F(6115) = F(6113)*6115

F(6113) = F(6111)*6113

F(6111) = F(6109)*6111

Выражения F(6115)/F(6112) = (F(6113)*6115) / (F(6109)*6112) = (F(6111)*6113*6115) / (F(6109)*6112) = (F(6109)*6111*6113*6115) / (F(6109)*6112) = (6111*6113*6115) / 6112 = 37374878.999...

После округления ответ: 37374879

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

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

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

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

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