Данное задание проверяет умение восстанавливать исходные данные линейного алгоритма по результатам его работы. Задание базового уровня, на его выполнение отводится 4 минуты согласно спецификации ЕГЭ.
Условие задачи
На вход алгоритма подаётся натуральное число n. Алгоритм строит по нему новое число R следующим образом:
- Строится двоичная запись числа n.
- Эта запись обрабатывается по следующему правилу:
- а) Если сумма цифр двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на «10».
- б) Если сумма цифр двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на «11».
- Полученная запись является двоичной записью числа R.
Вопрос: Укажите минимальное число n, после обработки которого с помощью этого алгоритма получается число R больше 40. Запишите это число в десятичной системе счисления.
Решение задачи
Для решения задачи эффективнее использовать язык программирования. Ниже приведён код на Python, реализующий данный алгоритм:
for n in range(1, 100): # Перебор чисел от 1 до 99 (ограничение для эффективности)
s = bin(n)[2:] # Получение двоичной записи числа, отрезаем "0b"
if s.count('1') % 2 == 0: # Проверка на чётность суммы цифр (единиц)
s += '0'
s = '10' + s[2:] # Замена первых двух разрядов на "10"
else:
s += '1'
s = '11' + s[2:] # Замена первых двух разрядов на "11"
r = int(s, 2) # Преобразование двоичной строки в десятичное число
if r > 40:
print(n) # Вывод минимального n, удовлетворяющего условию
break # Прерывание цикла после нахождения первого решенияКод перебирает натуральные числа от 1 до 99. Для каждого числа строится двоичная запись, обрабатывается согласно условию задачи, и полученное двоичное число преобразуется обратно в десятичное. Как только находится число R больше 40, соответствующее значение n выводится на экран и цикл прерывается.
Ответ
Запустив данный код, получаем ответ: 16. Минимальное число n, удовлетворяющее условию задачи, равно 16.