Задание №5 — Анализ простейших алгоритмов

#69705Задание №5ФИПИ

Анализ алгоритмов и исполнители

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:

1) Строится двоичная запись числа N.
2) Далее если исходное число чётное, то справа к построенной двоичной записи числа N приписывается 0, если нечётное, то приписывается 1.
3) Далее полученная на втором шаге алгоритма запись обрабатывается по следующему правилу:
а) если количество единиц в двоичной записи кратно трём, то в этой записи два левых разряда заменяются на 11;
б) если количество единиц в двоичной записи некратно трём, то в этой записи два левых разряда заменяются на 10.
Полученная таким образом запись является двоичной записью искомого числа R.

Например, для исходного числа 6₁₀ = 110₂ результатом является число 1000₂ = 8₁₀, а для исходного числа 3₁₀ = 11₂ результатом является число 111₂ = 7₁₀.
Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, не большее, чем 37. В ответе запишите это число в десятичной системе счисления.

Правильный ответ

Пояснение

Решение:

Разберёмся, что делает алгоритм. К двоичной записи $N$ справа приписывается её последняя цифра: 0 для чётного $N$ , 1 для нечётного. Затем два левых разряда заменяются на 11, если количество единиц кратно трём, и на 10 в противном случае.

Длина записи $R$ на один разряд больше длины записи $N$ , а старший разряд остаётся единицей.

Так как $37=100101_2$ — шестиразрядное число, у $R$ не может быть больше шести разрядов, значит у $N$ их не больше пяти и $N\le 31$ . Кроме того, шестиразрядное число, начинающееся с 11, не меньше $110000_2=48\gt 37$ , поэтому левые разряды обязаны замениться на 10.

Перебираем $N$ от 31 вниз:

$N$	после шага 2	единиц	$R$
31	111111	6 (кратно 3)	$111111_2=63$
30	111100	4	$101100_2=44$
29	111011	5	$101011_2=43$
28	111000	3 (кратно 3)	$111000_2=56$
27	110111	5	$100111_2=39$
26	110100	3 (кратно 3)	$110100_2=52$
25	110011	4	$100011_2=35$

Первое сверху значение, при котором $R\le 37$ , — это $N=25$ .

def alg(n):
    b = bin(n)[2:] + str(n % 2)
    b = ('11' if b.count('1') % 3 == 0 else '10') + b[2:]
    return int(b, 2)

print(max(n for n in range(1, 1000) if alg(n) <= 37))

Ответ: 25