Задание №5 — Анализ простейших алгоритмов
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1) Строится двоичная запись числа N.
2) Далее эта запись обрабатывается по следующему правилу:
а) если число чётное, то к двоичной записи числа слева дописывается 10;
б) если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 410 = 1002 результатом является число 2010 = 101002, а для исходного числа 510 = 1012 это число 1101012 = 5310. Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее чем 516. В ответе запишите это число в десятичной системе счисления.
Правильный ответ
65
Пояснение
Решение:
Разберём, как меняется длина записи.
- Для чётного слева приписывается 10: запись на два разряда длиннее и начинается с 10.
- Для нечётного слева приписывается 1, а справа 01: запись на три разряда длиннее и начинается с 11.
Число записывается десятью разрядами, поэтому нам нужна запись длиной не менее десяти разрядов.
Посмотрим, что даёт . Нечётные не превосходят 63 и записываются не более чем шестью разрядами, значит у не более девяти разрядов. Чётные записываются не более чем семью разрядами, значит у тоже не более девяти разрядов. В обоих случаях .
Итак, . Число нечётное, поэтому — подходит.
def alg(n):
b = bin(n)[2:]
b = '10' + b if n % 2 == 0 else '1' + b + '01'
return int(b, 2)
print(min(n for n in range(1, 1000) if alg(n) > 516))
Ответ: 65