Максимальное значение N
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом.
1. Строится двоичная запись числа $N$.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число $N$ делится на 3, то к этой записи дописываются три последние двоичные цифры;
б) если число $N$ на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа $R$.
Например, для исходного числа $12 = 1100_2$ результатом является число $1100100_2 = 100$, а для исходного числа $4 = 100_2$ результатом является число $10011_2 = 19$.
Укажите максимальное число $N$, после обработки которого с помощью этого алгоритма получается число $R$, меньшее чем 76.
Условие как в банке ФИПИ — открыть и сверить
| На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. Далее эта запись обрабатывается по следующему правилу: а) если число N делится на 3, то к этой записи дописываются три последние двоичные цифры; б) если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись Полученная таким образом запись является двоичной записью искомого числа R. 3. Результат переводится в десятичную систему и выводится на экран. Например, для исходного числа 12 = 11002 результатом является число 11001002 = 100, а для исходного числа 4 = 1002 результатом является число 100112 = 19. Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее чем 76. | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Рассмотрите отдельно случаи, когда $N$ делится на 3 и когда остаток от деления на 3 равен 1 или 2.
2Наводящая — какие числа считатьуровень 2 из 3
Если к двоичной записи $N$ дописывается двоичная запись числа $x$, то новое число равно $N \cdot 2^k + x$, где $k$ — число дописанных цифр.
3Прямая — фактически решениеуровень 3 из 3
Для $N \not\equiv 0 \pmod 3$: при остатке 1 получаем $R=4N+3$, при остатке 2 — $R=8N+6$. Проверка подходящих чисел даёт максимум $N=16$.