ЕГЭ · ЗАДАНИЕ 5
Алгоритмы обработки чисел · №31502
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N чётное, то к этой записи справа и слева дописываются по две единицы;
б) если число N нечётное, то в конец двоичной записи (справа) дописываются два нуля, а в начало (слева) дописывается единица.
Полученная таким образом запись (в ней на три или четыре разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 1310 = 11012 результатом является число 11101002 = 11610, а для исходного числа 610 = 1102 это число 11110112 = 12310.
Укажите наименьшее число R, превышающее 95, которое может быть результатом работы данного алгоритма. В ответе запишите это число в десятичной системе счисления.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 100
1. Переведём действия в Python
Для чётного N собираем строку "11" + b + "11", для нечётного — "1" + b + "00". В ответе требуется наименьшее R, поэтому нельзя прекращать перебор на первом подходящем N.
values = []
for n in range(1, 96):
b = bin(n)[2:]
result = '11' + b + '11' if n % 2 == 0 else '1' + b + '00'
r = int(result, 2)
if r > 95:
values.append((r, n))
print(min(values)) # (100, 9)2. Проверим границы перебора
В обеих ветках число R больше 4N: запись сдвинута на два разряда, слева добавлена хотя бы одна единица. При N ≥ 96 получим R > 384 — это уже больше найденного 100. Поэтому выбранного диапазона достаточно.
3. Проверим ответ вручную
N = 9 → 1001₂ → 1100100₂ = 64 + 32 + 4 = 100. Для чётного N = 4 получается R = 115: первое найденное подходящее N не обязательно даёт минимальное R.