Сегодня я хочу разобрать пример 14 задания из ЕГЭ по информатике. В общем случае это задание на выполнение алгоритма для конкретного исполнителя. Иногда, увидев имя Исполнителя алгоритма, можно подумать, что задания пишут не лишенные чувства юмора специалисты.
Вообще суть задания на умение анализировать алгоритм, находить закономерность и, естественно, использовать математические операции для нахождения ответа, потому как, если просто выполнять по-ша-го-во алгоритм, на это уйдет уйма времени.
Рассмотрим такой пример:
ДОНТВОРРИ, ну что тут еще скажешь. К чему лишнее беспокойство? Решаем и не киснем.
Во-первых, разберемся, что умеет делать исполнитель. Если исполнитель "видит" четыре подряд идущие единицы, он заменяет их на одну 5. Если исполнитель "видит" три подряд идущие пятерки, он заменяет их одной 1.
Именно в таком порядке, сначала он "ищет" единицы потом - пятерки.
Теперь перехожу к данной программе. Есть у нас строка из 2020 "пятерок" (ну так, совсем немного, эти бы "пятерки" да по всем предметам в классный журнал).
Естественно, в начале выполнения никаких единиц нет. Поэтому исполнитель находит "555" и заменяет их на 1. Получаем строку из одной 1 и уже из 2020-3 = 2017 пятерок: 155...555.
Затем у нас еще нет "1111", а только одна 1, и исполнитель находит еще "555" и заменяет их на одну 1. Мы получаем строку из двух 1 и 2017-3=2014 пятерок: 1155...55.
Итак, до тех пор, пока у нас не окажется в начале строки "1111". И тогда у нас получится строка, состоящая из четырех 1 и 2014-3-3=2008 пятерок: 1111555...55.
Конечно, мы могли сразу получить эту строку. Как? Каждую единицу мы получаем "взамен" трех пятерок, поэтому, чтобы получить четыре 1, нам надо избавиться от 4*3 = 12 пятерок. Получаем тот же результат: 1111 и 2020-12 = 2008 пятерок.
Что происходит далее, по программе 1111 заменяются на одну 5. И мы опять получаем строку, содержащую только пятерки. Их у нас становится 2009 штук.
И начинаем заново "добывать" единицы, по одной штуке за каждые три пятерки.
Конечно, мы не будем шаг за шагом выполнять этот алгоритм. На это, повторюсь, уйдет много времени. А мы ведь с вами знаем математику.
Получается, что алгоритм представляет собой цикл, при каждом витке которого в строке сначала заменяются 12 пятерок на четыре 1, а затем эти четыре 1 заменяются на одну 5.
В начале каждого витка цикла мы имеем строку из n пятерок, в конце витка строку из n-11 пятерок (надеюсь, понятно, что сначала мы "променяли" 12 пятерок на четыре 1, а затем одну "вернули" за те же самые четыре 1, получается теряем мы на каждом витке 11 пятерок)
Ну вот. Всего в начале выполнения программы у нас 2020 пятерок, посчитаем, сколько одинаковых витков, при которых мы потеряем по 11 пятерок, получится.
2020/11=183,6..
После запятой нас цифры не интересуют. Округляем в меньшую сторону, так как нам надо количество полных витков.
То есть выше описанная процедура у нас повторится 183 раза. За 183 повторения мы потеряем 183*11=2013 пятерок.
И у нас останется 2020-2013 = 7 пятерок, т.е. будем иметь строку:
5555555
А дальше так же по программе: каждые три пятерки заменяем на одну 1:
115.
Все. Это и есть ответ.
Если остались вопросы, пишите в комментариях. Обязательно отвечу. Если нужно разобрать конкретный пример, также - в комментарии.
Читайте также: Задание 1, Задание 2, Задание 3, Задание 4, Задание 5, Задание 6, Задание 7, Задание 8, Задание 9, Задание 10, Задание 11, Задание 12, Задание 13, Задание 15, Задание 18, Задание 19, Задание 22, Задание 16, Задание 17, Задание 20, Задание 21, Задание 23, Задание 24, Задание 25, Задание 26, Задание 27.