Карточки
Тесты
Главная
Курсы
Подписка
5. Построение алгоритмов для исполнителей: #291377
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом.
- Строится двоичная запись числа $N$.
- Далее эта запись обрабатывается по следующему правилу:
- если число $N$ делится на $3$, то к этой записи дописываются три последние двоичные цифры;
- если число $N$ на $3$ не делится, то остаток от деления умножается на $3$, переводится в двоичную запись и дописывается в конец числа.
- Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа $12=1100_2$ результатом является число $1100100_2=100$, а для исходного числа $4=100_2$ результатом является число $10011_2=19$.
Укажите максимальное число $N$, после обработки которого с помощью этого алгоритма получается число $R$, меньшее чем $108$.
Рассмотрим три случая.
Если $N$ делится на $3$, то: $R=8N+(N\bmod 8)$.
При $N=12$: $R=8\cdot12+4=100<108$.
Следующее кратное $3$ число — $15$, для него $R=127>108$. Кандидат — $12$.
Если остаток от деления $N$ на $3$ равен $1$, дописывается число $3=11_2$: $R=4N+3$.
Из условия $4N+3<108$ получаем $N<26{,}25$. Наибольшее число с остатком $1$ при делении на $3$ — $25$: $R=4\cdot25+3=103<108$.
Если остаток от деления $N$ на $3$ равен $2$, дописывается число $6=110_2$: $R=8N+6$.
Из условия $8N+6<108$ получаем $N<12{,}75$. Наибольшее число с остатком $2$ при делении на $3$ — $11$: $R=8\cdot11+6=94<108$.
Максимальное из найденных значений: $\max(12,25,11)=25$.
20
