Автор статьи: Андрей Рогов
Пятое задание из ЕГЭ по информатике проверяет понимание алгоритмов, работающих с числами. Оно считается базовым по сложности. Обычно задание связано с переводом числа из десятичной системы счисления в другую, модификацией числа и переводом обратно. Вопросы могут касаться поиска максимального или минимального результата алгоритма или определения исходного числа, дающего заданный результат. Программное обеспечение для решения не требуется.
Способы решения
Это задание перешло в компьютерный вариант экзамена из «бумажного» практически без изменений. Но мы всё же не советуем делать это задание без компьютера.
Задание можно решать двумя способами: программным и аналитическим (ручным). Программное решение популярно из-за своей универсальности и шаблонности, но требует внимательности и аккуратности при написании кода. Опечатка или новая формулировка задания — и вот всё пошло не так.
Аналитический метод, при котором компьютер используется только для перевода чисел между системами счисления, тоже очень полезен. Он помогает развивать мышление и навыки анализа, что важно для будущих программистов. Этот метод может быть быстрее и проще для уверенных учеников, которые неплохо разбираются в алгоритмах.
Если вы испытываете сложности с программированием, стоит освоить аналитику. Обычно в заданиях используется двоичная система счисления, но в 2023 году на экзамене была троичная, из-за чего процент решаемости сильно упал:
- 2021 год — 58,6 %
- 2022 год — 44,9 %
- 2023 год — 35,5 %
- 2024 год — 51,8 %
Скорее всего, это связано со встроенной функцией bin() в Python. Она возвращает двоичную запись числа, а вот для перевода в троичную систему счисления такой функции нет.
Однако около 90% выпускников, которые набирают больше 80 баллов, справляются с этим заданием. Важно уметь адаптироваться и решать задачи аналитически. Если овладеть этим навыком, то можно обходиться без шаблонных решений и уверенно справляться с любыми изменениями в заданиях.
Как решать пятое задание с помощью Python и электронных таблиц
Чтобы решить задание, нужно уметь переводить числа из десятичной системы в другие системы счисления и обратно. Обратите внимание на один нюанс: многие функции программирования работают только с системами счисления, основания которых находятся в диапазоне от 2 до 36. Это связано с тем, что в алфавите этих функций используются цифры и латинские буквы для представления чисел.
Разберёмся, как решать задание аналитически. Сначала напомним правила Python для перевода числа в разные системы счисления.
# Перевод в двоичную
b = bin(x)[2:]
b = f'{x:b}'
b = format(x, 'b')
# Перевод в восьмеричную
b = oct(x)[2:]
b = f'{x:o}'
b = format(x, 'o')
# Перевод в шестнадцатеричную
b = hex(x)[2:]
b = f'{x:x}'
b = format(x, 'x')
# Перевод в десятичную
a = int(x, b)
где b — основание системы счисления, в которой записано число x (в виде строки).
В режиме Shell можно легко использовать функции для перевода чисел между системами счисления. Для этого не требуется использование команды print или создание переменных — просто введите нужную команду и нажмите Enter, чтобы сразу увидеть результат.
>>> bin(123)
'0b1111011'
Функция возвращает строку, в начале которой префикс '0b'. Чтобы избавиться от него и получить только двоичную запись, используют срез от второго элемента и до конца строки либо другие варианты получения двоичной записи.
>>> bin(123)[2:]
'1111011'
>>> f'{123:b}'
'1111011'
>>> format(123, 'b')
'1111011'
В режиме Shell удобно делать однократные переводы. Чтобы не набирать команду заново, достаточно использовать сочетание Alt + P. Тогда последняя набранная команда вновь появится в строке ввода. Но если нужно много переводов, удобнее написать цикл.
>>> for i in range(100, 110):
... i, format(i, 'b')
...
(100, '1100100')
(101, '1100101')
(102, '1100110')
(103, '1100111')
(104, '1101000')
(105, '1101001')
(106, '1101010')
(107, '1101011')
(108, '1101100')
(109, '1101101')
Пример использования функции int:
# перевод числа 10110101 из двоичной системы счисления в десятичную 181
>>> int('10110101', 2)
# перевод числа 123 из четверичной в десятичную 27
>>> int('123', 4)
В Python нет встроенной функции для перевода из десятичной в другие системы счисления, поэтому понадобится написать алгоритм. Его можно оформить, например, в виде следующей функции:
def to_base(x, b):
s = []
while x > 0:
s.append(x % b)
x //= b
s.reverse()
return s
Функция вычисляет список из остатков деления числа на новое основание. Список пригодится для универсальности, так как для систем счисления с основанием больше 10 нужно использовать буквы в качестве цифр.
Элементы в списке представляют собой числовые значения цифр. Например, если в числе есть буквы, они будут записаны как числа больше 9. Так, буква A будет обозначена числом 10.
>>> to_base(123, 2)
[1, 1, 1, 1, 0, 1, 1]
>>> to_base(123, 12)
[10, 3]
Теперь рассмотрим, как использовать электронные таблицы для решения задания № 5. В MS Excel и Libre Office Calc есть функция «основание (число, основание)». Она позволяет переводить числа из десятичной в любую систему счисления и принимает два аргумента:
- число для перевода
- основание системы счисления, в которую требуется перевести
Противоположная ей по действию функция «дес (число; основание)» переводит число в десятичную систему счисления.
Ход аналитического решения кардинально отличается от решения программой. Мы не используем перебор исходных значений алгоритма и полученных результатов, а, наоборот, отталкиваемся от результата и определяем подходящее исходное значение.
Задача 1. Аналитическое решение с помощью Python
Для практики решим несколько задач. Вот первая из них.
Обратите внимание на шаг 2. После его выполнения возможны два результата. Если выполнен пункт «а», число заканчивается на *01, где * — любая последовательность нулей и единиц. Если выполнен пункт «б», число имеет вид 1 × 1.
Решать будем с конца. Нам нужно найти минимальное исходное число. Оба пункта увеличивают число на два разряда, поэтому начнём с минимального возможного результата алгоритма. Например, берём число 157 (минимальное значение после 156) и переводим его в двоичную систему с помощью Python.
>>> bin(157)
'0b10011101'
Число оканчивается на 01, поэтому, возможно, подходит пункт «а». Уберём 01 с конца числа и получим 100111₂. Пункт «а» применяется, если число чётное. Число 100111₂ нечётное, поскольку оканчивается на 1, но в этом можно убедиться, переведя его в десятичную систему счисления.
>>> int('100111', 2)
39
Следовательно, пункт «а» тут неприменим.
Проверим пункт «б». Если убрать первую и последнюю единицу из числа, останется 001110₂. Но число не могло начинаться с нулей, поэтому пункт «б» тоже не применим. Возьмём следующее по величине число — 158.
>>> bin(158)
'0b10011110'
Оно тоже не могло быть результатом, поскольку не оканчивается на 01 и не подходит под маску 1 × 1. Следующее подходящее число — 161.
>>> bin(161)
'0b10100001'
Оно оканчивается на 01. До того, как дописали 01, число было 101000₂.
>>> int('101000', 2)
40
Если бы в задаче спрашивали о минимальном R, мы бы нашли ответ. Но вопрос о минимальном N. Поэтому, возможно, пунктом «б» можно получить подходящее число из меньшего N.
Найдём минимальное число, большее 156, которое начинается с двух единиц в двоичной записи и оканчивается на единицу. Это число 193.
>>> int('11000001', 2)
193
До добавления единиц в начало и конец число было 100000₂. Оно чётное, поэтому нам не подходит. Возьмём число на 1 больше, 100001₂. Оно нечётное, поэтому к нему допишется 1 в начало и конец.
>>> int('100001', 2)
33
Число 33 меньше, чем 40, подходит под все требования и является минимальным.
На первый взгляд решение кажется сложным, но многие задания получится выполнить значительно быстрее, чем написать программу, если разобраться во всех этапах. К тому же решить задание двумя способами куда надёжнее, чем одним.
Задача 2. Аналитическое решение с помощью электронных таблиц
Перейдём ко второй задаче.
Поскольку мы используем троичную систему, обратимся к электронным таблицам. Рассмотрим форму итогового числа:
- Если выполнен пункт «а», то последние две цифры равны предпоследним и число будет выглядеть как *abab.
- Если выполнен пункт «б», число не делится на 3, то его остаток при делении на 3 равен 1 или 2. После умножения на 5 это будут числа 5 и 10 соответственно. Поэтому число будет оканчиваться этими числами, переведёнными в троичную систему.
Начнём с перевода чисел 5 и 10 в троичную систему.
Теперь перейдём к поиску R. Начиная с числа 134 будем строить троичную запись. Так мы найдём три числа, каждое из которых можно получить, используя этот алгоритм.
Возьмём первое число, 12012₃. До добавления 12 в конец число было равно 120₃. Переведём его в десятичную систему счисления.
Это число 15, оно кратно трём. К нему по алгоритму подходит пункт «а», поэтому число 12012₃ не может быть результатом.
Следующее число 12020₃. При дублировании добавились бы цифры 2 и 0, поэтому исходное число — это 120₃. Его мы уже переводили в десятичную систему счисления, это 15. Следовательно, оно нам подходит. Ответ 141.
Заключение
Хотя большинство выпускников решают задание № 5 с помощью программирования, аналитический метод часто бывает таким же эффективным, а иногда и быстрее. Поэтому при подготовке важно пробовать разные способы решения. Также полезно решить подборку задач для практики.