Задание №5 — Анализ простейших алгоритмов
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1) Из числа N вычитается остаток от деления N на 4.
2) Строится двоичная запись полученного результата.
3) К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры построенной двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия - справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись является двоичной записью искомого числа R. Укажите такое наибольшее число R, для которого результат работы данного алгоритма меньше числа 47. В ответе это число запишите в десятичной системе счисления.
Правильный ответ
34
Пояснение
Решение:
Первый шаг алгоритма — вычитание остатка от деления на 4 — превращает в число , кратное четырём. Дальше к двоичной записи дважды приписывается справа бит чётности, то есть запись удлиняется ровно на два разряда: , где и — приписанные биты.
Отсюда , и из условия следует . Кратных четырём значений тут немного: , , . Чем больше , тем больше , поэтому берём наибольшее подходящее и проверяем его.
Запись числа 8 — 1000. Сумма цифр равна 1, остаток от деления на 2 равен 1, приписываем: 10001. Теперь сумма цифр равна 2, остаток 0, приписываем: 100010. Это , и действительно . Для сравнения, даёт , а уже даёт . Наибольшее подходящее равно 34 (оно получается при ).
def R(N):
b = bin(N - N % 4)[2:]
for _ in range(2):
b += str(sum(int(c) for c in b) % 2)
return int(b, 2)
print(max(R(N) for N in range(1, 1000) if R(N) < 47)) # 34
Ответ: 34