Решение: Максимальное число после преобразования
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом.
1. Строится двоичная запись числа $N$.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число $N$ делится на 3, то к этой записи дописываются три последние двоичные цифры;
б) если число $N$ на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа $R$.
Например, для исходного числа $12 = 1100_2$ результатом является число $1100100_2 = 100$, а для исходного числа $4 = 100_2$ это число $10011_2 = 19$.
Укажите максимальное число $R$, не превышающее 162, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.
Решение по шагам
4 шагаЕсли $N$ делится на 3, приписываются три последние двоичные цифры. Тогда $R = 8N + (N \bmod 8)$. При условии $R \leq 162$ имеем $N \leq 20$.
Если $N \bmod 3 = 1$, к двоичной записи приписывается число $3 = 11_2$. Поэтому $R = 4N + 3$. Из условия $4N + 3 \leq 162$ следует $N \leq 39$. Наибольшее число, не делящееся на 3 и дающее максимальный результат, — $N = 37$.
Для $N = 37$ имеем $37 \bmod 3 = 1$, поэтому к записи $100101_2$ приписывается $11_2$: $10010111_2 = 151$.
Если $N \bmod 3 = 2$, приписывается число $6 = 110_2$, поэтому $R = 8N + 6$. При $R \leq 162$ получается $N \leq 19$, и этот случай не даёт результата больше 151.
Где здесь ошибаются
Забывают, что приписывание двоичных цифр справа соответствует умножению на степень двойки.
Используют десятичное представление остатка вместо его двоичной записи.
Не проверяют ограничение $R \leq 162$.