РЕШУ ЕГЭ — информатика

Задания

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

F(n)  =  n, если n ≥ 2025;

F(n)  =  n + 3 + F(n + 3), если n < 2025.

Чему равно значение выражения F(23) − F(21)?

Решение. Приведём решение на языке Python.

def F(n):

if n >= 2025:

return n

if n < 2025:

return n + 3 + F(n + 3)

print(F(23) - F(21))

Ответ: 1338.

Приведём решение Евгения Джобса (аналитическое наблюдение).

Для выявления закономерности выражения $f левая круглая скобка n правая круглая скобка – f левая круглая скобка n минус 2 правая круглая скобка$ вычислим значения функции для чисел в диапазоне [2016; 2027].

2027	2026	2025	2024	2023	2022	2021	2020	2019	2018	2017	2016
2027	2026	2025	4054	4052	4050	6078	6075	6072	8099	8095	8091

Можно заметить, что разница между числом, кратным 3, и числом, на 2 большим, увеличивается с каждой тройкой на 2. Тогда:

$f левая круглая скобка 2027 правая круглая скобка минус f левая круглая скобка 2025 правая круглая скобка =2,$ $f левая круглая скобка 2024 правая круглая скобка минус f левая круглая скобка 2022 правая круглая скобка =4,$ $f левая круглая скобка 2021 правая круглая скобка минус f левая круглая скобка 2019 правая круглая скобка =6,$ $f левая круглая скобка 2018 правая круглая скобка минус f левая круглая скобка 2016 правая круглая скобка =8.$

Следовательно, нужно понять, какой тройкой по счету будет тройка (23, 22, 21), и умножить её номер на 2. Вычислим:

$дробь: числитель: левая круглая скобка 2027 минус 23 правая круглая скобка , знаменатель: 3 конец дроби плюс 1= дробь: числитель: 2004 , знаменатель: 3 конец дроби плюс 1=668 плюс 1=669.$

Приведём решение Евгения Джобса (аналитическое, вывод формулы).

Заметим, что рекуррентная формула накапливает значение с шагом 3. То есть получает

$левая круглая скобка n плюс 3 правая круглая скобка плюс левая круглая скобка n плюс 6 правая круглая скобка плюс левая круглая скобка n плюс 9 правая круглая скобка плюс \ldots плюс левая круглая скобка n плюс 3 умножить на k правая круглая скобка плюс 2 умножить на левая круглая скобка n плюс 3 умножить на левая круглая скобка k плюс 1 правая круглая скобка правая круглая скобка ,$

где значение k  — максимальное целое число, для которого выполняется неравенство $n плюс 3 умножить на k меньше 2025.$

Найдем значения k для 23 и 21:

$23 плюс 3 умножить на k меньше 2025 равносильно 3 k меньше 2002 равносильно k меньше 667,33 ...,$

откуда $k_\max =667;$ и

$21 плюс 3 умножить на k меньше 2025 равносильно 3 k меньше 2004 равносильно k меньше 668,$

тогда $k_\max =667.$

Следовательно, имеем дело с двумя рядами одинаковой длины:

$f левая круглая скобка 23 правая круглая скобка = левая круглая скобка 23 плюс 3 правая круглая скобка плюс левая круглая скобка 23 плюс 6 правая круглая скобка плюс левая круглая скобка 23 плюс 9 правая круглая скобка плюс \ldots плюс левая круглая скобка 23 плюс 3 умножить на 667 правая круглая скобка плюс 2 умножить на левая круглая скобка 23 плюс 3 умножить на левая круглая скобка 667 плюс 1 правая круглая скобка правая круглая скобка ;$ $f левая круглая скобка 23 правая круглая скобка = левая круглая скобка 23 плюс 3 правая круглая скобка плюс левая круглая скобка 23 плюс 6 правая круглая скобка плюс левая круглая скобка 23 плюс 9 правая круглая скобка плюс$
$плюс \ldots плюс левая круглая скобка 23 плюс 3 умножить на 667 правая круглая скобка плюс 2 умножить на левая круглая скобка 23 плюс 3 умножить на левая круглая скобка 667 плюс 1 правая круглая скобка правая круглая скобка ;$

$f левая круглая скобка 21 правая круглая скобка = левая круглая скобка 21 плюс 3 правая круглая скобка плюс левая круглая скобка 21 плюс 6 правая круглая скобка плюс левая круглая скобка 21 плюс 9 правая круглая скобка плюс \ldots плюс левая круглая скобка 21 плюс 3 умножить на 667 правая круглая скобка плюс 2 умножить на левая круглая скобка 21 плюс 3 умножить на левая круглая скобка 667 плюс 1 правая круглая скобка правая круглая скобка .$ $f левая круглая скобка 21 правая круглая скобка = левая круглая скобка 21 плюс 3 правая круглая скобка плюс левая круглая скобка 21 плюс 6 правая круглая скобка плюс левая круглая скобка 21 плюс 9 правая круглая скобка плюс$
$плюс \ldots плюс левая круглая скобка 21 плюс 3 умножить на 667 правая круглая скобка плюс 2 умножить на левая круглая скобка 21 плюс 3 умножить на левая круглая скобка 667 плюс 1 правая круглая скобка правая круглая скобка .$

Значит, при вычитании из f(23) значения f(21) получим набор разностей:

$f левая круглая скобка 23 правая круглая скобка минус f левая круглая скобка 21 правая круглая скобка = левая круглая скобка левая круглая скобка 23 плюс 3 правая круглая скобка минус левая круглая скобка 21 плюс 3 правая круглая скобка правая круглая скобка плюс левая круглая скобка левая круглая скобка 23 плюс 6 правая круглая скобка минус левая круглая скобка 21 плюс 6 правая круглая скобка правая круглая скобка плюс левая круглая скобка левая круглая скобка 23 плюс 9 правая круглая скобка минус левая круглая скобка 23 плюс 9 правая круглая скобка правая круглая скобка плюс \ldots$ $f левая круглая скобка 23 правая круглая скобка минус f левая круглая скобка 21 правая круглая скобка = левая круглая скобка левая круглая скобка 23 плюс 3 правая круглая скобка минус левая круглая скобка 21 плюс 3 правая круглая скобка правая круглая скобка плюс$
$плюс левая круглая скобка левая круглая скобка 23 плюс 6 правая круглая скобка минус левая круглая скобка 21 плюс 6 правая круглая скобка правая круглая скобка плюс левая круглая скобка левая круглая скобка 23 плюс 9 правая круглая скобка минус левая круглая скобка 23 плюс 9 правая круглая скобка правая круглая скобка плюс \ldots$

$\ldots плюс левая круглая скобка левая круглая скобка 23 плюс 3 умножить на 667 правая круглая скобка минус левая круглая скобка 21 плюс 3 умножить на 667 правая круглая скобка правая круглая скобка плюс 2 умножить на левая круглая скобка левая круглая скобка 23 плюс 3 умножить на левая круглая скобка 667 плюс 1 правая круглая скобка правая круглая скобка правая круглая скобка минус 2 умножить на левая круглая скобка левая круглая скобка 21 плюс 3 умножить на левая круглая скобка 667 плюс 1 правая круглая скобка правая круглая скобка правая круглая скобка ,$ $\ldots плюс левая круглая скобка левая круглая скобка 23 плюс 3 умножить на 667 правая круглая скобка минус левая круглая скобка 21 плюс 3 умножить на 667 правая круглая скобка правая круглая скобка плюс$
$плюс 2 умножить на левая круглая скобка левая круглая скобка 23 плюс 3 умножить на левая круглая скобка 667 плюс 1 правая круглая скобка правая круглая скобка правая круглая скобка минус 2 умножить на левая круглая скобка левая круглая скобка 21 плюс 3 умножить на левая круглая скобка 667 плюс 1 правая круглая скобка правая круглая скобка правая круглая скобка ,$

то есть

$f левая круглая скобка 23 правая круглая скобка минус f левая круглая скобка 21 правая круглая скобка = 2 плюс 2 плюс 2 плюс \ldots плюс 2 плюс 2 умножить на 2 = 2 умножить на левая круглая скобка 667 плюс 2 правая круглая скобка = 1338.$

Приведём решение Евгения Джобса на языке Python.

Так как шаг рекурсии 3, то нет необходимости хранить все значения, достаточно хранить последние три вычисленных и обращаться к вычисленным ранее значениям по признаку остатка от деления на 3. Также разница между значениями 23 и 21 составляет 2, что означает, что списка из трех элементов точно хватит.

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

f = [0]*3

for n in range(2025, 2028):

f[n % 3] = n

# перебираем значения в порядке убывания до 21

for n in range(2024, 20, -1):

f[n % 3] = n + 3 + f[n % 3]

print(f[23 % 3] - f[21 % 3])

№ п/п	№ задания	Ответ
1	55812	1338

Ключ