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