Числа по маске
Маска задаёт вид записи числа: знак вопроса заменяет ровно одну цифру, звёздочка — любую цепочку цифр, в том числе пустую. Программа перебирает только числа, кратные делителю из условия, и проверяет запись каждого функцией fnmatch или регулярным выражением. Ответ — найденные числа по возрастанию и частные от деления на делитель.
Как найти числа по маске
Маска — запись из цифр и знаков ? и *. Знак ? заменяет ровно одну цифру, знак * — любую последовательность цифр, в том числе пустую.
- Перебирайте только кратные делителю :
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.Без звёздочки в маске четыре знака, число должно иметь не меньше четырёх цифр. 125 не подходит.
- 2.Последние три цифры числа должны иметь вид
2?5: двойка, любая цифра, пятёрка. Первая цифра — 1, звёздочка забирает всё между ними. - 3.1205: 1, пустая звёздочка, 205 — подходит. 13205: 1, звёздочка 3, 205 — подходит.
- 4.12345 оканчивается на 345, 1325 — на 325: на месте двойки стоит 3. Не подходят.
Ответ: 1205 и 13205
Перебор кратных и проверка через fnmatch
В задании нужны числа до , которые делятся на . Перебор всех десяти миллиардов чисел займёт часы. Кратные идут с шагом : range(k, limit + 1, k). Их в раз меньше: при это около 5 миллионов чисел, программа работает несколько секунд. «Не превышающих » — граница входит, поэтому limit + 1.
Функция fnmatch(s, mask) из модуля fnmatch проверяет, соответствует ли строка s маске целиком. В ней ? — ровно один символ, * — любая цепочка символов, в том числе пустая. Это те же правила, что в задании, поэтому маску из условия передают без изменений. Запись числа даёт str(n), частное — n // k.
Пример
Среди натуральных чисел, не превышающих , найдите все числа, которые соответствуют маске 1?3*7 и делятся на 2021. Для каждого укажите частное от деления на 2021.
- 1.Цикл перебирает кратные 2021:
range(2021, 10**7 + 1, 2021), это меньше 5000 чисел. - 2.
fnmatch(str(n), '1?3*7')пропускает числа, которые начинаются с 1, имеют 3 третьей цифрой и оканчиваются на 7. - 3.Для 1630947: 1, затем 6 на месте
?, 3, звёздочка 094, 7. Частное .
Ответ: 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 ищет шаблон в любом месте. С ними пройдут числа с лишними цифрами в конце или в начале.
Пример
Среди натуральных чисел, не превышающих , найдите все числа, которые соответствуют маске 2?4*9 и делятся на 3031. Для каждого укажите частное.
- 1.Шаблон:
2[0-9]4[0-9]*9. - 2.Цикл перебирает кратные 3031 и проверяет
re.fullmatch(pattern, str(n)). - 3.Для 2148979: 2, 1, 4, цепочка 897, 9. Частное .
Ответ: 2148979 709, 2543009 839, 2846109 939
Порядок ответа
Ответ — таблица: в первом столбце найденные числа по возрастанию, во втором — частные от деления на . Цикл по кратным идёт от меньших чисел к большим, поэтому программа печатает строки уже в нужном порядке. Частное не надо считать отдельно: это 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. Количество строк в таблице для ответа избыточно.