Задание №5 — Анализ простейших алгоритмов
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1) Строится двоичная запись числа N.
2) Далее эта запись обрабатывается по следующему правилу:
а) если количество значащих цифр в двоичной записи числа чётное, то к этой записи в середину дописывается 1;
б) если количество значащих цифр в двоичной записи числа нечётное, то запись не изменяется.
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 510 = 1012 результатом является число 1012 = 510, а для исходного числа 210 = 102 результатом является число 1102 = 610.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее, чем 26. В ответе запишите это число в десятичной системе счисления.
Правильный ответ
12
Пояснение
Решение:
Если количество разрядов двоичной записи нечётно, запись не меняется и . Если чётно — в середину вставляется 1.
Ищем наименьшее , при котором .
Числа записываются не более чем тремя разрядами, поэтому содержит не более трёх разрядов и — мало. Числа от 8 до 15 записываются четырьмя разрядами, вставка даёт пятиразрядную запись:
- ;
- ;
- ;
- ;
- — подходит.
Все меньшие числа дают , поэтому искомое наименьшее равно 12.
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(min(n for n in range(1, 1000) if alg(n) >= 26))
Ответ: 12