Задание 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.



Последнее изменение: Понедельник, 22 мая 2023, 19:24