Навигация по странице
О задании
Задание 17 ЕГЭ по информатике нацелено на проверку умений перебора последовательности целых чисел. В данном задании предстоит работать с текстовым файлом, в каждой строке которого находится целое число. В зависимости от задания эти числа могут быть как положительными, так и отрицательными, что незначительно, но все же влияет на решение задания.
В целом, основная сложность данного задания в его витиеватой и запутанной формулировке. Ваша цель здесь – вдумчиво прочитать текст задания и выписать все необходимые условия, которым должны отвечать подходящие числа. В ответ всегда требуется дать 2 числа: количество подходящих пар или троек чисел и результат какого-либо выражения с ними (максимальная сумма элементов, минимальная сумма квадратов и т.д.).
В этой статье мы разберем основные подходы для грамотной и безопасной работы с файлами, вспомним методы и функции для работы со списками и разберем алгоритм решения задания 17 на основе нескольких примеров.
Работа с файлами
Подробно работу с файлами мы уже разбирали ранее (здесь и здесь). Сейчас же просто кратко изложим основные моменты, на которые стоит обратить внимание, если вам предстоит считывать данные из файла.
Для начала запомните, что с файлами в Python следует всегда работать только используя менеджер контекста. Он позволяет гарантированно закрыть файловый поток, тем самым обеспечивая безопасное выполнение вашего кода.
Понятно, что для небольших программ, которые помогают вам решать задания из ЕГЭ, такое может быть слегка излишне. Но все же, если вы в будущем планируете писать код, то лучше сразу приучайтесь делать это грамотно, соблюдая все рекомендации сообщества.
Открываем файлы мы следующей конструкцией:
with open('file.txt') as f:
Далее, внутри блока менеджера контекста следует код, в котором и происходит обработка данных из файла: их чтение, запись или перемещение указателя внутри файла.
После того как поток управления выходит за пределы этого блока, файл автоматически закрывается, освобождая ресурсы операционной системы. При таком подходе файл не будет «висеть» открытым на протяжении всех вычислений, которые будут происходить, пока программа не закончит свою работу.
Причем совершенно не нужно писать весь остальной код внутри блока with. Открыли файл, считали данные в свою переменную, закрыли его — больше уже он вам не пригодится.
Теперь поговорим о том, как же правильно извлекать данные из файла. Вспомним, что в 17 задании ЕГЭ данные в файле у нас представлены в виде последовательности чисел: по одному числу в каждой строчке. Например, файл содержит такие данные:
«567
51360
76956
45215
22129
34648»
Как же их правильно считать в одну переменную?
У нас есть 3 базовых функции, которые позволяют читать данные из текстового файла: read(), readline() и readlines(). Вы можете использовать любую из них на ваше усмотрение. Но, забегая вперёд, нам потребуется работать с данными в виде списка целых чисел.
Можно считать все данные с помощью readlines(), которая поместит значение каждой строки в список. Но тогда придётся заново проходиться в цикле по каждому элементу этого списка и приводить его к целочисленному типу.
Более лаконичным и эффективным способом будет использование списочного включения. Дело в том, что файловые объекты в Python поддерживают протокол итерации, то есть мы можем буквально поместить этот объект в цикл for и в каждой итерации цикла получать по одной строке из файла.
В таком случае можно написать следующее списочное включение, которое позволит в цикле перебрать каждую строку из файла, привести значение этой строки к целочисленному типу и сохранить как элемент списка:
data = [int(line) for line in f]
Таким образом, весь код, который нам понадобится для чтения данных из файла и сохранения их в виде списка целых чисел представлен ниже:
with open('file.txt') as f:
data = [int(line) for line in f]
Работа со списками
Итак, данные извлечены из файла и сохранены в список. Теперь нужно их как-то обработать, верно? Рассмотрим работу нескольких функций и методов для работы со списками и научимся быстро и легко разом обрабатывать пары и тройки чисел в последовательности.
Зачастую в 17 заданиях требуется найти максимальное или минимальное значение в списке. Для этого можно использовать функции max() и min() соответственно.
Причем это универсальные функции, которые могут работать как с числами, так и со строками. Для чисел они возвращают максимальное или минимальное значение числа, а для строк — самую длинную или короткую строку.
Например, данный код позволяет вернуть самое большое целое число из списка:
numbers = [5, 2, 9, 1, 5, 6]
max_number = max(numbers)
print(max_number)
>>>9
Если мы работаем со списком строк, то функция min() вернёт строку, которая является лексикографически наименьшей (то есть первой в алфавитном порядке или согласно порядку символов в Unicode).
Например среди строк: «вишня», «банан» и «апельсин» лексикографически наименьшей является строка, начинающаяся на букву «а» — «апельсин».
words = ["вишня", "банан", "апельсин"]
min_word = min(words)
print(min_word)
>>>апельсин
Если же вам нужно вернуть количество элементов в списке, то можно использовать глобальную функцию len().
Например, выведем на экран количество элементов в списке:
numbers = [5, 2, 9, 1, 5, 6]
length = len(numbers)
print(length)
>>>6
Для нахождения суммы чисел в списке целесообразно будет использовать уже готовую функцию sum().
Для примера найдём сумму целых чисел:
numbers = [5, 2, 9, 1, 5, 6]
total = sum(numbers)
print(total)
>>>28
Давайте проверим работу всех функций в одном коде. Представим, что необходимо найти разницу между максимальным и минимальным элементами списка, а также вычислить среднее арифметическое всех его элементов.
Для этого воспользуемся таким кодом:
numbers = [10, 20, 30, 40, 50]
# Находим минимальный и максимальный элементы
min_num = min(numbers)
max_num = max(numbers)
# Вычисляем разницу
difference = max_num - min_num
# Вычисляем среднее арифметическое
average = sum(numbers) / len(numbers)
print("Разница между max и min:", difference)
print("Среднее арифметическое:", average)
>>>Разница между max и min: 40
>>>Среднее арифметическое: 30.0
Для формирования итогового списка, количество элементов которого и будем давать в ответ, нужно как-то добавлять в него новые значения, соответствующие всем условиям. Для добавления элементов в конец списка используется метод append().
Он вызывается у объекта списка (через точку) и принимает один аргумент — элемент, который нужно добавить в конец этого объекта.
Например, у нас есть список из трёх значений: 1, 2 и 3. Добавим в него еще одно значение:
numbers = [1, 2, 3]
numbers.append(4)
print(numbers)
>>>[1, 2, 3, 4]
По большому счёту, это все функции, которые вам понадобятся при решении 17 задания.
Но также стоит отметить еще один момент. Вам понадобится одновременно проверять пары или тройки элементов. То есть необходимо будет перебирать по 2 или 3 числа последовательно, с перекрытием.
Например, в списке [1, 2, 3, 4, 5] нужно перебрать тройки элементов:
1 2 3
2 3 4
3 4 5
Неопытные программисты могут сделать это через обычный цикл for i in range() , в котором будут присваивать новым переменным значения по индексам нашего списка. Например, так:
nums = [1, 2, 3, 4, 5]
# Перебираем по 3 числа с шагом 1
for i in range(len(nums) - 2):
x, y, z = nums[i], nums[i + 1], nums[i + 2]
print(x, y, z)
>>>1 2 3
>>>2 3 4
>>>3 4 5
Но никогда не помещайте в range() длину итерируемого объекта, чтобы работать с его индексами! Это очень неэффективный и времязатратный подход. Если хотите работать с индексами – используйте enumerate()! А в нашем же случае гораздо эффективнее, лаконичнее и быстрее достичь задуманной цели можно, используя функцию zip().
Функция zip() в Python позволяет объединять элементы из нескольких итерируемых объектов в кортежи. Причем каждый i-й кортеж содержит i-й элемент каждого из переданных итерируемых объектов.
Продемонстрируем работу этой функции на простом примере. Есть два списка:
- Первый содержит числа от 1 до 3: [1, 2, 3]
- Второй содержит только буквы: [‘a’, ‘b’, ‘c’]
Мы же хотим видеть список из кортежей, где каждой цифре соответствует буква. Реализуем это с использованием функции zip():
list1 = [1, 2, 3]
list2 = ['a', 'b', 'c']
result = zip(list1, list2)
print(list(result))
>>>[(1, 'a'), (2, 'b'), (3, 'c')]
Теперь вернёмся к нашей задаче. Логично предположить, что, передавая на вход функции zip() сначала весь список, затем список без первого элемента и список без второго элемента, мы можем получить за первую итерацию первую тройку элементов. И с каждой следующей итерацией значения из списка будут постепенно перебираться в виде таких троек.
Продемонстрируем это на следующем коде:
nums = [1, 2, 3, 4, 5]
for x, y, z in zip(nums, nums[1:], nums[2:]):
print(x, y, z)
>>>1 2 3
>>>2 3 4
>>>3 4 5
Именно такой подход мы и будем использовать в своих решениях 17 задания.
Алгоритм решения
Теперь, когда вся необходимая теория изложена, можем смело перейти к решению 17 задания. Как таковых типов здесь выделить не получится, задания отличаются друг от друга незначительно. Разберём 4 примера этого задания, на которых можно будет продемонстрировать все основные отличия в формулировках.
Пример 1
Задание 1700
«В файле содержится последовательность натуральных чисел.
Её элементы могут принимать целые значения от 1 до 100 000 включительно. Определите количество пар последовательности, в которых остаток от деления хотя бы одного из элементов на 16 равен минимальному элементу последовательности. В ответе запишите количество найденных пар, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности»
Итак, сначала будем выделять ключевые моменты из формулировки задания:
- Работать будем с парами элементов
- Числа будут только положительные (от 1 до 100 000)
- Будем искать остаток от деления каждого элемента на 16
- Сравнивать будем с минимальным элементом всей последовательности
- В ответе нам нужна будет максимальная сумма элементов
Такое разбиение поможет вам лучше понять условие и не запутаться в формулировках. Постарайтесь для каждого задания также тезисно выписывать части условия и подчеркивать для себя ключевые слова! В конце этого примера мы покажем, как выполняется каждый пункт в нашем коде.
Решение начнём с того, что откроем файл и считаем все данные в переменную data:
with open('1700.txt') as f:
data = list(map(int, f))
После этого найдём минимальный элемент в data и сформируем пустой список answer, в который будем добавлять значения, удовлетворяющие условию.
min_el = min(data) answer = []
Далее перебираем пары элементов из списка data и проверяем, что остаток от деления хотя бы одного элемента равен значению min_el. Если это так, то будем добавлять сумму этих элементов в список answer:
for x, y in zip(data, data[1:]):
if x % 16 == min_el or y % 16 == min_el:
answer.append(x + y)
В ответ нужно дать количество элементов в списке answer и максимальное значение из него.
print(len(answer), max(answer))
Полный код для решения данного задания следующий:
with open('1700.txt') as f:
data = list(map(int, f))
min_el = min(data)
answer = []
for x, y in zip(data, data[1:]):
if x % 16 == min_el or y % 16 == min_el:
answer.append(x + y)
print(len(answer), max(answer))
>>>1214 176024
Теперь, как и заявляли в начале, давайте разберём, как выполняется каждый пункт из списка, написанного выше.
То, что мы работаем с парами элементов, находит своё отражение в количестве переменных и количестве срезов в цикле: for x, y in zip(data, data[1:]):
При работе с положительными числами мы никак не меняем код программы. Но если в условии сказано, что числа могут быть и отрицательными, то следует применять к каждому числу функцию abs(), если требуется проверить делимость числа или подсчитать количество цифр в нём. Это мы рассмотрим в следующем примере.
Третий пункт из списка означает условие, которое будет проверяться в решении. В дальнейшем эти условия будут гораздо сложнее, так что мы будем выносить их в отдельную функцию.
В четвёртом пункте мы отмечаем, что работаем с минимальным элементом. Его значение мы ищем в следующей строчке: min_el = min(num for num in data)
Теперь пятый пункт: слово «максимальная» означает, что в ответе мы будем использовать функцию max(). А то, что нам нужна сумма чисел, отражается в элементе, который будет добавляться в список answer: answer.append(x + y).
В дальнейшем вы увидите, что все решения строятся по одному и тому же шаблону и различия между ними как раз и кроются в разобранных ранее пунктах.
Пример 2
Задание 1701
«В файле содержится последовательность целых чисел. Её элементы могут принимать целые значения от -100000 до 100000 включительно. Определите количество троек последовательности, в которых хотя бы один элемент является пятизначным числом и оканчивается на 43, а сумма квадратов элементов тройки не больше квадрата максимального элемента последовательности, являющегося пятизначным числом и оканчивающегося на 43.
Гарантируется, что такой элемент в последовательности есть.
В ответе запишите количество найденных троек, затем минимальную из сумм квадратов элементов таких троек. В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности»
Выделим ключевые моменты из формулировки задания:
- Работать будем с тройками элементов
- Числа могут быть отрицательными (от -100 000 до 100 000)
- Элемент должен быть пятизначным и оканчиваться на 43 (вынесем в функцию)
- Сравнивать будем с максимальным элементом всей последовательности, удовлетворяющим условию
- В ответе нам нужна будет минимальная сумма квадратов элементов
Составим функцию для проверки, что число является пятизначным и оканчивается на 43. Определить количество цифр в числе можно несколькими способами:
- Перевести число в строку и применить функцию
len() - Использовать двойное неравенство.
Первый способ максимально наглядный, но выполняется немного дольше, чем сравнения из-за изменения типа данных и использования функции len(). В нашем случае проверить, что число num пятизначное можно так:
len(str(abs(num))) == 5
Мы же будем использовать двойное неравенство и радоваться ускорению программы. Пятизначным является число, большее 9 999 и меньшее 100 000, если использовать знаки строгого неравенства (9999 < x < 100000).
Но для большей наглядности можно заменить первый знак «меньше» на «меньше или равно» и записать неравенство так: 10000 <= x < 100000. Так и слева, и справа будут значения, отличающиеся лишь одним порядком.
Аналогично, для определения, что число оканчивается на какое-то значение, можно пойти двумя путями:
- Если работаем со строкой, то через срез сравниваем последние два элемента с нужным числом
- Если работаем с числом, то проверяем остаток от деления на 10 (или 100, если число должно оканчиваться на двузначное)
И снова мы выбираем второй путь, поскольку мы сохраняем из файла сразу целые числа, а не строки.
В таком случае функцию можно написать следующим образом:
def cons(num):
# Пятизначное
cond_1 = 10_000 <= abs(num) < 100_000
# Оканчивается на 43
cond_2 = abs(num) % 100 == 43
return cond_1 and cond_2
Здесь название cons — сокращение от conditions (условия). Также оба условия можно было записать в одну строку, но для наглядности мы их разделяем на две.
Далее в нашем решении идёт считывание данных из файла:
with open('1701.txt') as f:
data = list(map(int, f))
Теперь найдём максимальный элемент в data, который будет удовлетворять условиям из функции cons() и создадим список для ответа:
max_el = max(num for num in data if cons(num))
answer = []
В цикле перебираем тройки элементов из data, сразу вычисляем сумму квадратов и в блоке if проверяем, что хотя бы один элемент удовлетворяет условия в cons() и только что посчитанная сумма квадратов меньше или равна квадрату max_el.
for x, y, z in zip(data, data[1:], data[2:]):
sum_sq = x ** 2 + y ** 2 + z ** 2
if (cons(x) or cons(y) or cons(z)) \
and sum_sq <= max_el ** 2:
answer.append(sum_sq)
Собираем весь код вместе:
def cons(num):
# Пятизначное
cond_1 = 10_000 <= abs(num) < 100_000
# Оканчивается на 43
cond_2 = abs(num) % 100 == 43
return cond_1 and cond_2
with open('1701.txt') as f:
data = list(map(int, f))
max_el = max(num for num in data if cons(num))
answer = []
for x, y, z in zip(data, data[1:], data[2:]):
sum_sq = x ** 2 + y ** 2 + z ** 2
if (cons(x) or cons(y) or cons(z)) \
and sum_sq <= max_el ** 2:
answer.append(sum_sq)
print(len(answer), min(answer))
И получаем ответ: 92 838850571
Пример 3
Задание 1702
«В файле содержится последовательность целых чисел. Её элементы по модулю не превышают 100000 включительно. Определите количество троек элементов последовательности, в которых хотя бы один элемент оканчивается на 3 и является трёхзначным числом, а сумма всех элементов меньше максимального элемента последовательности, оканчивающегося на 3 и являющегося трёхзначным числом. В ответе запишите количество найденных троек, затем максимальную из сумм элементов таких троек.
В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности»
Выделим ключевые моменты из формулировки задания:
- Работать будем с тройками элементов
- Числа могут быть отрицательными (от -100 000 до 100 000)
- Элемент должен быть трёхзначным и оканчиваться на 3 (вынесем в функцию)
- Сравнивать будем с максимальным элементом всей последовательности, удовлетворяющим условию
- В ответе нам нужна будет минимальная сумма элементов
Можно сказать, что это «облегчённая» версия прошлого задания. Решается оно аналогично, а все отличия будут только в функции cons() и в цикле for: теперь сравниваем не квадрат суммы с квадратом максимального числа, а сумму элементов с максимальным числом.
Подробно останавливаться на разборе кода здесь не будем. Все решение будет таким:
def cons(num):
# Трёхзначное
cond_1 = 100 <= abs(num) < 1_000
# Оканчивается на 3
cond_2 = abs(num) % 10 == 3
return cond_1 and cond_2
with open('1702.txt') as f:
data = list(map(int, f))
max_el = max(num for num in data if cons(num))
answer = []
for x, y, z in zip(data, data[1:], data[2:]):
if (cons(x) or cons(y) or cons(z)) \
and x + y + z < max_el:
answer.append(x + y + z)
print(len(answer), max(answer))
На выходе получаем ответ: 147 944
Но можем привести еще такое альтернативное решение:
def cons(num):
# Трёхзначное и оканчивается на 3
return (100 <= abs(num) < 1_000
and abs(num) % 10 == 3)
with (open('1702.txt') as f):
data = list(map(int, f))
# Находим максимальное число по модулю,
# удовлетворяющее условию cons()
max_el = max(abs(num) for num in data if cons(num))
# Фильтруем числа, удовлетворяющие условию
valid_numbers = {num for num in data if cons(num)}
answer = []
for x, y, z in zip(data, data[1:], data[2:]):
# Проверяем, что хотя бы одно из чисел x, y, z
# удовлетворяет условию
if (x in valid_numbers
or y in valid_numbers
or z in valid_numbers):
# Проверяем условие x + y + z < max_el
sum_xyz = x + y + z
if sum_xyz < max_el:
answer.append(sum_xyz)
print(len(answer), max(answer))
Здесь вместо вызова функции cons() на каждой итерации цикла мы просто проверяем принадлежность хотя бы одного числа из тройки множеству valid_numbers. Это позволяет увеличить скорость работы нашей программы. Подробнее о таком подходе мы рассказывали в разборе 15 задания ЕГЭ по информатике.
Пример 4
Задание 1703
«В файле содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от -100 000 до 100 000 включительно. Определите количество троек элементов последовательности, в которых хотя бы один из трёх элементов оканчивается на 3, а сумма элементов тройки не больше максимального элемента последовательности, являющегося пятизначным числом, которое оканчивается на 3. В ответе запишите количество найденных троек чисел, затем максимальную из сумм элементов таких троек. В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности»
Ключевые моменты здесь следующие:
- Работать будем с тройками элементов
- Числа могут быть отрицательными (от -100 000 до 100 000)
- Элемент должен оканчиваться на 3 (вынесем в функцию)
- Сравнивать будем с максимальным элементом всей последовательности, который является пятизначным и оканчивается на 3 (вынесем в функцию)
- В ответе нам нужна будет максимальная сумма элементов
В этом задании у нас разные условия для элементов, которые проверяются в цикле и для максимального элемента. Следовательно, для нашего же удобства, напишем две функции: одну для проверки, что хотя бы один из элементов нам подходит (то есть оканчивается на 3), а вторую для определения, что элемент пятизначный и оканчивается на 3.
Первая функция выглядит так:
def is_val(num):
return abs(num) % 10 == 3
На самом деле, можно было это выражение не выносить в отдельную функцию, а записать сразу в условии. Но тогда бы блок if выглядел бы чересчур большим и трудночитаемым.
Вторую функцию определим так:
def cons(num):
# Пятизначное
cond_1 = 10_000 <= abs(num) < 100_000
# Оканчивается на 3
cond_2 = abs(num) % 10 == 3
return cond_1 and cond_2
Найдём максимальный элемент последовательности, удовлетворяющий условию из функции cons():
max_el = max(num for num in data if cons(num))
А цикл for у нас будет выглядеть следующим образом:
for x, y, z in zip(data, data[1:], data[2:]):
if (is_val(x) or is_val(y) or is_val(z)) \
and x + y + z <= max_el:
answer.append(x + y + z)
Весь код для решения этого задания будет таким:
def is_val(num):
return abs(num) % 10 == 3
def cons(num):
# Пятизначное
cond_1 = 10_000 <= abs(num) < 100_000
# Оканчивается на 3
cond_2 = abs(num) % 10 == 3
return cond_1 and cond_2
with open('1703.txt') as f:
data = list(map(int, f))
max_el = max(num for num in data if cons(num))
answer = []
for x, y, z in zip(data, data[1:], data[2:]):
if (is_val(x) or is_val(y) or is_val(z)) \
and x + y + z <= max_el:
answer.append(x + y + z)
print(len(answer), max(answer))
По итогу его работы получаем ответ: 1767 99081