Задание №5 — Анализ простейших алгоритмов
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1) Строится двоичная запись числа N.
2) Далее эта запись обрабатывается по следующему правилу:
а) если количество значащих цифр в двоичной записи числа чётное, то к этой записи в середину дописывается 1;
б) если количество значащих цифр в двоичной записи числа нечётное, то запись не изменяется.
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 510 = 1012 результатом является число 1012 = 510, а для исходного числа 210 = 102 результатом является число 1102 = 610.
Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, не большее, чем 26. В ответе запишите это число в десятичной системе счисления.
Правильный ответ
26
Пояснение
Решение:
Если количество разрядов двоичной записи нечётно, запись не меняется и . Если чётно — в середину вставляется 1, из-за чего число разрядов увеличивается на единицу и становится нечётным, а само число возрастает: .
Итак, в любом случае запись содержит нечётное число разрядов и .
Число записывается пятью разрядами. Посмотрим, что даёт :
- при в записи пять (нечётное число) разрядов, поэтому — не подходит;
- при в записи шесть разрядов, значит в записи их семь и — не подходит;
- при тем более .
Само число записывается пятью разрядами — количество нечётное, запись не изменяется, . Условие выполнено.
def alg(n):
b = bin(n)[2:]
if len(b) % 2 == 0:
b = b[:len(b) // 2] + '1' + b[len(b) // 2:]
return int(b, 2)
print(max(n for n in range(1, 1000) if alg(n) <= 26))
Ответ: 26