Задание №5 — Анализ простейших алгоритмов
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1) Строится двоичная запись числа N.
2) Каждый разряд этой записи заменяется двумя разрядами по следующему правилу: если в разряде стоит 0, то вместо него пишется 00; если в разряде стоит 1, то 1 заменяется на 11.
Например, двоичная запись 1001 числа 9 будет преобразована в 11000011.
Полученная таким образом запись (в ней в два раза больше разрядов, чем в записи исходного числа N) является двоичной записью числа R — результата работы данного алгоритма.
Укажите минимальное число R, большее 63, которое может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Правильный ответ
192
Пояснение
Решение:
Алгоритм просто удваивает каждый разряд двоичной записи . Если запись содержит разрядов, то запись содержит ровно разрядов, причём она составлена из пар 11 и 00.
Чем короче запись , тем меньше само число, поэтому сначала подбираем минимально возможную длину, а затем — минимальное число такой длины.
При (то есть от 4 до 7) запись шестиразрядная, и самое большое такое значение — . Оно не больше 63, поэтому шести разрядов не хватает.
Значит, нужно . Наименьшее восьмиразрядное получается из наименьшего четырёхразрядного :
.
def alg(n):
return int(''.join(c * 2 for c in bin(n)[2:]), 2)
print(min(r for r in {alg(n) for n in range(1, 100)} if r > 63))
Ответ: 192