1. ЗАДАНИЕ ЕГЭ №25 В СПЕЦИФИКАЦИИ КИМ ДЛЯ ПРОВЕДЕНИЯ ЕГЭ ПО ИНФОРМАТИКЕ
|
№
|
Сведения из Спецификации контрольно-измерительных материалов для проведения в 2023 году ЕГЭ по информатике [2] |
|
|
1. |
Проверяемые элементы содержания |
Умение создавать собственные программы (10-20 строк) для обработки целочисленной информации |
|
2. |
Уровень сложности |
Высокий |
|
3. |
Максимальный балл за выполнение задания |
1 балл |
|
4 |
Примерное время выполнения задания |
20 мин |
|
5. |
Требуется использование специализированного программного обеспечения |
Среда программирования на языке программирования высокого уровня(одном из нижеследующих): С#, C++, Pascal, Java, Python |
2. ОСНОВНЫЕ ТИПЫ ЗАДАНИЯ №25 ЕГЭ ПО ИНФОРМАТИКЕ
Задание ЕГЭ по информатике №25, как правило, делятся на три основных вида:
- Задачи на поиск делителей;
- Задачи на простые числа;
- Задачи на маски чисел.
Также возможны задачи комбинированного типа, когда условие задания включает в себя одновременно две темы, например, «Маски чисел» и «Поиск делителей числа».
В статье рассматривается программное решение задач ЕГЭ №25 третьего типа. Данный тип задач является наиболее современным, т.к. именно задачи по теме «Маски чисел» были включены в КИМ ЕГЭ-2022 и ЕГЭ-2023.
3. ПРОГРАММНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАНИЯ №25 ЕГЭ ПО ИНФОРМАТИКЕ
Пример 1. В маске символ «*»
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
- символ «?» означает ровно одну произвольную цифру;
- символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 109, найдите все числа, соответствующие маске 1234*76 и делящиеся на 173 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце - соответствующие им результаты деления этих чисел на 173.
Решение задачи в два этапа:
1 этап. Определение количества возможных длин последовательностей цифр, соответствующих символу «*» в маске числа
Согласно условию, маска, которой должны соответствовать числа, содержит символ «*», означающий любую последовательность цифр произвольной длины; в том числе этот символ в маске может задавать и пустую последовательность т.е. отсутствие какой-либо цифры. Следовательно, перед составлением программы требуется определить количество возможных длин последовательностей цифр, соответствующую символу «*» в маске числа. Такое определение осуществляется путем сопоставления значения верхней границы, которую не могут превышать числа, и максимально возможного числа, которое может соответствовать маске числа. Разрядность данного числа должна быть на единицу меньше.
| Верхняя граница, которую не могут превышать подходящие числа 109 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Максимальное число, которое может соответствовать маске |
|
1 |
2 |
3 |
4 |
* |
7 |
6 |
||
Из представленной схемы видно, что максимально возможная длина последовательности цифр, соответствующую символу «*» в маске числа, равна 3. Таким образом, количество возможных длин последовательностей цифр, соответствующих символу «*» в маске, равно четыре, т.е. на месте «*» цифры могут отсутствовать или последовательность цифр может состоять из 1-го символа или из 2-х символов или из 3-х символов.
2 этап. Составление программы
Рассмотрим три простых программных способа решения задач по теме «Маски чисел».
1 способ решения. Методом формирования последовательностей возможных цифр, соответствующих «*» в маске числа, длиной в одну, две, три цифры. Также учитывается и случай, когда «*» в маске означает отсутствие каких-либо цифр.
Преимущество данного способа: простота и наглядность кода программы.
Существенный недостаток: длина кода программы зависит от максимальной длины последовательностей цифр, соответствующих «*» в маске. Чем больше длина последовательности символов, тем длиннее код программы. Так, в данной задаче максимальная длина «*» равна 3, соответственно, код программы содержит циклические конструкции, состоящие из одно цикла, из двух вложенных циклов, из трех вложенных циклов. Кроме того, учитывается случай, когда «*» в маске означает отсутствие каких-либо цифр.
Программа:
Ответ:
123402976 713312
123420276 713412
123437576 713512
123454876 713612
123472176 713712
123489476 713812
Как видно из примера, программа состоит из 4-х блоков. Первый блок проверяет число, в котором «*» задает пустую последовательность цифр, т.е. отсутствие какой-либо цифры. Второй блок проверяет числа, в которых «*» означает одну любую цифру. Третий блок проверяет числа, в которых «*» означает две любые цифры. Четвертый блок проверяет числа, в которых «*» означает три любые цифры.
2 способ решения. С использованием функции fnmatch() модуля fnmatch в Python. Функция fnmatch() модуля fnmatch является шаблонизатором, который проверяет, соответствует ли строка имени файла шаблонной строке, возвращая «True» или «False».
В программном решении задачи по теме «Маски чисел» выполняется перебор всех натуральных чисел из диапазона [1,109] с шагом 173. Таким образом обеспечивается кратность проверяемых чисел нужному значению. А в качестве строки имени файла в шаблонизаторе fnmatch используется очередное число из диапазона, преобразованное в сроковый вид.
Программа:
Ответ:
123402976 713312
123420276 713412
123437576 713512
123454876 713612
123472176 713712
123489476 713812
Преимущество данного способа: очень простой и лаконичный код программы.
Недостаток: при уменьшении шага в цикле, количество проверяемых чисел увеличивается, что существенно повышает время выполнения программы. Кроме того, при добавлении в условии задания дополнительных ограничений, дынный метод не всегда позволяет учесть в программе все возможные дополнительные ограничения.
3 способ решения. Автор предлагает универсальный и простой метод решения заданий по теме «Маски чисел», позволяющий решить любую задачу с любыми возможными дополнительными ограничениями. Для реализации данного метода используется функция product() из стандартной встроенной библиотеки itertools.
Поясняющий (иллюстративный) пример работы функции product() модуля itertools:
from itertools import product
for i in product('012', repeat = 2):
a = ''.join(i)
print(a)
Результат выполнения данной программы:
00
01
02
10
11
12
20
21
22
Как видно из примера, функция product ('012', repeat = 2) возвращает итерируемые последовательности из символов 0, 1, 2. Аргумент repeat = 2 определяет длину данных последовательностей.
По сути функция product ('012', repeat = 2) в данном примере является эквивалентом циклическим конструкциям, состоящим из двух вложенных циклов:
for i in '012':
for j in '012':
s = i + j
print(s)
Для решения задания по теме «Маски чисел» аргументу repeat задается значение изменяющегося параметра L. Так как в рассматриваемой задаче количество возможных длин последовательностей цифр, соответствующих символу «*», равно 4, параметр L изменяется в цикле от 0 до 3, и таким образом задает очередное значение длины последовательности цифр, соответствующих «*». Когда repeat = 0, элементы функцией product() не повторяются, соответственно, возвращается пустая последовательность. Когда repeat = 1, последовательно возвращается одна любая цифра из перечня '0123456789'. Когда repeat = 2, возвращаются итерируемые последовательности из символов '0123456789' длиной 2. Когда repeat = 3, возвращаются итерируемые последовательности из символов '0123456789' длиной 3.
Программа:
Ответ:
123402976 713312
123420276 713412
123437576 713512
123454876 713612
123472176 713712
123489476 713812
Данная программа с комментариями:
|
Программа |
Комментарий |
|
from itertools import * |
Подключение (импортирование) модуля itertools |
|
for L in range (0,3+1): |
Перебор возможных длин последовательностей цифр, соответствующих «*» |
|
for i in product('0123456789', repeat = L): |
Получение итерируемых последовательностей из символов '0123456789' длиной L |
|
a = ''.join(i) |
Конвертирование списка строк в строку |
|
x = int('1234' + a + '76') |
Получение очередной строки и преобразование этой строки в число, соответствующее маске |
|
if x%173==0: |
Проверка числа на кратность |
|
print (x, x//173) |
Т.к. полученное число соответствует маске и выполняется необходимая кратность, то такое число является подходящим, соответственно, вывод результата: выводится само число и результат его деления на 173 |
4. ПРИМЕНЕНИЕ МЕТОДА С ИСПОЛЬЗОВАНИЕМ ФУНКЦИИ PRODUCT
Пример 2. В маске символ «*» и символ «?»
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
- символ «?» означает ровно одну произвольную цифру;
- символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 109, найдите все числа, соответствующие маске 1234*?76 и делящиеся на 173 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце - соответствующие им результаты деления этих чисел на 173.
Решение:
1 этап. Определение количества возможных длин последовательностей цифр, соответствующих символу «*» в маске числа
| Верхняя граница, которую не могут превышать подходящие числа 109 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Максимальное число, которое может соответствовать маске |
|
1 |
2 |
3 |
4 |
* |
? |
7 |
6 |
|
2 этап. Составление программы
Ответ:
123402976 713312
123420276 713412
123437576 713512
123454876 713612
123472176 713712
123489476 713812
Пример 3. Задача с дополнительными ограничениями
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
- символ «?» означает ровно одну нечетную цифру, не кратную 3;
- символ «*» означает любую последовательность четных цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123485 и 12322475.
Среди натуральных чисел, не превышающих 109, найдите все числа, соответствующие маске 1234*?76 и делящиеся на 17 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце - соответствующие им результаты деления этих чисел на 17.
Решение:
1 этап. Определение количества возможных длин последовательностей цифр, соответствующих символу «*» в маске числа
| Верхняя граница, которую не могут превышать подходящие числа 109 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Максимальное число, которое может соответствовать маске |
|
1 |
2 |
3 |
4 |
* |
? |
7 |
6 |
|
2 этап. Составление программы
Ответ:
12340776 725928
12344176 726128
123408576 7259328
123422176 7260128
123442576 7261328
123486776 7263928
5. ЗАКЛЮЧЕНИЕ
Использование функции product() для решения заданий ЕГЭ по обработке целочисленной информации по теме «Маски чисел» позволяет сделать программный код лаконичным, простым и универсальным. Это относится как к типовым задачам, так и задачам с дополнительными ограничениями. Данный способ решения успешно применяется на практике при подготовке обучающихся к ЕГЭ по информатике. Так как программный код является лаконичным, простым и универсальным, обучающиеся усваивают его быстро и успешно применяют на экзамене.
Источники
- Демонстрационный вариант контрольных измерительных материалов единого государственного экзамена 2023 года по Информатике / подготовлен ФГБНУ «ФИПИ» - 2022.
- Спецификация контрольных измерительных материалов для проведения в 2023 году единого государственного экзамена по Информатике / подготовлена ФГБНУ «ФИПИ» - 2022.
- Кодификатор проверяемых требований к результатам освоения основной образовательной программы среднего общего образования и элементов содержания для проведения единого государственного экзамена по Информатике / подготовлен ФГБНУ «ФИПИ» - 2022.
Интернет-ресурсы
- ФГБНУ «Федеральный институт педагогических измерений» [электронный ресурс]. - URL https://fipi.ru
- Справочная документация по языку Python3 [электронный ресурс]. - URL https://docs-python.ru
- Преподавание, наука и жизнь: сайт Константина Полякова [электронный ресурс]. - URL https://kpolyakov.spb.ru