Автор статьи: Андрей Рогов
О чём задание № 5
Пятое задание ЕГЭ по информатике посвящено числовым алгоритмам. Оно считается базовым по сложности. Обычно задание связано с переводом числа из десятичной системы счисления в другую, его модификацией и переводом обратно. Вопросы могут касаться поиска максимального, минимального результата алгоритма или определения исходного числа, которое приводит к заданному результату. Специальное программное обеспечение для того, чтобы решить задачу, не требуется. В статье по ссылке рассмотрен аналитический подход к заданию, а здесь поговорим о решении с помощью кода на Python.
Основная идея
Вычислительные мощности компьютеров позволяют решить это задание полностью отличным от аналитического подхода способом. Можно перебрать множество начальных значений алгоритма, вычислить для всех конечный результат и получить ответ.
Главное преимущество такого способа — не нужно пользоваться сложной аналитикой. Задача сводится к тому, чтобы корректно записать алгоритм, указанный в задании, на языке программирования. Основная сложность такого решения связана с тем, что действия алгоритма могут быть разнообразными: дописывание символов, их замена, вычисление остатков деления, нахождение суммы цифр и перевод числа в другую систему счисления.
Навыки программирования
В статье об аналитическом способе решения описывались встроенные методы перевода чисел в двоичную, восьмеричную, шестнадцатеричную систему счисления и обратно в десятичную.
Напомним, как они выглядят на языке 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 — основание системы счисления (от 2 до 36), в которой записано число x (в виде строки)
Для перевода чисел в произвольную систему счисления рекомендуем использовать собственную функцию. Вот две её реализации: с хранением результата в виде списка и в виде строки:
def to_base(x, b):
s = []
while x > 0:
s.append(x % b)
x //= b
s.reverse()
return s
def to_base(x, b):
s = ''
while x > 0:
s = str(x % b) + s
x //= b
return s
Функция, которая возвращает результат в виде списка, будет корректно работать со всеми основаниями систем счисления (но вместо буквенных цифр будут числа). Функция со строками будет корректно работать только с основаниями до 10. В этом задании встречались двоичная и троичная системы счисления, поэтому можно использовать обе функции. Вариант с str удобнее, поскольку функция int работает со строками, bin возвращает строку и преобразования чисел удобнее делать через строки. Далее будем использовать именно этот вариант.
Следующий важный навык — работа со строками. Чтобы решить задание № 5, нужно уметь дописывать числа в начало или в конец строки. Помните, что строки в Python — неизменяемые объекты, поэтому в каждом случае нужно будет создавать новые. Необходимо также знать, как работают срезы.
Приведём несколько примеров:
s = '012345'
# строка со второго символа
s[1:]
'12345'
# строка с третьего символа
s[2:]
'2345'
# строка без последнего символа
s[:-1]
'01234'
# строка без двух последних символов
s[:-2]
'0123'
Рассмотрим несколько вариантов решения заданий.
Задача 1. Программное решение с помощью Python
На примере этого задания разберём общий подход. Для начала нужно организовать перебор всех возможных значений N. Нижняя граница понятна: числа натуральные, поэтому минимальное число — 1. Как быть с верхней? Актуальные типы заданий содержат примеры результатов для некоторых исходных чисел. На первом этапе решения можно ограничиться числами, которые есть в примерах, чтобы проверить на них корректность работы алгоритма.
for n in range(1, 13):
На первом шаге алгоритма строится двоичная запись. Можно использовать любой из описанных способов.
b = bin(n)[2:]
На втором шаге нужно проверить исходное число на чётность и дописать необходимые цифры.
if n % 2 == 0: # если число чётное
b = b + '01' # приписать справа
else:
b = '1' + b + '1' # приписать слева и справа
Последний шаг — перевести число в десятичную систему счисления. На этом этапе решения будем выводить все начальные и конечные значения на экран. Полный код программы:
for n in range(1, 13):
b = bin(n)[2:] # двоичная запись числа
if n % 2 == 0: # если число чётное
b = b + '01' # приписать справа
else:
b = '1' + b + '1' # приписать слева и справа
r = int(b, 2) # перевод в десятичную систему счисления
print(n, r)
Вывод программы:
1 7
2 9
3 15
4 17
5 27
6 25
7 31
8 33
9 51
10 41
11 55
12 49
Сверимся с условием задачи. Для числа 5 наша программа вывела 27, для числа 12 — 49, что соответствует условию. Рекомендуем всегда проверять корректность работы алгоритма перед тем, как выполнять задание.
Теперь можем переходить к вопросу задачи. Требуется найти минимальное число N, дающее в результате R больше 156.
Один из самых простых способов получить ответ — расширить границы цикла и просмотреть вывод программы. Это не очень удобно, к тому же есть вероятность ошибиться.
Чтобы видеть в выводе только подходящие результаты, можно его фильтровать:
for n in range(1, 100):
b = bin(n)[2:] # двоичная запись числа
if n % 2 == 0: # если число чётное
b = b + '01' # приписать справа
else:
b = '1' + b + '1' # приписать слева и справа
r = int(b, 2) # перевод в десятичную систему счисления
if r > 156: # фильтр
print(n, r)
Мы расширили границы цикла (теперь он выполняется от 1 до 99) и выводим на экран информацию, только если R больше 156. Первое значение, которое мы увидим на экране, будет подходящим. Также для удобства можно прекратить выполнение цикла после того, как будет найден первый результат, с помощью команды break. Но это будет корректно, только если вопрос задания о наименьшем N.
Задача 2. Программное решение с помощью Python
Видим, что строится троичная запись. Будем использовать функцию для перевода в троичную систему счисления:
def to_base(x, b):
s = ''
while x > 0:
s = str(x % b) + s
x //= b
return s
for n in range(1, 13):
b = to_base(n, 3) # троичная запись числа
if n % 3 == 0: # если число делится на 3
b = b + b[-2:] # приписать справа
else:
b = b + to_base(n % 3 * 5, 3)
r = int(b, 3)
print(n, r)
Как и в прошлый раз, сначала проанализируем вывод программы и сравним его с условием задачи. Далее перейдём к поиску R. Действия, выполняемые в зависимости от условия, не равноценны. Они по-разному меняют число, давая нелинейную зависимость. Это хорошо видно по выводу программы:
1 14
2 64
3 30
4 41
5 145
6 60
7 68
8 226
9 81
10 95
11 307
12 111
Первое R больше 133, это 145, но оно может быть не минимальным. Нам нужно получить гарантированно правильный ответ. Для этого организуем фильтрацию вывода с двух сторон: ограничим и верхнее, и нижнее значение. Нам требуется R больше 133, мы видим в выводе 145. Попробуем определить, появятся ли другие значения больше 133, но меньше 145. Не забудем увеличить границу цикла:
def to_base(x, b):
s = ''
while x > 0:
s = str(x % b) + s
x //= b
return s
for n in range(1, 100):
b = to_base(n, 3) # троичная запись числа
if n % 3 == 0: # если число делится на 3
b = b + b[-2:] # приписать справа
else:
b = b + to_base(n % 3 * 5, 3)
r = int(b, 3)
if r > 133 and r < 145: # фильтр
print(n, r)
Программа выдаст ещё одно число:
15 141
Следовательно, наименьшим числом больше 133 будет 141.
В рассмотренных заданиях было достаточно перебрать числа от 1 до 100. Диапазон мы выбрали исходя из того, какие результаты дают эти числа. Однако в других заданиях такого диапазона может быть недостаточно, а слишком большой перебор может занять много времени.
Внимательно выбирайте диапазон перебора. Некоторые варианты задач ограничивают минимальное или максимальное значение N. Вот пример такого задания:
Другие задания
Рассмотренные задачи не исчерпывают всего многообразия задания № 5. Например, в демоверсии ЕГЭ за 2017 год оно выглядело так (тогда его номер был шестым):
Здесь речь о переводе в другую систему счисления не идёт, но требуется разбить трёхзначное число на цифры, что довольно просто сделать с помощью целочисленной арифметики. Такой тип задания не встречался на экзаменах последние восемь лет, поэтому рассматривать его решение мы не будем.
Заключение
Задание № 5 часто можно решить шаблонным кодом. Увы, в стрессовой обстановке экзамена даже элементарные знания, которые всегда выручали, могут забыться. Мы рекомендуем не заучивать код, а научиться использовать его в своих целях. Навыки его написания должны быть первичны, и, обладая ими, можно приступать к такому типу решения. Без крепкой базы программирования это задание нужно научиться решать аналитически.
При подготовке к ЕГЭ рекомендуем использовать несколько способов решения для каждого задания.
Для закрепления материала рекомендуем последовательно решить три подборки задач:
- отработайте базовые алгоритмы модификации записей на задачах с двоичной системой счисления
- реализуйте собственную функцию перевода и более сложную логику обработки строк на задачах с другими системами счисления
- освойте работу с цифрами числа через целочисленную арифметику и операции деления с остатком на задачах с десятичной системой счисления