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

Навигация по странице

О задании

Задание 25 ЕГЭ по информатике нацелено на обработку числовой информации. Для успешного решения этого задания вам не обойтись без написания программы.

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

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

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

Модуль fnmatch

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

Просто так перебирать во встроенном поиске все эти файлы и каталоги будет слишком долго. Куда эффективнее решить эту проблему можно с использованием навыков программирования на Python и встроенного модуля fnmatch.

Модуль fnmatch был создан для решения одной из самых распространенных задач в программировании — сопоставления имен файлов с шаблонами. Его название как раз и произошло от словосочетания «filename matching» (сопоставление имен файлов).

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

К тому же синтаксис подстановочных знаков идентичен аналогичным, используемым в оболочке Unix. Из этого вытекают сразу два преимущества использования fnmatch. Во-первых, многие программисты уже знакомы с синтаксисом подстановочных знаков. Во-вторых, эти подстановочные знаки интуитивно понятны и легко запоминаются, в отличие от обилия метасимволов из регулярных выражений.

Давайте подробнее рассмотрим работу подстановочных знаков.

Подстановочные знаки

В модуле fnmatch представлено 4 вида подстановочных знаков. Они прямо соответствуют тем, что используется в Unix-системах при работе с файлами через командную строку.

Разбор подстановочных знаков начнём со знака «*». Он соответствует любой последовательности любых символов, в том числе и пустой строке.

Так, под шаблон «a*b» будут подходить все строки, начинающиеся на букву «a» и оканчивающиеся буквой «b»: «a1b», «axxxb» и «a1x*x#b».

Следующий знак – это «?». Он соответствует ровно одному любому символу. При этом если на месте «*» может не быть ничего, то на месте «?» всегда должен быть хоть какой-то один символ.

Так, шаблону «a?b» будут подходить строки, состоящие из трёх символов, первый из которых «a», а последний – «b»: «a1b», «axb», но не «ab» или «a12b».

Как и в регулярных выражениях, в подстановочных знаках можно перечислять набор допустимых символов. Для определения такого диапазона используются квадратные скобки «[…]».

В квадратные скобки можно передавать требуемые символы по одному (например, «[12345]») или сразу диапазоном от первого до последнего символа включительно (например, «[1-5]»).

Так, шаблону «a[1-5]» будут удовлетворять только такие строки: «a1», «a2», «a3», «a4», «a5».

С помощью квадратных скобок также можно экранировать рассмотренные ранее подстановочные знаки «*» и «?». Например, такому шаблону «a[*?]» будут удовлетворять строки «a*», «a?», но не «a**» или «a1».

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

Например, нам нужно получить все пары с буквой «а», после которой не идёт никакая нечётная цифра. Для этого можно составить такой шаблон «а[!13579]». Тогда этому шаблону будут соответствовать следующие строки: «a2», «a4» и даже «a*», но не «a1» или «a5».

Теперь можем перейти к рассмотрению функций, доступных при подключении модуля fnmatch.

Функции модуля fnmatch

В модуле fnmatch содержатся 4 функции, каждую из которых мы и разберём далее, а также научимся применять на практике.

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

По своей работе эта функция напоминает fullmatch() из модуля re. То есть она проверяет, соответствует ли вся строка какому-то определённому шаблону.

Для начала проверим её работу на каком-либо уже разобранном примере. Допустим, это будет пример к подстановочному знаку «?»:

from fnmatch import fnmatch

words = ["a1b", "axb", "ab", "a12b"]

pat = 'a?b'

for word in words:
    if fnmatch(word, pat):
        print(f"{word} удовлетворяет шаблону {pat}")
    else:
        print(f"{word} НЕ удовлетворяет шаблону {pat}")

>>>a1b удовлетворяет шаблону a?b
>>>axb удовлетворяет шаблону a?b
>>>ab НЕ удовлетворяет шаблону a?b
>>>a12b НЕ удовлетворяет шаблону a?b

Мы поместили вызов функции fnmatch() в блок if. Таким образом, если функция возвращает истину, что означает соответствие строки word шаблону pat, то на экран выводится сообщение «{word} удовлетворяет шаблону {pat}».

В противном случае, мы видим на экране сообщение, означающее, что переданная строка не удовлетворяет шаблону.

Приведём далее сразу несколько примеров использования fnmatch() с различными подстановочными знаками:

from fnmatch import fnmatch

print(fnmatch("image.png", "*.txt"))
print(fnmatch("img-1.png", "img-?.png"))
print(fnmatch("docs1.zip", "docs[246].zip"))
print(fnmatch("file2.py", "file[!01].py"))

>>>False
>>>True
>>>False
>>>True

Следующей мы рассмотрим функцию fnmatchcase(). На первый взгляд она может показаться идентичной fnmatch(), но есть важное отличие: эта функция учитывает регистр символов.

На Unix системах (это различные дистрибутивы Linux и macOS) сравнение символов регистрозависимое. То есть при поиске название «FILE.TXT» не совпадёт с шаблоном «*.txt».

В Windows же сравнение не зависит от регистра, а название «FILE.TXT» совпадает с шаблоном «*.txt».

Значит, при использовании функции fnmatch() в Windows регистр символов будет игнорироваться:

from fnmatch import fnmatch, fnmatchcase

words = ["FILE.TXT", "file.txt"]
pat = "*.txt"

# fnmatch
for word in words:
    if fnmatch(word, pat):
        print(f"{word} удовлетворяет шаблону {pat}")
    else:
        print(f"{word} НЕ удовлетворяет шаблону {pat}")

>>>FILE.TXT удовлетворяет шаблону *.txt
>>>file.txt удовлетворяет шаблону *.txt

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

from fnmatch import fnmatch, fnmatchcase

words = ["FILE.TXT", "file.txt"]
pat = "*.txt"

# fnmatchcase
for word in words:
    if fnmatchcase(word, pat):
        print(f"{word} удовлетворяет шаблону {pat}")
    else:
        print(f"{word} НЕ удовлетворяет шаблону {pat}")

>>>FILE.TXT НЕ удовлетворяет шаблону *.txt
>>>file.txt удовлетворяет шаблону *.txt

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

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

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

from fnmatch import filter

files = ["text.doc", "image.png", "res.xlsx",
         "photo.png", "notes.txt", "asdsad.zip"]

pat = "*.png"

images = filter(files, pat)
print(images)

>>>['image.png', 'photo.png']

Если вам эта функция не показалась полезной, то давайте разберем такой практичный пример. Допустим, у нас есть папка, в которой содержатся разные файлы: изображения, текстовые файлы в формате «docx» и в формате «txt».

И появилась у нас идея удалить из этой папки все документы в формате «txt». Конечно, здесь можно сделать это и вручную. Но что, если таких файлов будет гораздо больше, да и удалять их необходимо не в одной папке.

Давайте напишем программу на Python, которая займётся удалением фалов вместо нас.

Для начала импортируем fnmatch и модуль os для работы с операционной системой (у нас файлы хранятся в папке files на рабочем столе):

from fnmatch import filter
import os

path = r"C:\Users\FutureStep\Desktop\files"

Затем получаем список всех файлов:

files = os.listdir(path)

В переменной files будет такой список:

['ava_square.png', 'delete_this.txt', 'logo_blue.png', 'notes.txt', 'Python.png', 'task-25.docx', 'tasks.txt', 'watermark.png']

Теперь составим новый список, в котором будут находиться только имена файлов с расширением «txt»:

txt_files = filter(files, "*.txt")

В этом списке будет всего три элемента:

['delete_this.txt', 'notes.txt', 'tasks.txt']

Осталось лишь пройтись циклом for по txt_files и сгенерировать полный путь до файла:

for file in txt_files:
    name = rf"\{file}"

В переменной name будет строка такого формата:

C:\Users\FutureStep\Desktop\files\delete_this.txt

Её мы будем передавать в функцию remove() из модуля os, которая и удалит файл по этому пути.

В итоге мы создали вот такую небольшую программу для удобного удаления файлов определённого типа:

from fnmatch import filter
import os

path = r"C:\Users\FutureStep\Desktop\files"

files = os.listdir(path)

txt_files = filter(files, "*.txt")

for file in txt_files:
    name = rf"\{file}"
    os.remove(path+name)

Запускаем её и радуемся отсутствию текстовых файлов в нашей папке.

Помните, что мы в начале говорили про схожесть fnmatch с регулярными выражениями?

Так, в данном модуле есть специальная функция, которая служит неким мостом между миром подстановочных знаков и миром регулярных выражений. Эта функция называется translate().

Она преобразует шаблон fnmatch в эквивалентное регулярное выражение. Давайте преобразуем шаблон из прошлого примера, по которому мы искали файлы с расширением «txt», в регулярное выражение.

from fnmatch import translate

pat = '*.txt'
re_pat = translate(pat)
print(f'Регулярное выражение: {re_pat}')

>>>Регулярное выражение: (?s:.*\.txt)\Z

Полученное регулярное выражение уже можно применять с функциями модуля re. Аналогом функции fnmatch в регулярных выражениях является функция fullmatch().

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

from fnmatch import fnmatch, translate
import re

words = ["data.txt", "image.png", "notes.txt"]

# === Часть fnmatch === #
# Шаблон с подстановочными знаками
pat = '*.txt'

for word in words:
    if fnmatch(word, pat):
        print(f"{word} удовлетворяет шаблону {pat}")
    else:
        print(f"{word} НЕ удовлетворяет шаблону {pat}")

# Получаем регулярное выражение из шаблона
re_pat = translate(pat)

# === Часть re === #
for word in words:
    if re.fullmatch(re_pat, word):
        print(f"{word} удовлетворяет {re_pat}")
    else:
        print(f"{word} НЕ удовлетворяет {re_pat}")

>>>data.txt удовлетворяет шаблону *.txt
>>>image.png НЕ удовлетворяет шаблону *.txt
>>>notes.txt удовлетворяет шаблону *.txt
>>>data.txt удовлетворяет (?s:.*\.txt)\Z
>>>image.png НЕ удовлетворяет (?s:.*\.txt)\Z
>>>notes.txt удовлетворяет (?s:.*\.txt)\Z

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

Функция translate() дает возможность иметь «лучшее из обоих миров»: вы можете использовать простой синтаксис fnmatch для определения шаблона, а затем преобразовать его в регулярное выражение для более сложной обработки или для использования с другими функциями модуля re.

Алгоритм поиска делителей

В 25 заданиях второго типа нам предстоит работать с делителями чисел. Давайте вспомним основы теории чисел и, в частности, свойства делимости чисел. А также выведем свой простой и эффективный алгоритм поиска всех делителей какого-либо числа.

Найдём все делители числа 16. Начнём с того, что каждое целое число всегда делится на само себя и на единицу. Значит, мы уже нашли два делителя нашего числа 16: число 1 и 16.

Далее мы можем просто перебирать все числа от 1 до 16 и мысленно спрашивать себя «делится ли 16 на это число без остатка?». Первым таким числом будет 2: если 16 поделить на 2, то получится число 8.

Следующее число 3 нам уже не подходит, ведь 16 поделить на 3 без остатка уже не получится.

А вот число 4 уже подходит, причём при делении 16 на 4 получаем то же самое число 4. Это происходит потому, что 16 – это полный квадрат.

Полным квадратом в теории чисел называется некоторое число, являющееся квадратом некоторого целого числа. То есть квадратный корень из числа 16 извлекается нацело и, как мы уже знаем, равняется числу 4.

Мы нашли уже 4 делителя числа 16: 1, 2, 4 и 16. Осталось рассмотреть все числа от 5 до 15. Но мы ведь уже знаем, что поделив 16 на 2, получаем число 8. Значит, число 8, как и число 2, является еще одним делителем 16.

В итоге мы получаем ровно пять делителей числа 16: 1, 2, 4, 8 и 16. Причем обратите внимание, что тут можно выделить три группы чисел:

В первую группу относятся два числа: единица и само число
Во вторую группу отнесём квадратный корень, в тех случаях, когда наше число является полным квадратом
В третью группу отнесём парные делители числа: здесь это 2 и 8

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

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

Записываем все делители в список и возвращаем этот список из функции:

def get_divisors(num):
    divisors = []
    for i in range(1, num + 1):
        if num % i == 0:
            divisors.append(i)
    return divisors


print(get_divisors(16))

>>>[1, 2, 4, 8, 16]

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

Что же считать половиной всех делителей? На примере с числом 16 мы можем понять, что достаточно дойти до корня из числа, включительно. То есть, дойдя до корня из 16 мы получим три делителя: 1, 2 и сам корень числа 16 – 4. Оставшуюся часть делителей найдём делением 16 на 2 и 1: получим, соответственно, числа 8 и 16.

Теперь нужно разобраться с тем, как же правильно извлекать корень из числа в Python. Поскольку значение корня нам нужно будет передать в функцию range(), оно должно быть целым числом. Есть два способа получить целочисленное значение корня из числа num:

Используя синтаксис возведения в степень 0.5: int(num ** .5)
Используя функцию isqrt() из модуля math: isqrt(num)

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

Для сравнения времени работы обоих методов составим небольшую программу, которая засекает время работы функции с помощью модуля timit. Первая функция будет вычислять значения корня чисел от 1 до 1 000 с использованием iqsrt().

def get_sqrt_1():
    from math import isqrt
    sqrt_set = set()
    for num in range(1, 1_000):
        sqrt_set.add(isqrt(num))

Вторая функция будет делать то же самое, но с возведением числа в степень 0,5 и приведением результата к целочисленному типу:

def get_sqrt_2():
    sqrt_set = set()
    for num in range(1, 1_000):
        sqrt_set.add(int(num ** .5))

Запустим обе функции 10 000 раз и выведем время работы каждой в миллисекундах:

from timeit import timeit


def get_sqrt_1():
    from math import isqrt
    sqrt_set = set()
    for num in range(1, 1_000):
        sqrt_set.add(isqrt(num))


def get_sqrt_2():
    sqrt_set = set()
    for num in range(1, 1_000):
        sqrt_set.add(int(num ** .5))


t_1 = timeit(get_sqrt_1, number=10_000)
t_2 = timeit(get_sqrt_2, number=10_000)

print(f'Через isqrt: {t_1 * 10 ** 3:.2f} мс')
print(f'Через **.5: {t_2 * 10 ** 3:.2f} мс')

>>>Через isqrt: 885.63 мс
>>>Через **.5: 2364.18 мс

Таким образом, можно сделать вывод, что функция isqrt() работает примерно в 2,5 раза быстрее, чем int(num**0.5). Значит, впредь будем пользоваться только этой функцией.

Также для хранения делителей вместо списка мы будем использовать множество. Это нам поможет, во-первых, избавиться от повторения чисел в случае, когда мы работаем с полным квадратом (например, чтобы здесь число 4 не встречалось дважды), во-вторых, сэкономить немного памяти.

Добавлять в множество будем сразу по два элемента: найденный делитель и частное от деления исходного числа на этот делитель. Для этого можно воспользоваться операцией объединения множеств через метод update() или оператор «|=».

То есть множество всех делителей объединяем с множеством двух, найденных на текущей итерации цикла, делителей.

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

from math import isqrt


def get_divisors(num):
    divisors = set()
    for i in range(1, isqrt(num) + 1):
        if num % i == 0:
            divisors |= {i, num//i}
    return divisors

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

Обычно есть два способа выполнить эту операцию:

Взять остаток от деления числа на 10
Превратить число в строку и взять последний элемент строки через срез

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

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

Для первого способа напишем такую функцию:

def get_last_1():
    nums = set()
    for num in range(1_000):
        if num % 10 == 5:
            nums.add(num)

Для второго будем использовать такую:

def get_last_2():
    nums = set()
    for num in range(1_000):
        if str(num)[-1] == "5":
            nums.add(num)

И вызовем каждую функцию по 10 000 раз с помощью timeit.

from timeit import timeit


def get_last_1():
    nums = set()
    for num in range(1_000):
        if num % 10 == 5:
            nums.add(num)


def get_last_2():
    nums = set()
    for num in range(1_000):
        if str(num)[-1] == "5":
            nums.add(num)


t_1 = timeit(get_last_1, number=10_000)
t_2 = timeit(get_last_2, number=10_000)

print(f'Через % 10: {t_1 * 10 ** 3:.2f} мс')
print(f'Через str: {t_2 * 10 ** 3:.2f} мс')

>>>Через % 10: 646.67 мс
>>>Через str: 1350.87 мс

В результате получается, что первый способ работает примерно в 2 раза быстрее второго. Оно и не удивительно: в цикле мы перебираем целые числа, и для того, чтобы получить последнюю цифру этого числа первым способом, выполняется всего две операции: взятие остатка от деления на 10 и сравнение результата с числом 5.

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

А чтобы не быть голословными, приведём байт-код обеих операций: слева код взятия остатка от деления числа 1 на 10 и сравнения его с числом 5, а справа код приведения числа 1 к строке, взятие последнего элемента и сравнение его со строкой «5».

Для получения байт-кода наших функций мы воспользовались функцией dis() из одноимённого модуля:

import dis


def get_last_1():
    nums = set()
    for num in range(1_000):
        if num % 10 == 5:
            nums.add(num)


def get_last_2():
    nums = set()
    for num in range(1_000):
        if str(num)[-1] == "5":
            nums.add(num)


print(dis.dis(get_last_1))
print(dis.dis(get_last_2))

Подробнее о каждой инструкции байт-кода можете прочитать в документации.

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

Тип 1

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

Задание 2502

«Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
1) символ «?» означает ровно одну произвольную цифру;
2) символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 54?1?3*7, делящиеся на 18579 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 18579»

Сначала идёт базовая информация о том, что такое маска и какой символ что означает. Обратить внимание стоит на диапазон значений, в котором будем искать ответ. Обычно это диапазон натуральных чисел до 10¹⁰.

Далее в формулировке идёт маска, по которой и будем подбирать числа и условие, которому должны удовлетворять те числа, которые уже подходят под маску. В нашем случае такие числа должны делиться на 18 579 без остатка.

Что же, можем сразу перейти к написанию программы. Будем в цикле for перебирать все числа от 18 579 до 10¹⁰ с шагом 18 579 и сравнивать каждое с заданной маской. Если число подходит под маску, то будем выводить на экран это число и частное от деления числа на 18 579.

В коде это может выглядеть так:

from fnmatch import fnmatch

for i in range(18579, 10 ** 10, 18579):
    if fnmatch(str(i), '54?1?3*7'):
        print(i, i // 18579)

Однако это неэффективный код. Нам нет смысла рассматривать числа, которые явно не подойдут под заданную маску. А как мы поймём, какое будет минимальное число, подходящее под маску «54?1?3*7»?

Для этого достаточно вспомнить, что делают подстановочные знаки. Так, на месте знака «?» всегда должен быть какой-то символ. А поскольку мы работаем с числами, то минимальный возможный символ будет 0. Заменим в маске все «?» на цифру 0: «540103*7».

Переходим к знаку «*». Она может определять любую последовательность символов, но самое главное для нас – это то, что она определяет в том числе пустую последовательность.

Из этого можно сделать вывод: для того, чтобы получить минимальное число можно просто удалить «*» из маски. Следовательно, минимальное число, которое удовлетворяет маски из условия – это «5401037».

Докажем это утверждение, написав такую программу:

from fnmatch import fnmatch

num = "5401037"
mask = "54?1?3*7"


if fnmatch(num, mask):
    print(f"{num} удовлетворяет маске {mask}")
else:
    print(f"{num} НЕ удовлетворяет маске {mask}")

>>>5401037 удовлетворяет маске 54?1?3*7

Но число 5401037 не делится без остатка на 18 579. А мы же хотим перебирать только те числа, которые заведомо подходят под условие делимости. В таком случаем для начала диапазона можем взять ближайшее число, которое делится без остатка на 18 579, меньшее 5401037.

Это число можно получить из такой записи: 5401037 – 5401037 % 18579.

На этом и завершим оптимизацию нашего решения. В итоге получаем такую программу:

from fnmatch import fnmatch

for i in range(5401037 - 5401037 % 18579, 10 ** 10, 18579):
    if fnmatch(str(i), '54?1?3*7'):
        print(i, i // 18579)

Пример 1

Для закрепления разберём еще один пример на работу с масками. Подробно останавливаться на нём не будем, ведь решения заданий этого типа всегда шаблонное.

Формулировка будет такая:

Задание 2503

«Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 3?12?14*5, делящиеся на 1917 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им
результаты деления этих чисел на 1917»

Сразу находим минимальное число, подходящее под маску: заменяем «?» на нули, а «*» просто удаляем, получается число 30120145.

Далее просто подставляем значения в уже известный нам код:

from fnmatch import fnmatch

for i in range(30120145 - 30120145 % 1917, 10 ** 10, 1917):
    if fnmatch(str(i), '3?12?14*5'):
        print(i, i // 1917)

Пример 2

Ради интереса рассмотрим авторское 25 задание этого типа с такой формулировкой:

Задание 2508

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

Например, маске 123$4%5 соответствуют числа 123445 и 1236415.
Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 14$$5%, делящиеся на 3257 без остатка.
В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 3257»

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

Давайте рассуждать. Начнём со знака «$», который означает только одну чётную цифру. В контексте регулярных выражений такую же роль выполняет диапазон чётных цифр: «[02468]».

Для следующего знака – «%» – можем написать диапазон нечётных цифр и поставить после него квантификатор «*», который будет означать 0 и более повторений: «[13579]*».

В результате получаем такое регулярное выражение:

pat = r'14[02468][02468]5[13579]*'

Будем использовать его в связке с функцией fullmatch() из модуля re. А в остальном наш код будет не сильно отличаться от уже рассмотренного ранее. Разве что добавим счётчик и будем завершать цикл после 5 полученных значений.

Полный код для решения этого задания выглядит так:

import re

pat = r'14[02468][02468]5[13579]*'
cnt = 0
for i in range(14005 - 14005 % 3257, 10 ** 10, 3257):
    if re.fullmatch(pat, str(i)):
        print(i, i // 3257)
        cnt += 1
        if cnt == 5:
            break

Тип 2

Второй тип 25 заданий чуть более интересен, чем первый. Хотя по большей части решение будет все таким же шаблонным.

Начнём с такой формулировки:

Задание 2500

«Пусть М – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей нет, то считаем значение М равным нулю. Напишите программу, которая перебирает целые числа, больше 700 000, в порядке возрастания и ищет среди них такие, для которых М оканчивается на 4.
В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения М.

Например, для числа 20 М = 2 + 10 = 12»

Давайте выделим ключевые моменты из этой формулировки:

Работать будем с суммой минимального и максимального делителей
Сумма минимального и максимального делителей должна оканчиваться на 4
Перебирать нужно числа от 700 000

Перебор делителей и проверку суммы минимального и максимального мы поместим в одну функцию. С её первой частью вы уже знакомы, здесь в множество res будем сохранять все делители числа (кроме самого числа и единицы):

def f(num):
    res = set()
    for i in range(2, isqrt(num) + 1):
        if num % i == 0:
            res |= {i, num // i}

Во второй части мы проверяем, что делители у числа действительно есть, вычисляем сумму максимального и минимального, а также проверяем, что она оканчивается на 4:

if len(res):
    summ = min(res) + max(res)
    if summ % 10 == 4:
        return summ
return 0

Здесь запись if len(res) может быть немного непонятна. Дело в том, что если во множестве res есть хотя бы один элемент, то len(res) вернёт значение 1. Которое будет воспринято как истина для условия.

Эту же строку можно было записать по-разному, но результат все равно был бы одинаковый:

if len(res) > 0
if len(res) != 0
if len(res)

В итоге имеем такую функцию, которая и формирует число М из условия:

def f(num):
    res = set()
    for i in range(2, isqrt(num) + 1):
        if num % i == 0:
            res |= {i, num // i}

    if len(res):
        summ = min(res) + max(res)
        if summ % 10 == 4:
            return summ
    return 0

Теперь осталось просто перебрать в цикле for() все числа от 700 000, проверить, что M для текущего числа не равно 0 и вывести на экран сначала найденное число и само число M. Главное – не забыть добавить условие остановки цикла.

В коде это реализуется следующим образом:

cnt = 0
for i in range(700_001, 10 ** 20):
    if M := f(i):
        print(i, M)
        cnt += 1
        if cnt == 5:
            break

Обратите внимание, что в строке «if M := f(i)» мы использовали моржовый оператор. Он доступен с версии Python 3.8 и позволяет присваивать значения переменным прямо внутри выражения.

То есть здесь вместо присваивания значения функции переменной M и проверки этого значения в условии if:

M = f(i)
if M:

Мы же поместили оба действия в одну строку.

Вся программа для решения этого задания выглядит так:

from math import isqrt

def f(num):
    res = set()
    for i in range(2, isqrt(num) + 1):
        if num % i == 0:
            res |= {i, num // i}

    if len(res):
        summ = min(res) + max(res)
        if summ % 10 == 4:
            return summ
    return 0


cnt = 0
for i in range(700_001, 10 ** 20):
    if M := f(i):
        print(i, M)
        cnt += 1
        if cnt == 5:
            break

Пример 3

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

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

Но здесь мы рассмотрим довольно нешаблонную формулировку:

Задание 2505

«Напишите программу, которая перебирает целые числа, бо́льшие 800000, в порядке возрастания и ищет среди них такие, у которых есть натуральный делитель, оканчивающийся на цифру 9 и не равный ни самому числу, ни числу 9.

В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце — соответствующий минимальный делитель для каждого числа, оканчивающийся цифрой 9, не равный ни самому числу, ни числу 9.
Строки выводятся в порядке возрастания найденных чисел»

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

Составим функцию для поиска делителей по данному условию. Сначала ищем все делители числа:

def f(num):
    res = set()
    for i in range(2, isqrt(num) + 1):
        if num % i == 0:
            res |= {i, num // i}

Затем в цикле проверяем каждый делитель согласно условию:

for div in sorted(res):
    if div % 10 == 9 and div != 9:
        return div
return 0

Осталось дело за малым: перебираем числа от 800 001 и проверяем делители каждого по уже рассмотренному алгоритму.

cnt = 0
for i in range(800_001, 10 ** 20):
    if res := f(i):
        print(i, res)
        cnt += 1
        if cnt == 5:
            break

А полный код для решения этого задания будет таким:

from math import isqrt


def f(num):
    res = set()
    for i in range(2, isqrt(num) + 1):
        if num % i == 0:
            res |= {i, num // i}

    for div in sorted(res):
        if div % 10 == 9 and div != 9:
            return div
    return 0


cnt = 0
for i in range(800_001, 10 ** 20):
    if res := f(i):
        print(i, res)
        cnt += 1
        if cnt == 5:
            break