Условие:
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи справа дописываются разряды по следующему правилу. Если число кратно 3, то дописывается 010, иначе в конец дописывается двоичная последовательность, являющаяся результатом умножения 5 на остаток от деления числа N на 3.
Например, для числа 13 двоичная запись 1101 преобразуется в запись 1101101, для числа 9 двоичная запись 1001 преобразуется в 1001010.
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите значение N, в результате обработки которого будет получено минимально возможное четное значение R, большее 300. Если таких значений несколько, приведите минимальное подходящее значение.
Решение:
Мы анализируем алгоритм, который по натуральному числу N строит новое число R по следующим правилам: 1. Записываем число N в двоичной системе. 2. Если N делится на 3 (N mod 3 = 0), то к двоичной записи дописывается «010». Иначе (N mod 3 = 1 или 2) к записи дописывается двоичная запись числа 5·(N mod 3). Нам нужно найти такое натуральное число N, чтобы полученное число R, интерпретированное как двоичное представление, было: – четным, – больше 300, – и при этом минимальным (если несколько N дают одно и то же минимальное R, выбираем наименьшее N). Чтобы работать с R, заметим следующее: если к ...
