Question

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

Answer 1

Проанализируем алгоритм. Правило а) добавляет справа нуль при четном количестве единиц или единицу при нечетном. Правило б) делает то же самое, но с учетом правила а) количество единиц всегда будет четным, поэтому всегда будет добавляться ноль.
Подытоживая, можно утверждать, что к числу будут дописаны справа:
- 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