Информатика. ЕГЭ
Задания для подготовки
Задачи разных лет из реальных экзаменов, демо-вариантов, сборников задач и других источников
Задание 16. Информатика. ЕГЭ. Статград. 28.01.2025-1
- Просмотры: 4060
- Изменено: 1 февраля 2025
Обозначим через \(a\%b\) остаток от деления натурального числа \(a\) на натуральное число \(b,\) а через \(a//b\) — целую часть от деления \(a\) на \(b.\) Функция \(F(n),\) где \(n\) — неотрицательное целое число, задана следующими соотношениями:
- \(F(n) = 0,\) если \(n = 0;\)
- \(F(n) = F(n//4) + n\%4,\) если \(n>0\) и \(n\%4 < 2;\)
- \(F(n) = F(n//4) + n\%4 - 1,\) если \(n\%4 \geqslant 2.\)
Найдите минимальное \(n,\) для которого \(F(n) = 27,\) а \(F(n + 1) = 16.\)
Решение:
Нетрудно понять, что функция \(F(n) = e + d + 2t,\) где \(e, d, t\) количество единиц, двоек и троек в четверичной записи числа \(n\) соответственно.Так как \(27 - 16 = 11,\) то при добавлении единицы количество троек в четверичной записи должно уменьшится на \(6,\) а седьмой справа разряд либо увеличиться с \(0\) до \(1\), либо с \(2\) до \(3\). Кроме того, сумма цифр старших разрядов начиная с седьмого справа для \(n\) должна равняться \(15,\) а для \((n + 1)\) равняться \(16.\) С учётом минимальности такого числа (в таком числе должно быть как можно меньше разрядов) получаем, что это число \(33333332333333_4 = 268431359.\)
Программа для проверки наших рассуждений:
Python
def F(n):
if n == 0:
return 0
if n % 4 < 2:
return F(n // 4) + n % 4
return F(n // 4) + n % 4 - 1
n = int('3'*7 + '2' + '3' * 6, 4)
print(n, F(n), F(n + 1))
Ответ: \(268431359\)
Обсуждение задания
Здесь пока нет ни одного комментария. Будьте первым!
Новый тренажёр-эмулятор
Станции КЕГЭ
Эффективно готовьтесь к ЕГЭ по информатике с новым тренажёром, эмулирующем работу станции КЕГЭ, которая используется на реальном экзамене.
Новое видео
Методы решения задания 16 ЕГЭ по Информатике «Вычисление рекуррентных выражений»
Поддержать автора сайта!
Поддержите автора сайта, если материалы, размещённые здесь, оказались вам полезны.
Совершая донат, вы соглашаетесь с Условиями использования