На вход алгоритма подаётся натуральное число n. Алгоритм строит по нему новое число p следующим образом:
- Строится двоичная запись числа n.
- К этой записи дописываются справа ещё два разряда по следующему правилу: складываются все цифры двоичной записи числа n, и остаток от деления суммы на 2 дописывается в конец числа справа. Эта операция повторяется дважды.
- Полученная запись, на два разряда больше, чем запись исходного числа n, является двоичной записью искомого числа p.
Необходимо указать наименьшее число n, для которого результат работы данного алгоритма (p) больше 77. Ответ следует записать в десятичной системе счисления.
Разбор решения
Рассмотрим пример. Пусть n = 20.
- Двоичная запись 20: 10100.
- Сумма цифр: 1 + 0 + 1 + 0 + 0 = 2. Остаток от деления на 2 равен 0. Дописываем 0: 101000.
- Сумма цифр: 1 + 0 + 1 + 0 + 0 + 0 = 2. Остаток от деления на 2 равен 0. Дописываем 0: 1010000.
- 1010000<sub>2</sub> = 64 + 16 = 80<sub>10</sub>.
В задании дано число p, и требуется найти n. Поскольку p > 77, возьмём p = 78.
- Двоичная запись 78: 1001110<sub>2</sub>.
- Исключая последние два разряда (10), получаем двоичную запись числа n: 10011<sub>2</sub>.
- 10011<sub>2</sub> = 16 + 8 + 1 = 25<sub>10</sub>. Проверим алгоритм для n = 25.
- Двоичная запись 25: 11001<sub>2</sub>. Сумма цифр: 3, остаток от деления на 2: 1. Дописываем 1: 110011<sub>2</sub>. Сумма цифр: 4, остаток от деления на 2: 0. Дописываем 0: 1100110<sub>2</sub>. Это не 78.
Попробуем другой подход. Так как p > 77, возьмём p = 78. Двоичное представление 78: 1001110. Отбросив последние два бита, получаем 10011. Это 19 в десятичной системе. Проверим:
- Двоичная запись 19: 10011.
- Сумма цифр: 3. Остаток от деления на 2: 1. 100111.
- Сумма цифр: 4. Остаток от деления на 2: 0. 1001110.
- 1001110<sub>2</sub> = 78<sub>10</sub>.
Таким образом, наименьшее число n, удовлетворяющее условию задачи, равно 19.