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