Как писать программы к заданиям ЕГЭ
Общий подход к написанию программ одинаковый и в крупной IT-компании, и в школьном классе. Соответственно, основные принципы и ошибки одинаковые. Очень хорошо, если у выпускника есть возможность использовать опыт промышленной разработки на ЕГЭ. Подобным опытом я и хочу поделиться. Разумеется, с учётом специфики экзамена.
Это общая, обзорная статья, которая нужна скорее для общего понимания стратегии программирования в ЕГЭ по информатике, нежели для решения конкретных заданий. Возможно, позже я эти задания и разберу.
Поскольку ЕГЭ по информатике целиком выполняется с использованием компьютера, и для каждого задания можно попытаться написать программу, выделение заданий "на программирование" очень условное. В заголовке я перечислил те задания, для которых я считаю использование программ наиболее рентабельным. И уж конечно, всегда можно отказаться от программирования и попытаться решить задачу аналитически, другими средствами автоматизации или вообще вручную.
На уроках информатики и при занятиях с репетитором, ученик видит, как учитель(репетитор) пишет программу с первой до последней строчки, запускает выполнение, и - о, чудо! - программа выдаёт конечный результат.
Происходит это потому, что учитель заранее знает код программы. Он её не разрабатывает, а всего лишь печатает. В настоящей разработке никогда никакую - даже самую маленькую программу не пишут целиком сразу (разве что "Hello, world!"). Этот принцип мне видится одним из самых важных, и вместе с тем - одним из самых забываемых учителями.
Написание программы всегда разбивается на "атомарные" этапы.
Возьмём в качестве примера задание №8 из демоверсии 24 года
Сколько существует восьмеричных пятизначных чисел, не содержащих
в своей записи цифру 1, в которых все цифры различны и никакие две
чётные или две нечётные цифры не стоят рядом?
Первым этапом может быть программа, которая просто выводит на экран восьмеричные числа. Вообще, для перебора чисел в n-ричной системе счисления существуют два популярных алгоритма: перевод чисел в целевую систему или непосредственный перебор сразу в целевой системе. Реализация каждого из них сама по себе интересная задача. Я выбрал бы первый. (Здесь и далее я буду приводить код на Python 3):
Отладить этот небольшой фрагмент не составит труда. Далее можно сделать более удобным вывод, который бы соответствовал привычным представлениям о записи чисел:
Сделать вывод всех пятизначных восьмеричных чисел с перебором в цикле:
И, наконец, сделать ограничения на вывод.
Ограничения тоже лучше вводить по одному. Сначала первое условие "не содержащих в своей записи цифру 1", потом остальные.
Включить в код программы прочие условия, а так же счётчик чисел предлагаю самостоятельно.
Ещё раз напоминаю: в серьёзных IT-компаниях, в крупных проектах так поступают не только зелёные "джуны", но и ведущие программисты с полувековым опытом. И на то есть очень веские причины: чем меньше изменение, тем проще не наделать ошибок, а если они просочились - отыскать и исправить.
Не обязательно доводить программу до совершенства
Это тоже один из принципов "взрослых" программистов. Программа должна выполнять свою задачу. На ЕГЭ - это выдача ответа в человеко-читаемом виде за разумный срок. Но совсем не обязательно, чтобы этот человеко-читаемый вид был финальным - тем самым, который можно будет скопировать и вставить в ответы.
Хотя, если мы посмотрим на примеры листингов, которые предлагают нам учителя, репетиторы да и просто сайты по подготовке - мы увидим, что в конце всегда есть print(otvet). Это хорошо, но часто так оказывается, что какой-то из шагов куда проще выполнить вручную, чем запрограммировать.
И если на каком-то этапе разработки программа выводит то, из чего очень легко "прочитать" ответ, на этом нужно заканчивать. Не стоит тратить время на лишний "лоск".
Например, сумму десятичных цифр, которые встречаются в строке "AB5X1F0" куда проще вычислить "глазами", чем написать парсер на питоне. 5 + 1 + 0 = 6.
Именно поэтому в предыдущем пункте я остановился на выводе массива цифр [1, 7, 6, 0, 7], а не выводе "числа" 17607. Это не нужно. Прочитать можно и так, а с массивом проще работать.
Хорошо продуманная программа пишется и выполняется куда быстрее
Проще пояснить на примере. В задаче, которую я взял, условий на числа довольно много. Всего 5 ограничений:
- числа пятизначные,
- нет цифры "1",
- цифры различные,
- нет чётных цифр подряд,
- нет нечётных цифр подряд.
В своём коде я организовал перебор и одно из условий (один раз в цикле есть "if"). В финальной программе получилось бы 5 проверок. Но. Я немного подумал заранее (об этом я сразу не написал, пишу сейчас), и организовал перебор таким образом, чтобы автоматически учитывать первое условие "числа пятизначные". Перебор ведётся с 4096 (10000_8) - первое пятизначное число в восьмеричной системе до 32768-1 (77777_8) - последнее пятизначное число в восьмеричной системе.
Кажется, до этого надо ещё догадаться. Но таких "автоматически выполняемых" условий не так уж и много. Кроме "длины" числа, в ЕГЭ это может быть делимость. Если бы в условии было "и делится на 2024 без остатка", то тоже можно было бы организовать перебор таким образом, чтобы и это условие выполнялось автоматически. Достаточно просто перебирать числа от 6072
(13670_8) - первое пятизначное восьмеричное число, которое делится на 2024 - с шагом 2024. Таким образом, количество перебираемых чисел уменьшается в 2024 раза - только те, которые делятся на 2024 - и проверка на делимость будет проходить "автоматически".
Итог - всего заменой границ перебора мы уменьшаем размер кода и, соответственно, сложность поиска ошибки.
Может показаться, что это ловля блох, но в крупных проектах, где каждая итерация цикла - драгоценные наносекунды (которые складываются в миллисекунды, секунды, минуты и даже часы процессорного времени), такой подход просто жизненно необходим!
Пользуйтесь всем инструментарием, который есть у вас под рукой
Компьютер - очень мощная система, которая умеет почти всё. На ЕГЭ даётся максимально широкий инструментарий (локальный, разумеется), на который только способны школьные машинки. Калькуляторы с переводами между системами счисления, вычислительные таблицы (Excel), СУБД (Accsess), разнообразные языки программирования (python, c/c++) с IDE для них. В конце концов, бумага и ручка!
Что касается программирования, то современные IDE - интегрированные среды разработки - спроектированы так, чтобы максимально облегчить труд программиста и минимизировать время на работу. Для этого используются подсказки кода, отладчики, справочные материалы и многое другое.
- Если в visualStudio написать "for" и нажать кнопку "Tab", среда сама создаст типовую конструкцию цикла (работает с большим количеством типовых конструкций).
- Если в любом месте кода нажать ctrl+"/", то почти все известные мне среды закомментируют ("выключат") текущую строку.
- Tab или Shift+Tab меняют отступы (что актуально для пайтона).
- А в среде PascalABC есть очень подробная справка (документация), которую никто не запрещает открывать на экзамене.
Пользоваться можно всем этим без ограничений. Не нужно упираться в один несчастный пайтон в блокноте с отладкой из командной строки. Да, все задания ЕГЭ можно решить с помощью программы на пайтоне. Все. Это достаточно универсальный язык.
И если какие-то прямо заточены под пайтон (№12 и №25), то иные удобнее решать на чистом СИ (№5), а некоторые вообще проще решать на бумаге (№1, №4 и пр.) или в экселе (№26).
Но самое важное, что для многих заданий удобно использовать несколько инструментов одновременно! Это позволит сэкономить кучу времени. Тот же эксель на борту имеет прекрасный редактор макросов на языке VBA - VisualBasic for Application. Если список из файла для 17 задачи поместить в эксель и отсортировать его там, по нужной колонке, вычислить промежуточные значения, то их обработка в пайтоне не потребует много труда.
Может показаться, что труъ-программисты способны работать в блокноте и командной строке. Но в серьёзных крупных проектах используется огромное количество вспомогательных инструментов - от текстовых редакторов до систем генерации кода (да-да, программисты уже десятилетия используют программы, которые за людей пишут программы)
Как НЕ писать программы к заданиям ЕГЭ
Не писать весь код сразу
Очень распространённая ошибка у экзаменуемых - это попытка написать всю программу сразу (обычно по памяти). Категорически нельзя (если вы не списываете с листа, не понимая, что там написано). Любая малейшая ошибка вроде неправильных границ (не от 4096 до 32768, а от 4096 до 32769) может привести к тому, что программа отработает, выдаст ответ похожий на истину, но неправильный. Это самый паршивый вариант, потому что ошибки синтаксиса, ошибки компиляции или времени выполнения вы увидите, а эту - нет. И даже ошибки времени выполнения отлавливать будет тяжело в большой программе. Программист на ЕГЭ должен быть уверен в каждой строке своей программы.
Не использовать тесты, тестовые запуски
Каждая программа обязательно должна проходить тестирование. В ЕГЭ к каждой задаче обязательно предлагается набор тестовых данных. Но не нужно ограничиваться только ими. Придумывайте свои тесты. Этому можно научиться, просто старайтесь "сломать" свою же программу "плохими" данными. Ищите слабые места. Договаривайтесь с друзьями. Этот опыт будет полезен на экзамене.
Будет большой ошибкой первый рабочий запуск программы считать конечным.