О задании
Задание 25 ЕГЭ по информатике нацелено на обработку числовой информации. Для успешного решения этого задания вам не обойтись без написания программы, поскольку объёмы данных и сложность вычислений делают ручной подход крайне неэффективным.
В этом задании можно выделить три основных типа задач, которые отличаются друг от друга подходом к решению и уровнем сложности.
Первый тип — работа с масками чисел. Это наиболее простые задачи, где требуется найти все числа, соответствующие заданной маске и превышающие некоторое пороговое значение. Для решения таких задач мы будем использовать встроенный модуль Python под названием fnmatch, который позволяет сопоставлять строки с шаблонами буквально в одну строку кода.
Второй тип уже посложнее и направлен на работу с делителями чисел. Здесь нам предстоит искать все делители заданного числа и определять их характеристики. Например, проверять, оканчивается ли делитель на определённую цифру или число, подсчитывать количество делителей с заданными свойствами или находить среди них наибольший и наименьший.
Третий тип ещё сложнее. Помимо поиска делителей здесь требуется определять, какие из них являются простыми числами. Такие задачи объединяют в себе навыки работы с делителями и знание эффективных и быстрых алгоритмов проверки простоты числа.
В этой же статье мы начнём с простого — разберём работу модуля fnmatch в Python, узнаем, как работают подстановочные знаки и научимся решать 25 задания первого типа.
Модуль fnmatch
Представьте, что вам нужно найти на компьютере все изображения вашего любимого питомца, все текстовые документы, которые вы готовили для написания большой проектной работы, или все новые папки, которые вы создавали, когда было лень придумывать нормальное название для каталога.
Просто так перебирать во встроенном поиске все эти файлы и папки будет слишком долго. Куда эффективнее решить эту проблему можно с использованием навыков программирования на Python и встроенного модуля fnmatch.
Модуль fnmatch был создан для решения одной из самых распространённых задач в программировании — сопоставления имён файлов с шаблонами. Его название как раз и произошло от словосочетания «filename matching», что переводится как «сопоставление имён файлов».
Однако несмотря на своё «файловое» происхождение, этот модуль прекрасно работает с любыми строками, что делает его идеальным инструментом для задач ЕГЭ с масками чисел.
Вся прелесть этого модуля заключается в том, что он использует синтаксис, близкий к регулярным выражениям, но при этом гораздо более простой. Это позволяет без труда пользоваться специальными символами — подстановочными знаками, которые служат для замены одного или нескольких неопределённых символов в шаблоне. И при этом не требуются знания синтаксиса регулярных выражений. Хотя мы все равно настоятельно рекомендуем его выучить как минимум для успешного решения 24 заданий ЕГЭ!
Синтаксис подстановочных знаков идентичен аналогичным символам, используемым в оболочке Unix (это различные Linux-дистрибутивы: Ubuntu, Kali, Астра, Альт и прочее). Из этого вытекают сразу два преимущества. Во-первых, многие программисты уже знакомы с этим синтаксисом. Во-вторых, подстановочные знаки интуитивно понятны и легко запоминаются, в отличие от обилия метасимволов из регулярных выражений.
Подстановочные знаки
В модуле fnmatch представлено четыре вида подстановочных знаков. Они напрямую соответствуют тем, что используются в Unix-системах при работе с файлами через командную строку. Давайте разберём каждый из них.
Начнём со знака звёздочки «*». Он соответствует любой последовательности любых символов, в том числе и пустой строке. Это самый «жадный» из подстановочных знаков — он захватывает всё, что только может.
Так, под шаблон «a*b» будут подходить все строки, начинающиеся на букву «a» и оканчивающиеся буквой «b». Сюда попадут и короткая строка «a1b», и более длинная «axxxb», и даже «ax*xasd%123&asdcxvdf#b» со специальными символами внутри. И строка «ab» тоже подойдёт, потому что звёздочка может соответствовать и пустой последовательности символов.
Следующий знак — это вопросительный знак «?». Он соответствует ровно одному любому символу. В этом его принципиальное отличие от звёздочки: если на месте «*» может не быть ничего, то на месте «?» всегда должен присутствовать ровно один символ.
Шаблону «a?b» будут подходить только строки, состоящие из трёх символов, где первый — это «a», а последний — «b». Подойдут «a1b» и «axb», но не подойдут «ab» (слишком короткая) и «a12b» (слишком длинная).
Как и в регулярных выражениях, в подстановочных знаках можно перечислять набор допустимых символов. Для этого используются квадратные скобки «[…]». Внутрь скобок можно передавать символы по одному, например «[12345]», или сразу диапазоном от первого до последнего символа включительно, например «[1-5]».
Шаблону «a[1-5]» будут удовлетворять только пять строк: «a1», «a2», «a3», «a4» и «a5». Никакие другие варианты не пройдут проверку.
С помощью квадратных скобок также можно экранировать (т.е. делать так, чтобы они переставали работать как спецсимволы) подстановочные знаки «*» и «?», если вам нужно найти их буквально. Например, шаблону «a[*?]» будут удовлетворять строки «a*» и «a?», но не «a**» или «a1».
Ещё в квадратных скобках можно перечислить символы, которые не должны находиться на данной позиции. Для этого перед такими символами следует поставить восклицательный знак «!».
Допустим, нам нужно получить все двухсимвольные комбинации с буквой «a», после которой идёт любая чётная цифра. Для этого можно составить шаблон «a[!13579]». Тогда этому шаблону будут соответствовать строки «a2», «a4», «a6», «a8», «a0» и даже «aX» (ведь буква X — это не нечётная цифра), но не «a1» или «a5».
Функции fnmatch
Теперь перейдём к рассмотрению функций, которые становятся доступны при подключении модуля fnmatch. Разберём только две основные функции: fnmatch() и filter().
Начнём с самой базовой и наиболее часто используемой функции — fnmatch(). Она принимает два аргумента: проверяемую строку и шаблон. Возвращает эта функция логическое значение в зависимости от того, соответствует ли переданная строка шаблону или нет.
По своей работе эта функция напоминает fullmatch() из модуля re для регулярных выражений. То есть она проверяет, соответствует ли вся строка целиком заданному шаблону, а не только её часть.
Давайте проверим работу функции на уже разобранном примере с подстановочным знаком «?»:
Мы поместили вызов функции fnmatch() в условие блока if. Если функция возвращает истину, что означает соответствие строки word шаблону pat, на экран выводится подтверждающее сообщение. В противном случае мы видим сообщение о несоответствии.
Приведём ещё несколько примеров использования fnmatch() с различными подстановочными знаками:
Вторая полезная функция — это filter(). Она позволяет обработать целый список строк и вернуть из него новый список, содержащий только те строки, которые подходят под заданный шаблон. Эта функция избавляет вас от необходимости писать циклы и проверки для фильтрации списков, делая код более чистым и читаемым.
Представим, что у нас есть список с названиями файлов. Давайте найдём среди них только изображения с расширением .png:
Всего одна строка кода — и мы получили отфильтрованный список. Легко и просто! Именно за такую простоту в использовании и полюбили данный модуль. А далее мы научимся применять рассмотренную выше функцию fnmatch на реальных заданиях ЕГЭ по информатике.
Алгоритм решения
Вся суть подхода с использованием fnmatch для решения 25 заданий первого типа заключается в следующем:
- Нам дана какая-то маска и диапазон чисел;
- Мы перебираем все числа из этого диапазона;
- Проверяем, подходит ли текущее число под маску через fnmatch;
- Если подходит, то выводим на экран это число и результат его деления на заданное в условии число.
Вот и всё. Единственное, что тут можно добавить — оптимизировать перебор чисел, но до этого мы дойдём немного позднее.
Перейдём сразу к заданию:
«Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Среди натуральных чисел, не превышающих 10^10, найдите все числа, соответствующие маске 3?12?14*5, делящиеся на 1917 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 1917.»
Сначала в задании расписывается базовая информация о том, что такое маска и какие символы мы можем встретить. Далее даётся диапазон, в данном случае — это число до 10 в десятой степени.
Затем идёт условие, по которому будем определять подходящие числа:
- Число должно советовать маске «3?12?14*5»;
- И оно должно делиться на 1917.
Вывести на экран требуется все подходящие числа, а рядом с ними — результаты деления на 1917.
Можно уже приступать к решению, но давайте подумаем, какой диапазон чисел нужно использовать? Начнём с левой границы. Будем перебирать с единицы? Но 1 не подходит под маску и уж тем более не делится на 1917 без остатка. Число 2 тоже, как и 3, и 4.
Очевидно, что нет смысла перебирать все числа начиная с 1. А с какого числа начать тогда?
Давайте подумаем, какое будет первое число, подходящее под маску из условия? Для этого вспомним, что означают подстановочные знаки. Поскольку «?» означает ровно один символ, то вместо знаков вопроса мы обязаны поставить какую-то цифру. А, так как ищем минимальное подходящее число, то вместо «?» поставим ноль.
Звёздочка же может означать пустую последовательность. Раз может, то пусть и означает — просто удалим её из записи. Получаем такое число: 30120145.
Убедимся, что оно подходит под маску:
Отлично. В базовом варианте можем стартовать от этого числа и идти до 10 в десятой степени с шагом 1. И где-то к концу экзамена мы, возможно, дойдём до ответа. Как-то не очень эффективно, согласитесь?
Давайте дальше оптимизировать. Нам, опять же, нет смысла проверять каждое число. Ведь чётко сказано: подходящие числа должны быть кратны 1917. Следовательно, и шаг должен быть равен 1917.
А вот теперь и новая загвоздка. Никто не гарантировал нам, что наименьшее число, соответствующее маске, будет кратно 1917. Значит, мы не можем идти от него «вверх» с шагом 1917. Как быть?
Что же, число 30120145 — это ведь наша нижняя граница. Меньше уже быть не может, потому что первая цифра обязана быть 3, дальше структура жёстко задана, а в конце обязательно 5. Теперь нам нужно первое число, которое делится на 1917 и при этом не меньше 30120145.
Вот тут начинается самое интересное.
Если 30120145 делится на 1917, отлично, стартуем с него. Если нет, то нам нужно добавить столько, чтобы попасть в следующее кратное. А сколько?
Разберёмся на примере попроще. Пусть у нас минимальное число — это 22. А нам нужны только числа, кратные 5. Как получить первое число, не меньшее 22 и кратное 5?
Можно записать такое уравнение: x = 22 + (5 – 22 % 5), где x — искомое число, а 22 % 5 — остаток от деления числа 22 на 5 (2).
Тогда получим x, равный 25, что и требовалось. В Python можно записать такую универсальную формулу:
Где:
- first — первое подходящее под оба условия число;
- start — минимальное число, подходящее под маску (у нас 30120145);
- rem — наше число 1917, которому должны быть кратны подходящие под условие числа.
Но снова можем наткнуться на ошибку. А что, если это минимальное число start уже и так делится на 1917? Тогда запись start % 1917 будет равна нулю, следовательно в переменной first будет начальное значение start, увеличенное на 1917.
Что не очень-то и хорошо. Ведь тогда мы пропустим это первое число, которое и кратно 1917, и подходит под маску. В таком случае можно добавить еще одну операцию взятия остатка от деления:
Выглядит довольно громоздко? Но не переживайте, в Python можно записать это выражение иначе:
Она работает по тому же принципу и автоматически даёт 0, если число start уже кратно rem.
Резюмируя, можно сказать, что мы хотим прибавить ровно столько, чтобы добраться до следующего кратного, но, если мы уже на кратном, прибавлять ничего не нужно — именно это и происходит в такой записи.
Теперь соберём все вместе в одну программу. Импортируем функцию fnmatch:
Перебираем числа от 30120145 + (-30120145 % 1917) до 10 в десятой степени с шагом в 1917:
Проверяем, что число подходит под маску (кратно 1917 оно и так будет):
И выводим на экран сначала найденное число i, затем результаты его деления на 1917:
Запускаем программу и получаем 5 пар чисел, которые запишем в ответ:
351261495 183235
3212614035 1675855
3412614645 1780185
3712414275 1936575
3912414885 2040905
Пример 1
Разберём еще одно задание для закрепления:
«Среди натуральных чисел, не превышающих 10^9, найдите все числа, соответствующие маске 33*21?7, делящиеся на 2079 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 2079.»
Сразу выпишем для себя минимальное число, удовлетворяющее маске: 332107. И приступим к решению. Начинаем с импорта:
Цикл:
Условие:
И вывод на экран пар чисел:
Запускаем программу и получаем 6 пар чисел:
336222117 161723
337012137 162103
337802157 162483
338592177 162863
339382197 163243
Их и запишем в ответ.
Пример 2
Для закрепления бегло рассмотрим еще одно задание:
«Среди натуральных чисел, не превышающих 10^10, найдите все числа, соответствующие маске 4*4736*1, которые делятся на 7993 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им результаты деления этих чисел на 7993.»
Здесь минимальным числом, удовлетворяющим маске, будет 44736, то есть просто удаляем все звёзды.
А далее все по шаблону:
Здесь получим сразу 7 пар чисел:
44736821 5597
4064736241 508537
4303247361 538377
4347368721 543897
4447361151 556407
4473658121 559697
4794736931 599867
Они и будут ответом на данное задание.
Итоги
Давайте выведем шаблонный код для решения первого типа 25 заданий:
Здесь:
*1 — минимальное число, подходящее под маску. Из маски условия удаляем все звёздочки, а вместо знаков вопроса пишем 0. Например: 12*3?4 = 12304;
*2 — число, на которое должны делиться без остатка подходящие числа;
*3 — верхняя граница диапазона чисел, обычно — 10 в десятой степени;
*4 — маска из условия.
На этом мы закончим с разбором алгоритма решения первого типа 25 заданий. В следующей же статье рассмотрим эффективный алгоритм поиска делителей числа и научимся решать задания второго типа.