На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Далее эта запись обрабатывается по следующему правилу: а) если сумма цифр двоичной записи чётная, то к этой

6 ноября 2025
Программирование

Условие:

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

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

б) если сумма цифр двоичной записи нечётная, то к этой записи справа дописывается 1, а два левых разряда заменяются на 11.

Полученная таким образом запись является двоичной записью искомого числа R. Например, для исходного числа 6 = 1102 результатом является 10002 = 8, а для исходного числа 4 = 1002 результатом является 11012 = 13.

Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее 35. В ответе запишите это число в десятичной системе счисления.

Решение:

Рассмотрим подробно алгоритм. Пусть дано натуральное число N. Его двоичная запись имеет вид d₁ d₂ d₃ … d_L (при L ≥ 2 – число бит) Алгоритм действует так: 1. Если сумма цифр двоичной записи (то есть число единиц) чётная, то: – к записи справа дописывается 0, – два левых разряда заменяются на «10». 2. Если сумма нечётная, то: – дописывается 1 справа, – два левых разряда заменяются на «11». При этом полученная запись – двоичная запись числа R. Нам нужно найти максимальное N, такое что R 35 (десятичное). Заметим важное: если N имеет L бит, то в новой записи остаётся (L–2) внутренних ...