Приветствую вас, друзья. Сегодня хотелось бы разобрать задачу 12 из ЕГЭ по информатике. В данной заметке мы подумаем какие можно использовать лайфхаки для решения таких задач.
Задача
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
1. заменить (v, w)
2. нашлось (v)
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (222)
заменить (222, 1)
заменить (111, 2)
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой программы к строке вида 1…12…2 (2019 единиц и 2050 двоек) ?
Решение:
ЕГЭ по информатике 2021 будет проходить теперь в компьютерной форме. Но это не значит, что все задания нужно решать только на компьютере! Часть заданий сохранилась с прошлых лет, и их придется решать «вручную». На экзамене можно будет использовать текстовый редактор, редактор электронных таблиц и среды для программирования, а это значит, что вычисления также можно будет выполнять на компьютере.
Рассмотрим два случая: аналитическое решение и компьютерное моделирование. Иногда бывает сложно решить задачу аналитически и легче замоделировать, иногда писать код дольше по времени, чем разобрать задачу на черновике.
Аналитическое решение
Для того, чтобы понять что происходит со строкой, понадобится расписать несколько итераций алгоритма. После того как мы это сделаем, можно внимательно посмотреть и увидеть, что структура строки, её топология повторяется через некоторое постоянное количество инструкций. Назовем это период T.
В нашей задаче может возникнуть соблазн разделить строку на две части (одна из единиц, другая из двоек) и исследовать отдельно. Этого делать не стоит. В конце вы увидите, что эти части взаимосвязаны.
Команда заменить() заменяет только первое вхождение подстроки.
Далее распишем первые 8 итераций цикла для понимания происходящего:
После 1-го прохода цикла строка будет выглядеть так:
2[2017 - 1][2047 - 2]
Через 1-й период строка будет выглядеть так:
2[2011 - 1][2041 - 2]
Через 2-й период строка будет выглядеть так:
2[2005 - 1][2035 - 2]
Можно заметить, что количество единиц в левой части строки уменьшается на 6, количество двоек в правой части строки также уменьшается на 6. А в текущей строке количество двоек на 30 больше количества единиц.
С учетом сохранения структуры, а также того, что 2017 div 6 = 336 и 2017 mod 6 = 1, мы можем найти вид строки после 336 периодов из итераций цикла. Строка будет выглядеть так:
2[1 - 1][2 - 31]
или в реальном виде: 212222222222222222222222222222222
(одна двойка, единица и тридцать одна двойка)
Далее эта строка уже легко вручную прогоняется через наш алгоритм, и после трех итераций, когда остаются одни двойки в количестве 27 штук, становится довольно очевидно, что алгоритм добивает их до строки, состоящей из одной единички - 1. Посмотрим как это выглядит по шагам:
Ответ: 1 - конечная строка.
Для некоторых такой алгоритм может показаться сложным, хотя мы и расписали всё по маленьким шагам. Поэтому проверить своё решение можно с помощью модели. Понадобится любой язык программирования.
Компьютерное моделирование
Программу можно написать разными способами. Предлагаю одно из решений. Из особенностей алгоритмы имеются две вспомогательные функции. Одна repl() - заменяет только первое вхождение искомой подстроки (как это и подразумевается в заданиях такого типа). Вторая generate_string() - генерирует исходную строчку, которую не имеет смысла забивать руками в программу. В конце программа возвращает такой же ответ ( 1 ), как и в нашем аналитическом решении.
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Библиотека с книгами для физиков, математиков и программистов
Репетитор IT mentor в VK
Репетитор IT mentor в Instagram
Репетитор IT mentor в telegram