Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
А это подборки моих материалов на канале
Пример ЕГЭ-задачи по программированию
Публиковать время от времени задачи из ЕГЭ порекомендовали мне в комментариях. И я подумал, что это хорошая идея. Вот такая задача сегодня будет опубликована. Конечно, решение задачи опубликовано в Инете. Но объяснять чужое решение, увольте, это не для меня. Все решения будут на языке Python.
И так задача. Перескажу условие своими словами. Дан текстовый файл. В каждой строке записано целое число. Известно что числа попадают некоторый промежуток, скажем от -k до +k. Например, от -10000 до 10000, как это указано в условии. Необходимо посчитать количество соседних пар, в которых оба числа делятся на 7. А также найти минимальную сумму в такой паре. Например для файла
7
14
21
-7
4
Получим
3 14
Задача, я вам скажу, не сложная, но требует уже наличие алгоритмического мышления.
Я приведу три решения задачи. Первое решение, на мой взгляд, являет собой то, как в принципе нужно подходить к задаче, разбивая её на фрагменты, которые по минимуму взаимодействуют с другими. Если вы решили задачу и программа работает корректно, то тогда можно приступать к её оптимизации. Ну а если вы на экзамене, то может и не стоит тратить на оптимизацию время.
Рассматривая решение (см. выше) обращу внимание, что в цикле, в котором перебираются числа файла, пары появятся, начиная с элемента с номером 1 (0 и 1), поэтому я использую переменную p (флаг), которая просто показывает, что взят только ещё первый элемент (p==0) или уже последующие (p!=0). Вот этот кусочек программы, когда взят только начальный элемент последовательности, мы и отделяем с помощью continue. Ну а далее работает следующая часть тела цикла, где подсчитываются пары соседних чисел, делящихся на 7 и проверяется их сумма. Т.е. в конце у нас сразу будет и количество нужных пар и минимальная сумма в таких парах.
Отмечу один важный момент. Задача решено согласно условия, т.е. числа находятся в промежутке [-10000, +10000]. По этой причине начальное значение переменной m = 20001, т.е. максимально возможное значение. Ситуация может измениться, если мы не будем знать какие числа хранятся в файле. В этом случае алгоритм практически не измениться, но нужно будет при вычислении первой суммы, присвоить её переменной m. Как вы будете определять, что сумма первая? Ну, например, введёте еще одну переменную типа p (флага) для индикации того, что вычислена первая сумма.
Следующая программа реализует тот же алгоритм, но несколько оптимизирована по объёму кода. Она представлена ниже.
Ну, а это решение, так сказать, с питоновскими изысками. Ну это для гурманов.
В этом решении, кроме питоновского "выпендрёжа" есть один важный изъян. Всё содержимое файла считывается в память. Кроме того используется дополнительный список. Т.е. расход памяти ещё удваивается. С помощью zip() мы получаем список пар соседних чисел. Потом отфильтровываем только пары, числа в которых делятся на 7, потом из этого списка получаем список сумм. Ну а дальше результат. Ну и объясните зачем мне fl1.pop() и fl2.pop(0). Ну это так, поиграться.
Замечание
О функциях filter(), map() можно посмотреть здесь.
Напишите в комментариях, если что. А может кому-то приёдет более красивое решение. Присылайте.
Хорошего программирования. Оставляйте свои комментарии, не забывайте про лайки и подписывайтесь на мой канал programmer's notes.