На вход алгоритма подаётся натуральное число N… (информатика)

Алгоритм построения двоичной записи с битами чётности

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

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

Решение

Пусть в двоичной записи N было k единиц.
Шаг а): дописывается бит . Теперь единиц , и это число всегда чётное.
Шаг б): дописывается остаток от деления на , то есть .

Значит, любое R, полученное алгоритмом, оканчивается на и содержит чётное количество единиц. Верно и обратное: если запись оканчивается на и в ней чётное число единиц, то её можно получить (отбросив два последних разряда, получим N).

Перебираем числа больше :

: три единицы, нечётно — не подходит.
: оканчивается на — не подходит.
: четыре единицы, оканчивается на — подходит.

Проверка: . Единиц три, дописываем : . Единиц четыре, дописываем : .

💡 Почему так

Первый дописанный бит делает число единиц чётным, поэтому второй дописанный бит всегда равен , а общее количество единиц в R чётно.

Ответ

Помогло?

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