Маска числа — это последовательность цифр с символами ? (одна произвольная цифра) и * (любая последовательность цифр произвольной длины, включая пустую), используемая для поиска чисел, удовлетворяющих определенным условиям.
Основы работы с масками
Символ ? означает ровно одну произвольную цифру от 0 до 9. Символ * означает любую последовательность цифр произвольной длины; в том числе может задавать пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Метод 1: Вложенные циклы
Этот метод подходит для масок с символом *, когда нужно перебрать все возможные варианты подстановки цифр.
Алгоритм решения
Шаг 1: Определите максимальную длину последовательности, которую может заменять *. Для этого сравните верхнюю границу чисел (обычно 10⁹) с максимальным числом, соответствующим маске.
Шаг 2: Создайте циклы для перебора всех возможных подстановок. Количество вложенных циклов зависит от максимальной длины — для длины 3 понадобятся циклы с одним, двумя и тремя уровнями вложенности.
Пример кода с вложенными циклами
# Задача: найти числа, соответствующие маске 1234*76, делящиеся на 173
# Максимальная длина * равна 3 (числа до 10^9)
# Случай 1: * означает пустую последовательность
n = int('123476')
if n <= 10**9 and n % 173 == 0:
print(n, n // 173)
# Случай 2: * означает одну цифру
for a in range(10):
n = int(f'1234{a}76')
if n <= 10**9 and n % 173 == 0:
print(n, n // 173)
# Случай 3: * означает две цифры
for a in range(10):
for b in range(10):
n = int(f'1234{a}{b}76')
if n <= 10**9 and n % 173 == 0:
print(n, n // 173)
# Случай 4: * означает три цифры
for a in range(10):
for b in range(10):
for c in range(10):
n = int(f'1234{a}{b}{c}76')
if n <= 10**9 and n % 173 == 0:
print(n, n // 173)
Преимущества и недостатки
Преимущества: Простота кода, наглядность логики, легко понять алгоритм.
Недостатки: Код становится длинным при больших значениях длины *, требуется много вложенных циклов.
Метод 2: Библиотека fnmatch
Библиотека fnmatch предоставляет готовые функции для работы с шаблонами, использующими подстановочные символы.
Основные функции fnmatch
fnmatch.fnmatch(строка, шаблон) — проверяет, соответствует ли строка заданному шаблону, возвращает True или False. Символ * заменяет любое количество символов, а символ ? — только один символ.
Пример кода с fnmatch
from fnmatch import fnmatch
# Задача: найти числа, соответствующие маске 12*93?, делящиеся на 3127
for n in range(0, 10**9 + 1, 3127):
if fnmatch(str(n), '12*93?'):
print(n, n // 3127)
Оптимизация с шагом перебора
Для ускорения работы используйте делитель как шаг цикла вместо проверки каждого числа:
from fnmatch import fnmatch
# Если нужно найти числа, делящиеся на 31 и 2031 одновременно
delitel = 31 * 2031 # НОК делителей
for n in range(0, 10**9 + 1, delitel):
if fnmatch(str(n), '12*93?'):
print(n)
Задачи с дополнительными условиями
Когда символы ? и * имеют особые ограничения (например, ? — только нечетные цифры, не кратные 3; * — только четные цифры), используйте комбинацию циклов и проверок:
# Задача: маска 1234*?76, где ? — нечетная цифра не кратная 3,
# * — четные цифры произвольной длины
# Нечетные цифры, не кратные 3: 1, 5, 7
nechet = [1, 5, 7]
# Четные цифры: 0, 2, 4, 6, 8
chet = [0, 2, 4, 6, 8]
# Пустая последовательность для *
for d in nechet:
n = int(f'1234{d}76')
if n <= 10**9 and n % 17 == 0:
print(n, n // 17)
# Одна четная цифра для *
for a in chet:
for d in nechet:
n = int(f'1234{a}{d}76')
if n <= 10**9 and n % 17 == 0:
print(n, n // 17)
# Две четные цифры для *
for a in chet:
for b in chet:
for d in nechet:
n = int(f'1234{a}{b}{d}76')
if n <= 10**9 and n % 17 == 0:
print(n, n // 17)
Сравнение методов
Вложенные циклы подходят, когда длина * невелика (1-3 цифры) и нужен полный контроль над перебором, особенно при специальных ограничениях на символы. Библиотека fnmatch удобна для стандартных масок с большой длиной *, так как код короче и читабельнее, а оптимизация шагом перебора значительно ускоряет выполнение.
Общие рекомендации
Всегда начинайте с определения максимальной длины последовательности для * путем сравнения верхней границы и максимально возможного числа маски. При наличии условий делимости используйте делитель (или их НОК) как шаг цикла для сокращения числа итераций. Проверяйте соответствие маске до проверки других условий для оптимизации производительности.