Решение: Максимальное значение N
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом.
1. Строится двоичная запись числа $N$.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число $N$ делится на 3, то к этой записи дописываются три последние двоичные цифры;
б) если число $N$ на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа $R$.
Например, для исходного числа $12 = 1100_2$ результатом является число $1100100_2 = 100$, а для исходного числа $4 = 100_2$ результатом является число $10011_2 = 19$.
Укажите максимальное число $N$, после обработки которого с помощью этого алгоритма получается число $R$, меньшее чем 76.
Решение по шагам
6 шаговЕсли $N$ делится на 3, дописываются три последние двоичные цифры числа $N$. Их значение равно $N \bmod 8$, поэтому
$$R=8N+(N\bmod 8)$$Для чисел, делящихся на 3, условию $R<76$ удовлетворяет, в частности, $N=9$: $R=8\cdot9+1=73$. Следующее такое число, $N=12$, уже даёт $R>76$.
Если остаток от деления $N$ на 3 равен 1, дописывается двоичная запись числа 3, то есть две цифры. Поэтому
$$R=4N+3$$При остатке 1 максимальное подходящее число — $N=16$: $R=4\cdot16+3=67<76$. Следующее число с таким остатком — $N=19$, для него $R=79$.
Если остаток от деления равен 2, дописывается двоичная запись числа 6, то есть три цифры:
$$R=8N+6$$В этом случае максимальное подходящее число — $N=8$, для которого $R=8\cdot8+6=70$. Сравнивая найденные значения, получаем максимальное $N=16$.
Где здесь ошибаются
Не учитывать, что число 3 записывается в двоичной системе как $11$, а число 6 — как $110$.
Использовать одинаковый множитель $2^k$ для всех случаев.
Искать максимальное значение $R$, а не максимальное значение $N$.