Задание №25 ЕГЭ Информатика с ответом и решением
Ответ: 1226156 3868 12321156 38868 12511356 39468 12701556 40068 12891756 40668
Условие
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
— символ «?» означает ровно одну произвольную цифру;
— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 108, найдите все числа, соответствующие маске 12??1*56, делящиеся на 317 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им результаты деления этих чисел на 317.
Количество строк в таблице для ответа избыточно.
Подсказки — как подойти к решению
- Удобный путь — перебор чисел, кратных делителю, с шагом, равным делителю: делимость проверять не придётся, останется сверка с маской.
- Разбери маску: два «?» — ровно по одной цифре, а «*» — любая последовательность цифр, включая пустую. Из-за ограничения из условия на месте звёздочки помещается немного цифр, поэтому кандидатов удобно строить вложенными циклами.
- Проверяй, что кандидат заканчивается нужными цифрами и что цифры на местах «?» действительно произвольны, а в ответ выпиши пары значений — число и результат деления — по возрастанию чисел.
Решение
Будем последовательно рассматривать каждое целое число, кратное 317. затем каждое число проверять на соответствие маске.
Приведём решение на языке Python.
from fnmatch import *
for x in range(0, 10**8, 317): # Перебираем все числа от 0 с шагом 317, будут получены числа кратные 317
if fnmatch(str(x), '12??1*56'):# Проверяем полученное число соответствию заданию
print(x, x // 317)
В результате работы программа должна вывести следующее:
1226156 3868
12321156 38868
12511356 39468
12701556 40068
12891756 40668
Приведём решение Евгения Джобса.
Заметим, что при ограничении до 108 на месте звездочки может стоять не больше одного разряда. Поэтому достаточно перебрать два варианта — пустая строка на месте звездочки и 1 символ на месте звездочки.
for a in range(10):
for b in range(10):
x = 12*10**5 + a*10**4 + b*10**3 + 156
# можно заменить на
# x = int(f'12{a}{b}156')
if x % 317 == 0:
print(x, x // 317)
for a in range(10):
for b in range(10):
for c in range(10):
x = 12*10**6 + a*10**5 + b*10**4 + 1*1000 + c*100 + 56
# можно заменить на
# x = int(f'12{a}{b}1{c}56')
if x % 317 == 0:
print(x, x // 317)
Приведём другое решение на языке Python.
a = ['', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
for i in range(0,10):
for j in range(0,10):
for k in a:
s = '12' + str(i) + str(j) + '1' + k +'56'
n = int(s)
if n % 317 == 0:
print(n, n // 317)
Приведём решение Егора Чернецова на языке Python.
from re import fullmatch
for n in range(0, 10**8, 317):
if fullmatch(r'12\d{2}1.*56', str(n)):
print(n, n // 317)
Приведём решение Юрия Красильникова на языке Python.
d = '0123456789'
nums = sorted([int(f'12{x}{y}1{s}56') for x in d for y in d for s in ['']+list(d)])
for y in [x for x in nums if x % 317 == 0]: print(y,y//317)
Приведём решение Сергея Донец на PascalABC.NET:
begin
var d := 317;
var minMask := 1200156;//12??1*56
var maxMask := 120019956;
var maxLimit:= 100000000;
var start := minMask + (d - minMask mod d) mod d;
var finish:= Min(maxLimit, maxMask);
for var i := start to finish step d do
if i.ToString.IsMatch('^12..1.*56$') then
Println(i, i div d);
end.
Типичные ошибки
- Потеряно число с пустой звёздочкой: такой вариант тоже соответствует маске, потому что «*» может задавать и нуль цифр.
- В таблице оставлен только первый столбец: по условию рядом с каждым числом должен стоять результат его деления на делитель.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №25 по информатике