Задание 25
тема 3 из 4

Числа по маске

Маска задаёт вид записи числа: знак вопроса заменяет ровно одну цифру, звёздочка — любую цепочку цифр, в том числе пустую. Программа перебирает только числа, кратные делителю из условия, и проверяет запись каждого функцией fnmatch или регулярным выражением. Ответ — найденные числа по возрастанию и частные от деления на делитель.

Часто в задании25На карте навыков

Как найти числа по маске

Маска — запись из цифр и знаков ? и *. Знак ? заменяет ровно одну цифру, знак * — любую последовательность цифр, в том числе пустую.

  • Перебирайте только кратные делителю kk: for n in range(k, limit + 1, k).
  • Проверяйте запись числа: fnmatch(str(n), mask) из модуля fnmatch.
  • Другой способ — регулярное выражение: ? пишут как [0-9], * — как [0-9]*, проверка re.fullmatch.
  • Печатайте n и n // k: числа выходят по возрастанию сами.

Маска: знаки «?» и «*»

Число соответствует маске, если его десятичную запись можно получить из маски: каждую цифру маски оставить, каждый ? заменить одной цифрой, каждую * — цепочкой цифр любой длины или ничем. Маска описывает всю запись числа от первой цифры до последней. Маске 123*4?5 соответствуют числа 123405 (звёздочка пустая) и 12300405 (звёздочка — 00).

Длина записи получается из маски. Каждая цифра и каждый ? дают ровно один знак, * — сколько угодно. Если в маске нет *, длина числа равна длине маски. Если есть, число не короче маски без звёздочек.

Пример

Какие из чисел 125, 1205, 12345, 13205, 1325 соответствуют маске 1*2?5?

  1. 1.Без звёздочки в маске четыре знака, число должно иметь не меньше четырёх цифр. 125 не подходит.
  2. 2.Последние три цифры числа должны иметь вид 2?5: двойка, любая цифра, пятёрка. Первая цифра — 1, звёздочка забирает всё между ними.
  3. 3.1205: 1, пустая звёздочка, 205 — подходит. 13205: 1, звёздочка 3, 205 — подходит.
  4. 4.12345 оканчивается на 345, 1325 — на 325: на месте двойки стоит 3. Не подходят.

Ответ: 1205 и 13205

Перебор кратных и проверка через fnmatch

В задании нужны числа до 101010^{10}, которые делятся на kk. Перебор всех десяти миллиардов чисел займёт часы. Кратные kk идут с шагом kk: range(k, limit + 1, k). Их в kk раз меньше: при k=1917k = 1917 это около 5 миллионов чисел, программа работает несколько секунд. «Не превышающих 101010^{10}» — граница входит, поэтому limit + 1.

Функция fnmatch(s, mask) из модуля fnmatch проверяет, соответствует ли строка s маске целиком. В ней ? — ровно один символ, * — любая цепочка символов, в том числе пустая. Это те же правила, что в задании, поэтому маску из условия передают без изменений. Запись числа даёт str(n), частное — n // k.

Пример

Среди натуральных чисел, не превышающих 10710^7, найдите все числа, которые соответствуют маске 1?3*7 и делятся на 2021. Для каждого укажите частное от деления на 2021.

  1. 1.Цикл перебирает кратные 2021: range(2021, 10**7 + 1, 2021), это меньше 5000 чисел.
  2. 2.fnmatch(str(n), '1?3*7') пропускает числа, которые начинаются с 1, имеют 3 третьей цифрой и оканчиваются на 7.
  3. 3.Для 1630947: 1, затем 6 на месте ?, 3, звёздочка 094, 7. Частное 1630947/2021=8071630947 / 2021 = 807.

Ответ: 1630947 807, 1731997 857, 1833047 907, 1934097 957

Проверка регулярным выражением

Регулярное выражение — шаблон строки из модуля re. В нём [0-9] означает одну любую цифру, а [0-9]* — любое число цифр, в том числе ноль. Маску переводят в шаблон знак за знаком: ? становится [0-9], * становится [0-9]*, цифры остаются. Маска 2?4*9 превращается в 2[0-9]4[0-9]*9.

Проверяйте функцией re.fullmatch: она требует, чтобы шаблону соответствовала вся строка. Функция re.match проверяет только начало строки, а re.search ищет шаблон в любом месте. С ними пройдут числа с лишними цифрами в конце или в начале.

Пример

Среди натуральных чисел, не превышающих 10710^7, найдите все числа, которые соответствуют маске 2?4*9 и делятся на 3031. Для каждого укажите частное.

  1. 1.Шаблон: 2[0-9]4[0-9]*9.
  2. 2.Цикл перебирает кратные 3031 и проверяет re.fullmatch(pattern, str(n)).
  3. 3.Для 2148979: 2, 1, 4, цепочка 897, 9. Частное 2148979/3031=7092148979 / 3031 = 709.

Ответ: 2148979 709, 2543009 839, 2846109 939

Порядок ответа

Ответ — таблица: в первом столбце найденные числа по возрастанию, во втором — частные от деления на kk. Цикл по кратным идёт от меньших чисел к большим, поэтому программа печатает строки уже в нужном порядке. Частное не надо считать отдельно: это n // k.

Пример задания

Открытый банк ФИПИ

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

Среди натуральных чисел, не превышающих 1010, найдите все числа, соответствующие маске 3?12?14*5, делящиеся на 1917 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 1917. Количество строк в таблице для ответа избыточно.

Звёздочка рядом со знаком вопроса

Если в маске стоят подряд * и ?, вместе они означают одну или больше любых цифр. Разделить эти цифры между знаками можно по-разному, но число учитывается один раз: fnmatch отвечает только «да» или «нет». Длину числа по-прежнему задают знаки без звёздочки. Маске 9*?001?1 соответствуют числа из 7 цифр и длиннее.

Пример задания

Открытый банк ФИПИ

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
- символ «?» означает ровно одну произвольную цифру;
- символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405. Среди натуральных чисел, не превышающих 1010, найдите все числа, соответствующие маске 9*?001?1, делящиеся на 12007 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце - соответствующие результаты деления этих чисел на 12007. Количество строк в таблице для ответа избыточно.

Потренируйте навык

Все задания на этот навык

Решать