Задание 25
Задание 25 (демо-2023). Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа
123405 и 12300405.
Среди натуральных чисел, не превышающих 1010, найдите все числа, соответствующие
маске 1?2139*4, делящиеся на 2023 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания,
а во втором столбце – соответствующие им результаты деления этих чисел на 2023.
Решение задания проиллюстрировано ниже.
|
PascalABC.NET |
|
## var a:=1021394-(1021394 mod 2023); foreach var x in range(a,10bi**10,2023) do begin var s:=x.ToString; if (s[1]='1') and (s[3:7]='2139') and (s.Last='4') then println(s, x div 2023); end; |
|
Python |
|
a=1021394-(1021394 % 2023) for x in range(a,10**10,2023): s=str(x) if (s[0]=='1') and (s[2:6]=='2139') and (s[-1]=='4'): print(s, x // 2023) |
|
Python и модуль fnmatch |
|
from fnmatch import * for i in range(124065,12994965): if fnmatch(str(i),'12?4*65'): print(i,i//161)
|
Перебор и проверка всех чисел от 0 до 1010 слишком затратен по времени, нужно оптимизировать. Для начала можно определить наименьшее число, удовлетворяющее маске, это число 1021394 (на месте ? ставим наименьшую цифру 0, на месте * оставляем пустое место). Будем проходить по числам, кратным 2023 с соответствующим шагом. Первое число получим путём вычитания из нашего числа остатка от деления его на 2023:
var a:=1021394 – (1021394 mod 2023);
a = 1021394 – (1021394 % 2023)
Будем пробегать числа от a до 10**10 c шагом 2023, так нам не нужно будет постоянно проверять делимость на 2023.
Далее преобразуем текущее число в строковое представление, в PascalABC.NET это метод x.ToString, в Python функция str(x). Для проверки соответствия маске будем использовать срезы строк, в языках различается только индексация (в PascalABC.NET строки индексируются с единицы, а не с нуля). Также взятие последнего элемента различается, в Python отрицательный индекс означает отсчитывание элементов с конца, в PascalABC.NET срезы в квадратных скобках не поддерживают отрицательные индексы. Для этого существует функция .Last, возвращающая последний элемент, что более логично, даже исходя из названия метода.
Найдя подходящее число, выводим его и результат от деления его на 2023.
В Python для работы с масками существует библиотека fnmatch, которая проверяет, соответствует ли текущая строка шаблонной строке, где знак «?» означает один любой символ, а знак «*» любую последовательность символов, включая пустую. Функция fnmatch возвращает True или False.
То есть, чтобы выполнить это задание, нужно в цикле перебрать все числа в заданном диапазоне, и для тех, которые удовлетворяют функции fnmatch, вывести их значение и результат деления на 161.