Задание №5 — Анализ простейших алгоритмов
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) Далее если исходное число чётное, то справа к построенной двоичной записи числа N приписывается 0, если нечётное, то приписывается 1.
3) Далее полученная на втором шаге алгоритма запись обрабатывается по следующему правилу:
а) если количество единиц в двоичной записи кратно трём, то в этой записи два левых разряда заменяются на 11;
б) если количество единиц в двоичной записи некратно трём, то в этой записи два левых разряда заменяются на 10.
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 610 = 1102 результатом является число 10002 = 810, а для исходного числа 310 = 112 результатом является число 1112 = 710.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее, чем 26. В ответе запишите это число в десятичной системе счисления.
Правильный ответ
9
Пояснение
Решение:
Сначала поймём, сколько разрядов в числе R. На втором шаге к двоичной записи числа N приписывается ровно один разряд, а третий шаг длину не меняет — он лишь заменяет два левых разряда на 11 или на 10. Значит, в двоичной записи R на один разряд больше, чем в двоичной записи N.
Нам нужно , а — пятиразрядное число, значит в записи R должно быть не менее 5 разрядов. Отсюда в двоичной записи N не менее 4 разрядов, то есть . Проверяем числа подряд, начиная с восьми.
- . Число чётное, приписываем 0: 10000. Единиц одна, 1 не кратно 3, поэтому два левых разряда заменяем на 10: получаем 10000, то есть — мало.
- . Число нечётное, приписываем 1: 10011. Единиц три, 3 кратно 3, поэтому два левых разряда заменяем на 11: получаем , и — подходит.
Значит, минимальное подходящее N равно 9. Ту же проверку удобно сделать программой:
def R(n):
s = bin(n)[2:]
s = s + ('0' if n % 2 == 0 else '1')
s = ('11' if s.count('1') % 3 == 0 else '10') + s[2:]
return int(s, 2)
for n in range(1, 1000):
if R(n) >= 26:
print(n)
break
Программа печатает 9.
Ответ: 9