1) Строится двоичная запись числа N.

2) К этой записи дописываются справа ещё два разряда по следующему правилу:

а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например,

запись 11100 преобразуется в запись 111001;

б) над этой записью производятся те же действия - справа дописывается остаток от деления суммы цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью

искомого числа R.

Укажите минимальное число R, которое превышает 43 и может являться результатом работы алгоритма.

Проанализируем алгоритм. Правило а) добавляет справа нуль при четном количестве единиц или единицу при нечетном. Правило б) делает то же самое, но с учетом правила а) количество единиц всегда будет четным, поэтому всегда будет добавляться ноль.

Подытоживая, можно утверждать, что к числу будут дописаны справа:

-10 (при нечетном количестве остальных единиц) ;

- 00 (при четном количестве единиц).

Минимальным числом R, которое превышает 43, является число 44. Получим его двоичную запись.

44 / 2 = 22, остаток 0

22 / 2 = 11, остаток 0

11 / 2 = 5, остаток 1

5 / 2 = 2, остаток 1

2 / 2 = 1, остаток 0

Записываем частное (оно всегда единица!) и приписываем к нему остатки в обратном порядке.

44₁₀ = 101100₂

Отделяем два последних разряда: 1011 00

Строим для части 1011 разряды по алгоритму.

Единиц три, следовательно надо приписать 10.

Получаем 101110₂

Переведем его в десятичную систему.

101110₂ = 1 х2⁵+0 х2⁴+1 х2³+1 х2²+1 х2¹+0 х2⁰=32+8+4+2=46₁₀

Ответ: R=46