Опубликовано 11.06.2017 по предмету Информатика от Гость >> <<

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

Ответ оставил Гость

1. Отметим, что приписывание к двоичному числу двух младших разрядов предполагает предварительный сдвиг этого числа влево на два разряда (что равносильно умножению на 2²=4), а затем установку двух младших разрядов в соответствующие приписываемым битам значения. Следовательно, можно записать, что 4N+a>43, где a - число, образованное приписываемыми справа битами, которое не может превышать 11(2)=3(10)
4N+[0..3]≥44, откуда минимальное N=11
Теперь запишем N=11 в двоичной системе и применим к нему заданный алгоритм.
N=1011(2), число единиц три, нечетное, приписываем 1, получая 10111.
Теперь число единиц четное, приписываем 0 и получаем R=101110(2).
В десятичной записи ему соответствует число 46.
Ответ: 46