Задание 16 – рекуррентно заданная функция $F(n)$: в условии даны база и шаг, требуется вычислить значение выражения из нескольких её значений. В части вариантов функций две, $F$ и $G$, и одна определена через другую.
1 балл, норматив 5 минут.
Что нужно знать заранее:
// – оно не преобразует результат в float.Задание 16 демонстрационного варианта ЕГЭ-2027 (ФИПИ).
Алгоритм вычисления значения функции $F(n)$, где $n$ – натуральное число, задан следующими соотношениями:
$F(n) = 1$ при $n = 1$;
$F(n) = n \times F(n - 1)$, если $n > 1$.
Чему равно значение выражения $\frac{F(3038) + 5 \times F(3037)}{F(3036)}$?
Соотношение переписывается в код построчно: каждая его часть имеет прямое соответствие в программе.
| Строка соотношения | Что задаёт | Строка кода |
|---|---|---|
| $F(1) = 1$ | база | F[1] = 1 |
| $F(n) = n \cdot F(n-1)$ | шаг | F[n] = n * F[n - 1] |
| порядок вычисления | от базы по возрастанию $n$, каждое значение вычисляется один раз | for n in range(2, N + 1) |
| ответ | значение выражения, а не самой функции | print((F[3038] + 5 * F[3037]) // F[3036]) |
Почему цикл, а не рекурсия. Соотношение допускает и запись рекурсивной функцией: на задании 13 применялся именно такой подход, но там глубина составляла несколько десятков. Здесь глубина равна 3038, а Python по умолчанию обрывает вложенность на 1000 вызовах и завершает выполнение с RecursionError. Предел повышается вызовом sys.setrecursionlimit(30000), и рекурсия без декоратора после этого отрабатывает: начиная с Python 3.11 вызов одной Python-функции из другой не занимает системный стек.
Второй приём, применённый в задании 13, – декоратор @lru_cache – здесь неприменим. Он реализован на C, поэтому каждый вызов через него занимает кадр в стеке потока; стек исчерпывается на глубине порядка тысячи вызовов (точное значение зависит от системы), и повышение предела рекурсии на это не влияет. Кеширование здесь и не требуется: цепочка $F(3038) \to F(3037) \to \dots$ линейная, каждое значение вычисляется ровно один раз. Цикл устраняет все три сложности – предел вложенности, стек и декоратор.
Почему //, а не /. / всегда даёт float, а во float помещаются числа примерно до 1e308 – 3038! с его 9263 знаками в этот диапазон не попадает. При делении факториала на факториал Python справляется: он делит длинные целые точно и округляет уже частное. Однако если в выражении есть деление на константу (например, выражения вида $F(n) / 519$), выполнение прерывается ошибкой OverflowError: integer division result too large for a float. Целочисленное деление работает с целыми числами и такой ошибки не даёт.
N = 3038 # наибольший аргумент в выражении
F = [0] * (N + 1)
F[1] = 1 # база: F(1) = 1
for n in range(2, N + 1):
F[n] = n * F[n - 1] # шаг: F(n) = n * F(n - 1)
print((F[3038] + 5 * F[3037]) // F[3036]) # 9241591
Выражение сворачивается вручную: выкладка занимает около полуминуты и не требует запуска программы.
Обоснование сокращения. Оба условия следуют из самого соотношения. Во-первых, $F(3036) \ne 0$: функция $F$ по определению есть произведение натуральных чисел начиная с единицы, нулевых множителей среди них нет, поэтому деление определено. Во-вторых, деление выполняется нацело: $F(3036)$ входит в числитель множителем, поэтому дробь сокращается тождественно, при любом $n$. По этой причине в программе используется // – остатка заведомо не возникает.
Преимущество способа не только в скорости. Могут встретиться задания, в которых $n = 247563$: факториал такого числа содержит 1227765 знаков, цикл вычисляет его около 12 секунд, а хранение всего списка значений потребовало бы десятков гигабайт памяти. Выкладка на бумаге от величины $n$ не зависит – сокращаются те же множители.
Общая схема решения не меняется: база и шаг переносятся в цикл, далее выражение либо вычисляется, либо сокращается. Различия сводятся к одному из трёх – вид шага, граница базы, число функций.
| Что в условии | Что делать |
|---|---|
| $F(n) = (n+1) \times F(n-1)$ или $F(n) = (n-1) \times F(n-1)$ | в цикле меняется только множитель; в выкладке аналогично: $F(3038)$ заменяется на $3039 \cdot F(3037)$ или на $3037 \cdot F(3037)$ |
| база задана не при $n = 1$, а как «$F(n) = 1$ при $n < 10$» | базой заполняется не одно значение, а весь диапазон: for n in range(1, 10): F[n] = 1 |
| шаг не на 1, а $F(n) = (n+3) \times F(n-3)$ | аргументы в выражении также идут через 3; сокращаются те же множители, их просто меньше |
| сложение вместо умножения: $F(n) = n + F(n-2)$, а требуется $F(2126) - F(2122)$ | разность раскрывается в сумму двух-трёх слагаемых и вычисляется устно |
| две функции: $F(n) = 3 \times G(n-3) + 7$, а $G$ задана собственным соотношением с шагом | сначала циклом вычисляется $G$ от базы до нужного аргумента, затем значение подставляется в $F$. |
/ вместо целочисленного //. На выражении из демонстрационного варианта результат получится, но на F(247563) / 519 выполнение прерывается ошибкой OverflowError: integer division result too large for a float. Целочисленное деление к float не обращается и такой ошибки не даёт.setrecursionlimit и @lru_cache с задания 13. Предел вложенности здесь действительно нужно повысить – глубина 3038 превышает 1000, – но @lru_cache реализован на C и занимает стек потока: рекурсия прерывается ошибкой RecursionError: Stack overflow примерно на тысяче вызовов, и повышение предела на это не влияет. Кеширование при линейной цепочке вызовов не требуется. Цикл вычисляет ту же формулу без этих ограничений.print(F(3038)) прерывается ошибкой ValueError: Exceeds the limit (4300 digits) for integer string conversion: Python не переводит в строку числа длиннее 4300 знаков. Выводить следует значение выражения – оно невелико.Разбор без практики забывается за неделю. Возьмите несколько задач на задание 16 прямо сейчас.
Войти, чтобы решать