ЕГЭ · краткий ответ

Задание 16 ЕГЭ по информатике — рекурсивные функции

Что проверяет номер, типичные ошибки, пример с решением на Python и 10 заданий с ответами под спойлером.

40заданий в банке
с ответамикак в КИМ
1 кликзадание на доске

Что проверяет задание 16 ЕГЭ

Функция задана рекурсивно (через значения при меньших или больших n), нужно найти значение выражения, например F(2024) / F(2021). Прямой вызов часто падает из-за ограничения глубины рекурсии — помогают sys.setrecursionlimit, кэширование @lru_cache или вычисление снизу вверх в цикле. Иногда ответ проще получить на бумаге, раскрыв формулу.

КЕГЭ, задание 1640 заданий в банке ИнфДоски

Типичные ошибки

  • Вызывают функцию с большим n без setrecursionlimit и получают RecursionError.
  • Делят большие числа через / и теряют точность в дробях — нужно //.
  • Не используют кэш, и программа считает часами.
  • Путают, при каких n работает базовый случай.

Пример с решением

Условие

Алгоритм вычисления значения функции F(n), где n — натуральное число:
F(n) = 1 при n = 1;
F(n) = n · F(n − 1) при n > 1.
Чему равно значение выражения F(2024) / F(2021)?

Решение

F(n) — это n!. Значит, F(2024) / F(2021) = 2024 · 2023 · 2022 = 8279184144. Программой: увеличиваем глубину рекурсии и используем целочисленное деление.

import sys
from functools import lru_cache
sys.setrecursionlimit(10000)

@lru_cache(None)
def F(n):
    return 1 if n == 1 else n * F(n - 1)

print(F(2024) // F(2021))
Код на Python 3 — его можно запустить прямо на ИнфДоске.
Ответ: 8279184144

Задания из банка

В банке ИнфДоски 40 заданий этого номера. Ниже — 10 из них, ответ спрятан под спойлером. Кнопка «Открыть на доске» ставит задание на вашу ИнфДоску.

Задание 1 Рекурсия Открыть на доске →

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

;

.

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

Ответ
4049
Задание 2 Рекурсия Открыть на доске →

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

;

;

.

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

Ответ
3194
Задание 3 Рекурсия Открыть на доске →

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

;

;

.

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

Примечание. При вычислении значения используется операция целочисленного деления.

Ответ
49134
Задание 4 Рекурсия Открыть на доске →

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

;

;

.

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

Ответ
20380
Задание 5 Рекурсия Открыть на доске →

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

;

;

.

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

Ответ
545
Задание 6 Рекурсия Открыть на доске →

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

;

.

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

Ответ
8191127
Задание 7 Рекурсия Открыть на доске →

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

;

.

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

Ответ
77785554
Задание 8 Рекурсия Открыть на доске →

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

;

.

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

Ответ
6066
Задание 9 Рекурсия Открыть на доске →

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

;

.

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

Ответ
16374162
Задание 10 Рекурсия Открыть на доске →

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

;

.

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

Ответ
6069
ИнфДоска

Разбирайте задание 16 ЕГЭ на онлайн-доске

Задание из банка — на доску в один клик, ответ видите только вы. После урока доска сама составит отчёт маме или папе.

Другие задания ЕГЭ