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

24 октября 2025
Программирование

Условие:

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа).
Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью результирующего числа R. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.

Решение:

Рассмотрим задачу по шагам. 1. Пусть N – заданное натуральное число, его двоичная запись обозначим как b (без ведущих нулей). Обозначим сумму его цифр (единиц) как S. Тогда первая добавляемая цифра (d₁) равна остатку от деления S на 2, т.е. d₁ = S mod 2. 2. После дописывания d₁ слева от b получается новая последовательность, сумма цифр которой равна S + d₁. Вторая добавляемая цифра (d₂) равна остатку от деления (S + d₁) на 2: d₂ = (S + d₁) mod 2. Заметим, что: - Если S чётно, тогда d₁ = 0, и S + d₁ = S, чётное ⇒ d₂ = 0. - Если S нечётно, тогда d₁ = 1, и S + d₁ становится чётным ...