Алгоритм решения задания 9 ЕГЭ по информатике (Python)

📌 Больше полезных статей по информатике и программированию вы можете найти у нас на сайте.

📢 Следить за новостями мира информатики, а также общаться, делиться впечатлениями и готовиться к экзаменам лучше вместе, в нашем Telegram-канале.

О задании

Подробно формулировки и основные моменты данного задания мы разбирали в прошлой статье, где показывалось решение задания 9 с помощью редактора электронных таблиц Microsoft Excel.

Хоть данное задание и нацелено на работу с электронными таблицами, мы все же разберем вариант его решения с помощью программы на языке Python. При должной сноровке такой метод позволит быстрее и надежнее решить задание 9 ЕГЭ по информатике.

К тому же, сдавая ЕГЭ по информатике, вы рассчитываете на поступление в технический вуз, где важным аспектом обучения является именно создание собственных программ, а не использование офисных приложений.

Далее давайте вкратце вспомним отличия в формулировках этого задания и разберем основные подходы к его решению.

Открытие файла

Как вам уже известно, приложенные файлы к заданию 9 имеют расширение xls (xlsx). По умолчанию, Python не умеет открывать файлы с таким расширением. Следовательно, необходимо сохранить все данные в файл с другим расширением, например, txt.

Это можно сделать несколькими способами. Самый банальный заключается в том, чтобы просто скопировать все числа из открытого в Excel файла и вставить в блокнот, после чего сохранить в формате txt.

Второй способ заключается в следующем:

1. В самом Excel переходим во вкладку «Файл»
2. Выбираем пункт «Сохранить как»
3. Выбираем нужную директорию (это должна быть папка, в которой находится ваш python-файл с решением)
4. Вводим названием (обычно используют названием «input.txt»
5. В пункте «Тип файла» выбираем «Текстовые файлы (с разделителем табуляции)»
6. Сохраняем

Теперь можно прочитать данный файл в вашей программе на Python. Помните, что на реальных проектах читать файлы следует с помощью менеджера контекста with…as…. Здесь же мы работаем только с одним файлом и самостоятельно завершаем работу программы после получения ответа.

Так что можно воспользоваться более простой конструкцией:

file = open('input.txt')

Построчно считывать данные из файла можно в цикле for:

for line in file:

Или же можно создать список со всеми строками следующим образом:

arr = [list(map(int, i.split())) for i in file]

В переменной arr здесь находится список, содержащий списки чисел каждой строки файла.

Например, если в файле первые 3 строки такие:

1 2 3 4 5 6 7 8 9 1 2 3

То в переменной arr будет следующее:

[[1, 2, 3, 4], [5, 6, 7, 8], [9, 1, 2, 3]]

Обратиться к первой строке [1, 2, 3, 4] можно с помощью индекса 0: arr[0]. Обратиться к первому элементу первой строки [1] можно так: arr[0][0].

Полный код для открытия файла, считывания данных и вывода рассмотренных выше значений на экран представлен ниже (вывод на экран обозначен знаками «>>>»):

Количество условий

Вспомним вывод, который мы сделали исходя из различного количества условий, требуемых к выполнению:

1. Если требуется выполнение обоих условий — используем конъюнкцию (логическую функцию И)
2. Если требуется выполнение хотя бы одного условия — используем дизъюнкцию (логическую функцию ИЛИ)
3. Если требуется выполнение только одного условия — используем логическую функцию исключающее ИЛИ.

В Excel мы пользовались встроенными функциями И(), ИЛИ() и ИСКЛИЛИ(). Но в Python есть свои операторы, реализующий тот же функционал: логические операторы and(), or() и знак ^, соответственно.

Обычно используется подобный синтаксис, когда нам необходимо посчитать количество строк, удовлетворяющих условиям:

При этом сами выражения для проверки заданного условия можно как писать внутри условной конструкции, так и выносить в отдельную функцию.

Ниже представлены примеры функций к различным формулировкам условий.

1. Подсчёт количества повторяющихся чисел

В cnt здесь содержится список, в котором для соответствующего элемента исходного списка записано количество его повторений.

Например, для строки 46 46 9 6 в cnt будет содержаться следующий список: [2,2,1,1]. Точно такое же действие мы делали и в Excel (синие столбцы).

Далее, необходимо сделать так, чтобы данная функция возвращала True для подходящих строк и False для неподходящих. Можем использовать практически те же алгоритмы, что и при решении через Excel.

Например, такая функция будет возвращать True, если в строке одно число повторяется дважды, а все остальные числа различны:

Для файла с числами:

1 1 3 2 4

5 4 3 3 2

1 2 4 5 6

Программа выдаст следующее: True, True, False.

На остальных формулировках мы уже не будем так подробно останавливаться, суть работы с функциями будет аналогичная.

2. Поиск всех повторяющихся/неповторяющихся чисел

В переменной not_repeat содержится список уникальных чисел или пустой список, если в строке только одно число, повторяющееся несколько раз.

В переменной repeat содержатся числа (число), которые встречаются в строке более одного раза. Если таких чисел нет, то в переменной находится пустое множество.

Также данная запись может быть полезна, если необходимо вернуть экземпляр единственного повторяющегося числа

3. Проверка, можно ли разбить 4 числа на две пары с разными суммами

4. Проверка, что все числа в строке различны

Значение для ответа

Ранее мы уже рассматривали варианты задания 9, в которых вас могут потребовать дать в ответ не только количество подходящих строк, но номер наименьшей/наибольшей строки или сумму элементов подходящей строки.

Тогда решения строились на использовании встроенных в Excel инструментов фильтрации и функции СУММ(). Теперь же приведем решения для заданий с подобными формулировками с помощью кода на Python.

Код, для подсчёта количества подходящих строк может быть следующим:

Здесь в переменной count содержится число строк, удовлетворяющих условиям. Сами условия у нас описаны в функциях f1() и f2(). Подсчет строк ведется в цикле for: мы считываем каждый элемент списка arr, то есть каждую строку исходного файла.

Далее в условной конструкции проверяем, что выполняются оба условия из f1() и f2(), если это так, то увеличиваем значение переменной count на 1.

Для поиска наименьшего или наибольшего номера подходящей строки будем использовать функцию enumerate() (но вы также можете использовать отдельную переменную-счётчик).

Функция enumerate() в Python используется для добавления счетчика к итерируемым объектам (например, спискам, кортежам, строкам) и возвращения их в виде объекта-итератора. Этот итератор генерирует пары, состоящие из индекса и значения соответствующего элемента итерируемого объекта.

То есть таким образом мы одновременно получаем все числа строки в виде списка и номер этой строки в виде числа.

Функция enumerate() имеет следующий синтаксис:

enumerate(iterable, start=0)

• iterable: итерируемый объект, по которому нужно пройтись
• start: начальное значение счетчика (по умолчанию 0)

Поскольку нумерация строк должна начинаться со значения 1, то всегда вторым аргументом данной функции необходимо будет писать start=1.

Для поиска наименьшего номера строки, удовлетворяющей условиям, нам достаточно остановить цикл после первой найденной строки и в ответ вывести значение индекса этой строки, полученное от enumerate():

Поиск наибольшего номера подходящей строки немного сложнее. Дело в том, что нам нужно «перевернуть» наши строки и их индексы, так, чтобы цикл начинался с последней строки. Тогда мы можем использовать все то же условие и остановить цикл, как только нам попадётся нужная строка.

Просто так «перевернуть» значения в объекте-итераторе, возвращаемом функцией enumerate(), не получится. Необходимо сначала создать из него список с помощью функции list(), а затем использовать стандартный срез [::-1] для инвертирования списка.

Тогда код для поиска наибольшего номера подходящей строки будет следующий:

В ряде заданий может потребоваться найти сумму всех чисел в строке таблицы с наибольшим или наименьшим номером, для которой выполняются условия. В таком случае мы также находим нужную и складываем все значения в этой строке с помощью функции sum():

Алгоритм решения

Пример 1

Формулировка задания следующая:

«Откройте файл электронной таблицы, содержащей в каждой строке четыре натуральных числа. Определите количество строк таблицы, в которых сумма наибольшего и наименьшего чисел меньше суммы двух оставшихся»

Скачиваем приложенный к заданию файл и сохраняем его в расширении txt, под названием import.txt.

Далее открываем его в нашей программе, считываем все данные и сохраняем в переменной arr.

Теперь займемся написанием кода функции, которая будет реализовывать условие «сумма наибольшего и наименьшего чисел меньше суммы двух оставшихся». Здесь можно пойти несколькими путями.

Во-первых, отсортировать исходный список, вычислить сумму первого и последнего, то есть сумму наименьшего и наибольшего чисел. Далее сравнить с суммой оставшихся двух: второго и третьего элементов списка. Такой подход с сортировкой и сложением по индексам мы использовали в первом примере прошлой статьи по Excel.

Сейчас же мы воспользуемся другим способом. Для поиска максимального и минимального будем использовать функции min() и max(). Следовательно, для вычисления суммы двух оставшихся от суммы всех чисел отнимем наименьшее и наибольшее число.

Код функции для условия будет такой:

Теперь нам осталось лишь перебрать все элементы списка arr (строки таблицы) в цикле for, увеличивая значение переменной-счётчика, когда строка удовлетворяет условию.

Оставшийся код программы выглядит так:

Полный код программы будет следующий:

В результате на экран выводится ответ — 9997.

Пример 2

Формулировка задания следующая:

«Откройте файл электронной таблицы, содержащей в каждой строке шесть натуральных чисел. Определите количество строк таблицы, содержащих числа, для которых выполнены оба условия:
– в строке только одно число повторяется трижды, остальные числа различны; 
– квадрат суммы всех повторяющихся чисел строки больше квадрата суммы всех её неповторяющихся чисел. 
В ответе запишите только число»

Код для открытия файла и считывания данных здесь будет такой же, что и в прошлом примере. Отличия начинаются в функциях для реализации условий.

Начнем с первого условия, здесь нужно проверить, что в списке одно число повторяется трижды, а три других числа представлены только в одном экземпляре. Для этого будем подсчитывать, сколько раз входит каждый элемент в список с помощью метода count().

Нам необходимо потребовать того, чтобы количество элементов, которые встречаются 3 раза было равно трём. Столько же должно быть и тех чисел, которые встречаются ровно 1 раз.

Код такой функции представлен ниже:

Далее напишем вторую функцию. Здесь мы ищем повторяющиеся и неповторяющиеся элементы. Для вычисления количества вхождений будем использовать уже использованную в первой функции конструкцию.

Для неповторяющихся значений, метод count() должен возвращать число 1. Для повторяющихся значений — любое число, не равное 1.

Код второй функции будет такой:

Идущий далее код практически идентичен рассмотренному в первом примере. Единственным отличием будет наличие в условии двух функций и оператора and между ними. В результате получаем ответ на это задание — число 19.

Полный код решения этого задания представлен ниже.

Пример 3

Формулировка задания следующая:

«Откройте файл электронной таблицы, содержащей в каждой строке семь натуральных чисел. Определите наибольший номер строки таблицы, для чисел которой выполнены оба условия:
    – в строке есть ровно два числа, каждое из которых повторяется трижды, и одно число без повторений;
    – среднее арифметическое повторяющихся чисел строки меньше неповторяющегося числа.
В ответе запишите только число»

С открытием файла и чтением данных из него здесь все аналогично предыдущим примерам.

Отличия начнутся в функциях, и то, первые две строки кода, где мы определяем количество повторений чисел в списке будут такие же, как и в прошлом примере.

В первой функции мы находим список чисел, которые повторяются трижды и список из одного числа, которое встречается только 1 раз в строке исходного файла.

Далее определяем, что у нас именно два числа, которые повторяются по 3 раза. То есть длина списка с такими числами должна быть равной 6. Следовательно, составим такую функцию:

Переходим к функции для второго условия. Как и в прошлом примере ищем все повторяющиеся и неповторяющиеся числа. Находим среднее арифметическое повторяющихся и проверяем, меньше ли оно чем первый элемент списка неповторяющихся чисел.

Нам здесь не важно, какой элемент брать, ведь в подходящих строках в переменной nrep будет только один элемент.

Как только готовы все функции, можем перейти к последней части нашей программы. Для поиска наибольшего номера строки, удовлетворяющей обоим условиям, будем использовать рассмотренную в самом начале конструкцию с функцией enumerate():

Итогом работы нашей программы станет ответ на 9 задание: 17975. Полный код данной программы представлен ниже.