Карточки
Тесты
Главная
Курсы
Подписка
5. Построение алгоритмов для исполнителей: #291365
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом.
- Строится двоичная запись числа $N$.
- Далее эта запись обрабатывается по следующему правилу:
- если число $N$ делится на $3$, то к этой записи дописываются три последние двоичные цифры;
- если число $N$ на $3$ не делится, то остаток от деления умножается на $3$, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа $R$.
- Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа $12=1100_2$ результатом является число $1100100_2=100$, а для исходного числа $4=100_2$ это число $10011_2=19$.
Укажите минимальное число $R$, большее $151$, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.
Рассмотрим три возможных остатка от деления $N$ на $3$.
Если $N$ делится на $3$, дописываются три последние цифры двоичной записи: $R=8N+(N\bmod 8)$.
Для $N=18$: $R=8\cdot18+2=146<151$.
Для следующего кратного $3$ числа $N=21$: $R=8\cdot21+5=173$.
Если остаток от деления $N$ на $3$ равен $1$, дописывается число $3=11_2$: $R=4N+3$.
При $N=37$: $R=4\cdot37+3=151$, но требуется число больше $151$. Следующее число с остатком $1$ при делении на $3$ — $40$: $R=4\cdot40+3=163$.
Если остаток от деления $N$ на $3$ равен $2$, дописывается число $6=110_2$: $R=8N+6$.
При $N=17$: $R=8\cdot17+6=142<151$.
Следующее число с остатком $2$ при делении на $3$ — $20$: $R=8\cdot20+6=166$.
Минимальное из полученных значений: $\min(173,163,166)=163$.
20
