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

Дана натуральное число N. Чтобы решить задачу и получить искомое число R, нужно выполнить следующие шаги:

1. Преобразовать число N в двоичную запись. Для этого можно использовать деление на 2 с остатком. Начиная с N, делим его на 2 и запоминаем остаток. Затем делим полученное частное на 2 и снова запоминаем остаток. Продолжаем этот процесс до тех пор, пока частное не станет равным 0. Остатки, полученные в процессе деления, образуют двоичную запись числа N в обратном порядке. Переворачиваем ее, чтобы получить правильную двоичную запись числа N.

2. Подсчитать количество значащих цифр в двоичной записи числа N. Для этого достаточно посчитать количество цифр в числе N в двоичной системе, исключая ведущие нули.

3. Проверить, является ли количество значащих цифр четным или нечетным.

4. Если количество значащих цифр четное, то добавляем 1 в середину двоичной записи числа N. Для этого разбиваем запись числа N на две части посередине и вставляем между ними символ 1.

5. Если количество значащих цифр нечетное, то запись числа N остается неизменной.

6. Полученная запись является двоичной записью искомого числа R.

Например, пусть дано число N = 13. Его двоичная запись – 1101.
Количество значащих цифр равно 4, что является четным числом.
Поэтому в середину записи числа добавляем 1.
Искомое число R = 11101.