Разбираем задачу №14 в ЕГЭ по информатике.
Обратите внимание, здесь будет не только пример решения, но и разбор задания по существу.
Для примера я беру демоверсию 2020 года (актуальная на момент написания статьи) с сайта fipi.ru.
Прежде чем приступать к решению этого примера, посмотрим в спецификацию к демоверсии.
Обратите внимание: задание на умение исполнять алгоритм. Хоть само по себе исполнение алгоритма - простейшая задача, но уровень сложности этого задания повышенный, значит, сам процесс исполнения будет осложнён количественно (много действий и записей). На выполнение отводится целых 6 минут, значит, потребуется именно длительная кропотливая работа, вряд ли поддающаяся стандартной оптимизации.
Вот проверяемые элементы содержания и умения в 14м задании очень любопытны. Проверяется, сможем ли мы построить эквивалентную алгоритмическую модель. Именно это можно было бы назвать оптимизацией, но о каких-либо шаблонах речи не идёт. И всё же тут есть более или менее часто используемые ходы. Разберёмся.
Решение задания
В тексте задания сначала очень подробно описывается исполнитель и его система команд. Не стоит пренебрегать этой информацией, надеясь, что на экзамене будет точно такой же исполнитель, как и в демоверсии. Достаточно заменить слово "слева" на слово "справа", и результат меняется коренным образом.
На какие вещи стоит обращать внимание при чтении текста:
1. Описание команд. К этим описаниям следует подходить, как будто видите их впервые. Это не шутка, а именно важный момент, потому что очень часто я сталкивался с учениками, которые выполнив три задания одного типа, используют ту же оптимизацию в заданиях другого типа с похожей по внешнему виду записью.
2. Описание цикла и условия очень мало отличается от аналогичных для того же Паскаля или Бэйсика, и я сильно сомневаюсь, что на экзамене описание будет не таким, но бросить хотя бы один взгляд на них надо, чтобы убедиться, что тут нет подвоха. Если подвох не очевиден, и стоит вопрос: "подвох" или "не подвох", то выбирать "не подвох"
3. Сам алгоритм. Существует несколько модификаций алгоритма, который предлагают в этом задании, но запомнить их и отличия между ними просто нереально (а ещё сложнее - не перепутать в стрессовой ситуации), поэтому никогда нельзя выполнять свой привычный алгоритм, а только тот, который написан, даже если кажется, что это один и тот же.
О смысловом чтении
Первая и, наверное, единственная серьёзная проблема этого задания - смысловое чтение текста. В принципе, выполнить 14 задание (как и многие другие, кстати) можно не зная информатики от слова "совсем", умея лишь читать текст. К сожалению, именно этого умения в современной школе с их образцами решения не дают. Поэтому я подробнее разжую.
Давайте прочитаем текст, который даётся в задании.
Исполнитель Редактор получает на вход строку цифр и преобразовывает её
Означает, что мы пишем несколько цифр на бумажке, отдаём этому редактору, а он нам возвращает эту же бумажку, но с другими цифрами. И дальше описаны правила, по которым происходит изменения.
Правило 1. Если встречается команда "заменить ()" (к ней обязательно должны идти два набора цифр), то исполнитель ищет в строке на бумажке первую последовательность и заменяет её на вторую. Тут написано, что "первое слева вхождение", то есть, поиск идёт слева направо, и замена выполняется 1 раз. Второй раз уже не надо делать.
Правило 2. Если встречается команда "нашлось()" (к ней идёт 1 набор цифр), то на её месте пишется "ИСТИНА", если в строке есть хотя бы один раз такой набор, и "ЛОЖЬ", если такого набора вообще не оказалось.
К каждому правилу идёт пример - набор чисел, который дают исполнителю, команда в полной записи, результат работы этой команды - что вернёт исполнитель.
И есть два описания стандартных конструкций "ПОКА...КОНЕЦПОКА" и "ЕСЛИ...ТО...ИНАЧЕ...КОНЕЦЕСЛИ". В принципе, очень похоже на дословный перевод с BASIC с его "WHILE...WEND", и "IF...THEN...ELSE...END IF". Ещё раз, конструкции - стандартные, но тем не менее, их действие слегка поясняется. Вообще, можно надеяться, что выбравший информатику ученик способен выполнить простейший цикл с предусловием и условный оператор.
Исполнение алгоритма
Я уже писал, что исполнять алгоритм надо честно и "в лоб", как в задании №8. И если выполняя предыдущие задания на алгоритмы, мы вполне укладываемся в лист А4 и отведённое на задание время, то для выполнения этого алгоритма придётся повозиться и много понаписать. Что я и рекомендую сделать. 6 минут - это достаточно для того, чтобы прочитать задание, записать входную строку карандашом и выполнить алгоритм.
Входная строка для нашего алгоритма - 70 подряд идущих цифр 8. Примерно вот так:
8888888888888888888888888888888888888888888888888888888888888888888888
Запись не такая уж длинная, чтобы её нельзя было сделать на черновике. Проблема здесь в том, чтобы не просчитаться с количеством. Поэтому выполнять такое задание первый раз я рекомендую на листе в клеточку:
Записывать в две строки очень плохо, хотя другого выхода у нас нет. Предупреждаю, что без опыта писать сокращённые записи опасно:
Теперь мы берём стирательную резинку и начинаем честно выполнять алгоритм, памятуя о том, что у нас есть переход на другую строку.
Каким бы нудным это дело ни казалось, выполнить его надо честно, для того, чтобы понять, как работает алгоритм такого типа. Хотя бы один раз. А лучше 2-3. Уверяю, опытные программисты, которые решают сие задание "в уме", в своё время делали это вручную и не один раз.
По алгоритму сначала выполняется проверка вхождения четырёх двоек или четырёх восьмёрок в строку (условие цикла). У нас восьмёрок 70, поэтому условие выполняется.
А теперь условие. Смотрите, если в условии цикла не важно, в каком порядке искать (8888 вперёд 2222 или наоборот), то тут чётко указано: "ЕСЛИ нашлось (2222)" - сначала ищем 2222. У нас таких нет, поэтому мы левые четыре восьмёрки заменяем на 2 двойки, и получаем 68 цифр:
Возвращаемся в начало, снова проверяем вхождение. Прекрасно видно, что 2222 не входит, а 8888 входит, и цикл ещё раз выполняется. Результат - 66 цифр, первые 4 двойки, остальные - восьмёрки.
Здесь я опять должен предостеречь от частой ошибки. Мозг человека пытается оптимизировать нудную работу и часто тут подсказывает ошибочные ходы. Вместо честного третьего прохода, мозг (особенно запетерсоненный) уже находит закономерность и может подсказать, что следующие 2*N восьмёрок будут заменены на N двоек. Это не так. Во-первых, если в конце останется 88, то замены не произойдёт, хотя по "закономерности" две восьмёрки на одну двойку заменятся, и должно быть 35 двоек. Это не так. Не всегда так.
При третьем проходе, условие цикла выполняется, и выполняется условие оператора "ЕСЛИ...ТО...ИНАЧЕ". И замена будет происходить уже двоек:
После трёх проходов текст "просто" сократился. Дальнейшие действия, думаю, понятны? Орудуя карандашом и стирательной резинкой, заменяем левые 2222 на 88, а если оных нет, то 8888 на 22:
В конце остаётся "22". Ответ: 22
Об оптимизации
Конкретно это задание оптимизировать очень трудно, хотя и возможно. Если не знать приёмов оптимизации заранее, то на это можно потратить времени куда больше, чем на прямое выполнение. И всё же, тренируясь, выполняя такие задания полностью вручную, каждый может разработать свои собственные пути оптимизации. Они будут куда эффективнее, чем любые, предложенные извне. Важно помнить, что если ответ не сошёлся, надо не метод подгонять под ответ, а выполнять "в лоб". Только так можно будет увидеть ошибку.
Конечно, есть и стандартные пути. Что можно сделать:
1. В одном из вариантов алгоритма сначала заменяются исходные цифры, а уж потом - обновлённые (у нас наоборот). В таком разе можно сразу выполнить замену, посчитав, сколько цифр заменится и на сколько заменится. Полученная строка будет в 3-4 раза короче исходной, и дальнейшее решение "в лоб" даст очень быстрый и точный результат
2. При замене обновлённых цифр перед исходными, можно заменять "пачками". Например, в нашем случае, за три прохода цикла серия из восьми восьмёрок заменяется на две. "Исчезают" 6 штук. Но тут надо помнить, что ряд не бесконечен, и из 7ми восьмёрок 6 не уберётся.
Практика показывает, что десятка тренировочных заданий хватит для наработки достаточных навыков.
Другие варианты
Раньше в этом задании был исполнитель чертёжник. Распространённым было задание, в котором часть программы (числа) была опущена. Решение уравнением было невозможным, так как, во-первых, на три пропущенных числа имелось всего два критерия и одно требование минимальности. Во-вторых, система из двух уравнений даже линейных не всегда решается за 6 минут (а ещё надо составить). Там бы я тоже дал рекомендацию честно выполнять алгоритм (поначалу, забив на анализ) и, устанавливая все три числа подбором, рисовать картинки, как сделал бы это исполнитель. В целых числах с требованием минимальности подбор работает эффективнее.
Практическая значимость
О практической значимости чертёжника говорить бессмысленно: это пример числового программного управления (чпу), которое, похоже, уже завоевало мир. А вот такой редактор иногда вызывает вопросы. Подобным образом действуют регулярные выражения. Работая программистом, любой рано или поздно сталкивается с этим эльфийским языком и,в первую очередь, с попытками их составлять или читать. Особенно актуально для веб-приложений.
