Особенности решения задания 17 К-ЕГЭ

Задание 17 ЕГЭ по своей сути является логическим продолжением задания 15.2 ОГЭ, только поданным на более высоком, соответствующем для выпускников 11 класса, уровне.

По своей сути, это все то же задание на обработку числовой последовательности. Но в отличие от задания 15.2 ОГЭ, оно состоит из двух подзадач, и основная задача имеет более комплексное условие отбора данных.

На примере решения задания 17 диагностической работы Статград от 14.02.2023 года разберем основные этапы решения.

Ремарка: лично мне очень нравятся работы Статград (не все коллеги разделяют мои взгляды), так как чаще всего они содержат определенную изюминку и требуют хорошего понимания математики (отмечу особо — не знания, а именно, понимания).

Итак, рассмотрим задачу:

«Файл содержит последовательность целых чисел, по модулю не превышающих 10 000. Назовём парой два идущих подряд элемента последовательности.

Определите количество пар, для которых выполняются следующие условия:

• запись элементов пары заканчивается одной и той же цифрой;

• ровно один элемент из пары делится без остатка на 7;

• сумма квадратов элементов пары не превышает квадрат наименьшего из элементов последовательности, запись которых заканчивается цифрой 7.

В ответе запишите два числа: сначала количество найденных пар, затем максимальную величину суммы квадратов элементов этих пар.»

В тексте задачи практически нет лишних формулировок, поэтому очень сложно цитировать задачу, пытаясь выделить главное. Главное здесь все.

Обратим внимание на третий пункт, по которому определяется отбор пар чисел: «сумма квадратов элементов пары не превышает квадрат наименьшего из элементов последовательности, запись которых заканчивается цифрой 7».

Фактически, данный пункт является формулировкой первой подзадачи: нахождение наименьшего значения элемента последовательности, который заканчивается на цифру 7. Формализуя данное условие, мы получаем задачу нахождения минимального значения элемента последовательности, удовлетворяющего определенным условиям. А данная задача является типовой, и, фактически, почти полностью повторяет задание 15.2 ОГЭ.

Особо хочу отметить условие «запись которых заканчивается цифрой 7».

К огромному сожалению, на просторах Интернета все чаще используются решения, которые являются чисто механистическими и эксплуатируют частные возможности того или иного языка программирования без углубления в суть вопроса. Таким образом, ученик, научившийся решать подобную задачу, используя данный подход, становится беспомощным, когда поступив в институт, ему необходимо решать подобные задачи на других языках программирования. Или же, когда требуется более глубокий анализ, который затрагивает математическую суть данной задачи.

В частности, частенько используется свойство Python воспринимать содержимое файла, как набор строк. Таким образом, число, попавшее на вход программе, интерпретируется как символьная строка. Возникает соблазн просто посмотреть на последний символ. Вроде хорошее решение, но строковые операции работают медленнее, чем операции над числовыми данными, в подавляющем количестве случаев (использование косвенно-индексной адресации вместо прямой, поиск последнего элемента связного списка и т.д…). И это я еще не говорю о том, что последним символом строки, прочтенной из файла будет совсем не цифра, а символ(ы) конца строки, которые, например, в ОС Linux имеют вид CR, а в ОС Windows — CR/LF. То есть, возникает необходимость глазками проверить, а что там у нас в конце строки и сколько места это занимает.

Следующий момент — необходимость найти среди найденных чисел минимальное требует преобразования к числу в любом случае. Плюс, такое решение значительно усложняет алгоритм в языках программирования со строгой типизацией (С++, С, Java, Pascal). Поэтому, откажемся от такого способа и будем рассматривать введенные данные, как число.

И здесь мы сталкиваемся с теорией математики, настолько же очевидной, насколько и глубокой одновременно. А именно, как работает традиционный способ получения последней цифры записи числа: получение остатка от деления на основание системы счисления. И здесь мы сталкиваемся с особенностью языка Python, которая может поставить в тупик человека, не знакомого с математикой. И дьявол кроется в строке задачи «целых чисел, по модулю не превышающих 10 000». То есть, подразумевается, что числа могут быть отрицательными. И это главный подводный камень.

Если мы попробуем на языке Python найти остаток от деления 123 на 10 мы ожидаемо получим число 3. Но если мы попробуем найти остаток от деления числа -123 на 10, мы неожиданно получаем число 7, что никак не похоже на последнюю цифру числа -123. Как такое могло получиться?

Обратимся к теории чисел.

Теорема: для любых целых чисел n и q существуют единственным образом определенные целые числа m и r, удовлетворяющие условиям:

\[ \left \{ {n=m \cdot q+r\\0 \leq |r| <|q|\\Sign(q)=Sign(r)}  \right.\] , где Sign(x) — функция определения знака числа x.

Таким образом, будем называть число r остатком от деления n на q, а число m — неполным частным (целой частью) от деления n на q.

Доказательство данной теоремы оставим для любознательных и пытливых умом. Оно несложное, и может быть проведено любым учеником 11 класса, владеющим методом доказательств.

Ключевое в данной теореме — соответствие знака q и знака r. Посчитаем значения остатков от деления и неполного частного на различных примерах, используя данную теорему:

Если вы попробуете в Python выполнить действия нахождения остатка от деления n на q и нахождения неполного частного от деления n на q над значениями, приведенными в таблице, вы обнаружите, что результат будет в точности соответствовать значениям m и r в вышеуказанной таблице. Таким образом, в отличие от того же Pascal, Python работает в точности в соответствии с теорией чисел и дает математически предсказуемый результат, в отличие от интуитивно предсказуемого в Pascal.

Таким образом, в процессе определения последней цифры числа в языке Python, нам необходимо учитывать знак числа. Иными словами, если мы видим словосочетание «по модулю не превышающих», то и следует использовать функцию abs() при операциях нахождения остатка.

Итак, вроде как все подводные камни теоретического материала рассмотрены, приступаем к реализации алгоритма:

infile=open('17.txt')
m7=10001 ## При поиске минимум начинаем с «невероятно» большого числа
for a in infile: ## перебираем строки файла
     a=int(a) ## преобразуем строку в целое число
     if abs(a)%10==7: ## Не забываем, что проверяем модуль числа
          m7=min(m7,a)

Да, для тех, кто теперь будет мне говорить о том, что стоит избегать специфических для языка методов, привожу следующий фрагмент:

infile=open('17.txt')
m7=10001 ## При поиске минимум начинаем с «невероятно» большого числа
for a in infile: ## перебираем строки файла
     a=int(a) ## преобразуем строку в целое число
     if abs(a)%10==7:
          if a<m7:
               m7=a

Далее, мы сталкиваемся с особенностями файла и тут не грех вспомнить различные виды памяти. Итак, мы все привыкли, что мы можем получить доступ к любым данным, по их адресу. То есть, мы воспринимаем любую память как память с произвольной выборкой (random access memory). Однако, это справедливо только отчасти. В той же самой оперативной памяти, чтобы прочитать 1 байт информации, современный процессор получает из памяти блок из 8 байт, из которых потом выбирает нужный. При чтении с диска, за одну операцию чтения извлекается сектор (кластер), который представляет из себя последовательность от 512 до 64536 байт. Файл же, как понятие, ведет свою родословную от ленточных накопителей информации, где до нужного участка памяти можно добраться только перемотав определенное количество ленты от начала. И приемы работы с файлом с тех пор не изменились и он представляет из себя образец памяти с последовательным доступом. Таким образом, ненавязчиво нарисовалась тема архитектуры компьютера. А проявляется это в том, что найдя минимум числовой последовательности в первой подзадаче, мы прочитали файл до конца, и для повторного чтения необходимо «перемотать» файл в начало. К счастью, делается это не сложно, одной командой:

infile.seek(0)

В Интернете можно найти множество вариантов решения задачи, когда файл считывается в список, а затем обрабатываются данные в оперативной памяти. Это не очень хорошая идея. Во-первых, списки в Python — далеко не локальная структура данных, то есть, при обработке списков Python мы с высокой вероятностью будем промахиваться мимо кэша процессора. Таким образом, эффект от использования оперативной памяти выглядит довольно сомнительным. Во-вторых, сама по себе идея закачивать файл на диске в оперативную память — так себе, так как файл может быть очень большим и может легко сожрать всю доступную оперативную память, включая виртуальную. Мне могут легко возразить, что в данном задании файл не такой уж и большой. Ну так и отлично, значит после первого чтения он почти весь лежит в файловом кэше в оперативной памяти, который, в отличие от списков Python является локальной структурой данных, и повторное чтение будет производиться уже из оперативной памяти с максимальным использованием кэша процессора. В сухом остатке, я не вижу серьезных преимуществ чтения файла в память. В любом случае, это хороший повод провести серию тестов на быстродействие разных способов, что будет критично при выполнении 27 задания. Но это уже другая история.

Далее мы можем приступать к решению основной задачи.

Читаем условие: «Назовём парой два идущих подряд элемента последовательности.». Итак, в нашем распоряжении имеется пара чисел, которые идут друг за другом подряд. Что бы это могло быть? А это есть ничто иное, как подготовка учащихся к введению в виртуальные структуры данных, таких как стеки, деки и очереди. И в данном случае, мы видим простейшую очередь из двух элементов. Первый элемент — это «голова» очереди (head), а второй - «хвост» (tail). Для организации очереди принято использовать списки, но в данном случае это не рационально (имеем в виду, что это еще не изучение, а только подготовка учащихся к восприятию подобных структур данных). Поэтому, мы будем использовать пару переменных, например, a и a1. Имена взяты для примера, можно использовать любые другие. Просто в математике член арифметической последовательности обычно обозначается буквой a.

Далее начинаются технические тонкости. Дело в том, что в языке Python переменная создается в результате операции присваивания. Таким образом, в переменной ВСЕГДА находится какое-то значение. Даже если отвязаться от языка Python и перейти к определению переменной, как поименованной области памяти, предназначенной для хранения значения определенного типа, надо понимать, что переменная всегда указывает на некую область памяти. А любая область памяти работающего компьютера всегда содержит какую-либо комбинацию нулей и/или единиц, то есть какое-то значение. Отсюда строгое требование в языках типа C/C++ к инициализации начального значения — при создании переменной в программе, она указывает на область данных, где хранится случайное значение, оставшееся от процессов, которые использовали эту память до запуска нашей программы.

В Python этот вопрос решен самим способом создания переменной (переменная создается в результате инициализации), но самое главное это то, что переменная ВСЕГДА хранит какое-либо значение. К чему весь этот пассаж? Да к тому, что при первом чтении из файла, переменная a (head) будет содержать значение из файла, то есть из последовательности, а вот переменная a1 (tail) будет хранить значение, которое не принадлежит файлу. То есть, в этот момент мы не можем рассматривать числа a и a1 как пару. Таким образом, возникает необходимость каким-то образом отфильтровать это лишнее значение. Хорошим решением будет способ, как в алгоритме поиска минимума или максимума — инициализировать переменную «невероятным» значением, то есть значением, которое выходит за пределы значений последовательности. Читаем задание: «Файл содержит последовательность целых чисел, по модулю не превышающих 10 000». Таким образом, мы можем спокойно инициализировать «хвост» очереди значением <-10 000 или >10 000.

Далее, так как мы переходим к решению основной задачи, неплохо бы прочитать, чего от нас хотят: «В ответе запишите два числа: сначала количество найденных пар, затем максимальную величину суммы квадратов элементов этих пар». Значит нам надо подготовить еще 2 переменные: cp (для количества пар)и maxs (для максимальной суммы).

Начинаем кодить:

cp=0
maxs=0
a1=-10001
for a in infile:
     a=int(a)
     if a1>-10001: ## Вот в этом месте мы проверяем, что наша очередь полная, 
                   ## то есть, все значения a и a1 принадлежать последовательности
          if ( (abs(a)%10==abs(a1)%10) and ## запись элементов пары заканчивается 
                                           ## одной и той же цифрой
             ((abs(a)%7==0)+(abs(a1)%7==0)==1) and ## ровно один элемент из пары 
                                                   ## делится без остатка на 7
             (a**2+a1**2<=m7**2)): ## сумма квадратов элементов пары не превышает  
                                   ## квадрат наименьшего из элементов  последовательности, 
                                   ## запись которых заканчивается цифрой 7
               cp+=1 ## Увеличиваем счетчик пар на 1 
               maxs=max(maxs,a**2+a1**2) ## Запоминаем максимальную сумму  квадратов
     a1=a ## «Проталкиваем» значение по очереди

print(cp, maxs) ## Выводим результаты

Все! Задача решена! Осталось запустить и перенести ответ в бланк ответов (электронный или бумажный — кому как повезло).

Особо хочу отметить очень важный момент. В ответ надо записывать числа в том порядке, в каком они указаны в условии!!! Если вы посчитали все правильно, но сначала внесли максимальную сумму, а потом количество пар — вы получите 0 баллов за задание, как за неверный ответ. И это не придирка. Если вы сдаете ЕГЭ по информатике, следовательно вы планируете свое развитие в сфере IT. А в программировании порядок следования параметров очень важен, и уже скоро вы это почувствуете, когда в институте начнете создавать более сложные программы и участвовать в проектах с другими программистами…

Итак, подытожим.

1. Полный код задачи:

infile=open('17.txt')

m7=10001 ## При поиске минимум начинаем с «невероятно» большого числа
for a in infile: ## перебираем строки файла
     a=int(a) ## преобразуем строку в целое число
     if abs(a)%10==7: ## Не забываем, что проверяем модуль числа
          m7=min(m7,a)

infile.seek(0)

cp=0
maxs=0
a1=-10001
for a in infile:
     a=int(a)
     if a1>-10001: ## Вот в этом месте мы проверяем, что наша очередь полная, 
                   ## то есть, все значения a и a1 принадлежать последовательности
          if ( (abs(a)%10==abs(a1)%10) and ## запись элементов пары заканчивается 
                                           ## одной и той же цифрой
             ((abs(a)%7==0)+(abs(a1)%7==0)==1) and ## ровно один элемент из пары 
                                                   ## делится без остатка на 7
             (a**2+a1**2<=m7**2)): ## сумма квадратов элементов пары не превышает  
                                   ## квадрат наименьшего из элементов  последовательности, 
                                   ## запись которых заканчивается цифрой 7
               cp+=1 ## Увеличиваем счетчик пар на 1 
               maxs=max(maxs,a**2+a1**2) ## Запоминаем максимальную сумму  квадратов
     a1=a ## «Проталкиваем» значение по очереди

print(cp, maxs) ## Выводим результаты

2. Что проверяем (ну кроме того, что официально в кодификаторе записано):

• элементы теории чисел

• особенности выполнения арифметических операций в языках программирования

• элементы архитектуры компьютера

• структуры данных

• базовые алгоритмы поиска и отбора значений по заданным критериям.