Задача 6
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
- Строится двоичная запись числа N.
- К этой записи дописываются справа ещё два разряда по следующему правилу:
- а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
- б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, которое превышает число 97 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Проанализировав условие замечаем, что фактически к числу дважды дописывается бит чётности, причем уже после шага «а» у нас всегда получится чётное число единиц, поэтому шаг «б» всегда добавит ноль.
Если в конце двоичной записи числа стоит 0, значит, оно чётное, поэтому в результате работы алгоритма должно обязательно получиться чётное число. Поэтому мы будем рассматривать только четные числа.
Наименьшее четное число, которое превышает 97 - 98. Переведем его в двоичную систему счисления:
1100010 - результат работы алгоритма, число R. Исходное число N можно получить отбрасыванием двух последних разрядов в двоичной записи.
Переведем число N из двоичной системы счисления в десятичную:
Возьмем следующее число (25) и применим к двоичной записи этого числа алгоритм:
Сумма цифр двоичной записи равна 3, поэтому:
Переведем полученное число в десятичную систему счисления:
Ответ: 102.
