Пробный урок
📘 ЕГЭ по информатике 2027 · задание 16 из 27

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

Что проверяет задание 16, сколько баллов оно приносит и сколько времени на него закладывать — и 3 примера в формате ФИПИ с подробным решением и ответом.

Уровень
повышенный
Максимум
1 балл
Время
~5 минут
Компьютер
нужен (специальное ПО)

Примеры задания 16 с решениями

Сначала попробуйте решить сами, затем откройте решение и сверьте ответ

Пример 1

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан соотношениями: F(n) = 1 при n = 1; F(n) = n · F(n − 1) при n > 1. Чему равно значение выражения (F(2024) + 2 · F(2023)) / F(2022)?
Показать решение и ответ
1. F(n) = n! (факториал). Напрямую считать огромные числа вручную не нужно — сокращаем. 2. F(2024) / F(2022) = 2024 · 2023, а 2 · F(2023) / F(2022) = 2 · 2023. 3. Сумма: 2023 · (2024 + 2) = 2023 · 2026 = 4 098 598. Решение программой (обратите внимание на глубину рекурсии):
import sys                                  # модуль sys нужен, чтобы поднять лимит рекурсии
sys.setrecursionlimit(5000)                 # по умолчанию Python не даст рекурсию глубже ~1000 вызовов

def F(n):                                   # функция по определению из условия
    if n == 1:                              # база: F(1) = 1
        return 1                            # возвращаем 1
    return n * F(n - 1)                     # иначе n · F(n − 1)

print((F(2024) + 2 * F(2023)) // F(2022))   # // — целочисленное деление, точное для огромных чисел

Ответ: 4098598

Пример 2

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан соотношениями: F(n) = 1 при n ≤ 2; F(n) = F(n − 1) + 2 · F(n − 2) при n > 2. Чему равно значение функции F(20)?
Показать решение и ответ
1. Считаем по формуле снизу вверх, запоминая два последних значения: 1, 1, 3, 5, 11, 21, 43, … 2. Рекурсия без запоминания здесь пересчитывает одно и то же много раз, поэтому быстрее цикл:
a, b = 1, 1                      # F(1) и F(2)
for n in range(3, 21):           # считаем F(3), F(4), …, F(20)
    a, b = b, b + 2 * a          # новое F(n) = F(n−1) + 2·F(n−2); сдвигаем пару
print(b)                         # F(20) = 349525
Можно заметить формулу: F(n) = (2ⁿ − (−1)ⁿ) / 3, и F(20) = (2²⁰ − 1) / 3 = 349 525.

Ответ: 349525

Пример 3

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан соотношениями: F(n) = n при n ≥ 2025; F(n) = n + F(n + 2) при n < 2025. Чему равно значение выражения F(2020) − F(2023)?
Показать решение и ответ
1. Раскрываем по определению: F(2023) = 2023 + F(2025) = 2023 + 2025 = 4048. 2. F(2020) = 2020 + F(2022) = 2020 + 2022 + F(2024) = 2020 + 2022 + 2024 + F(2026) = 2020 + 2022 + 2024 + 2026 = 8092. 3. F(2020) − F(2023) = 8092 − 4048 = 4044. Проверка программой:
def F(n):                        # функция по определению из условия
    if n >= 2025:                # база: F(n) = n
        return n                 # возвращаем само число
    return n + F(n + 2)          # иначе n + F(n + 2)
print(F(2020) - F(2023))         # 4044

Ответ: 4044

Не получается задание 16? Разберём на пробном уроке

Бесплатно покажем, как решать задание 16 и похожие, определим пробелы и составим план подготовки к ЕГЭ.

Записаться бесплатно

Все задания ЕГЭ по информатике

Структура экзамена, баллы и темы — на странице программы ЕГЭ по информатике