Задание 16. Информатика. ЕГЭ. Статград. 28.01.2025-1
- Просмотры: 1064
- Изменено: 2 февраля 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\)