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