Приветствую вас, друзья. Сегодня хотелось бы разобрать задачу 12 из ЕГЭ по информатике. В данной заметке мы подумаем какие можно использовать лайфхаки для решения таких задач.
Задача
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
1. заменить (v, w)
2. нашлось (v)
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (222)
заменить (222, 1)
заменить (111, 2)
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой программы к строке вида 1…12…2 (2019 единиц и 2050 двоек) ?
Информатика ЕГЭ 2016. Разбор 14 номера
Решение:
ЕГЭ по информатике 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 периодов из итераций цикла. Строка будет выглядеть так:
задача 14 егэ Редактор
2[1 — 1][2 — 31]
или в реальном виде: 212222222222222222222222222222222
(одна двойка, единица и тридцать одна двойка)
Далее эта строка уже легко вручную прогоняется через наш алгоритм, и после трех итераций, когда остаются одни двойки в количестве 27 штук, становится довольно очевидно, что алгоритм добивает их до строки, состоящей из одной единички — 1. Посмотрим как это выглядит по шагам:
Ответ: 1 — конечная строка.
Для некоторых такой алгоритм может показаться сложным, хотя мы и расписали всё по маленьким шагам. Поэтому проверить своё решение можно с помощью модели. Понадобится любой язык программирования.
Компьютерное моделирование
Программу можно написать разными способами. Предлагаю одно из решений. Из особенностей алгоритмы имеются две вспомогательные функции. Одна repl() — заменяет только первое вхождение искомой подстроки (как это и подразумевается в заданиях такого типа). Вторая generate_string() — генерирует исходную строчку, которую не имеет смысла забивать руками в программу.
В конце программа возвращает такой же ответ ( 1 ), как и в нашем аналитическом решении.
Моделирование 12 задачи из ЕГЭ по информатике
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Источник: dzen.ru
Е12.20 ниже программы к строке вида 1…12…2 (46 единиц и 46 двоек)?
ниже программы к строке вида 1…12…2 (46 единиц и 46 двоек)?
Исполнитель Редактор получает на вход строку цифр и преобразует её.
Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить (111, 27)
преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Источник: informatikaexpert.ru
Какая строчка получится в результате применения приведенной ниже программы к строке
Литература:
1. Информатика: учебник для 10 класса / К.Ю. Поляков, Е.А. Еремина — М.: БИНОМ.Лаборатория знаний, 2021. — 352 с.
К уроку:
Задача №1.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 85 идущих подряд цифр 9? В ответе запишите полученную строку.
ПОКА нашлось (666) ИЛИ нашлось (999)
ЕСЛИ нашлось (666)
ТО заменить (666, 9)
ИНАЧЕ заменить (999, 6)
Задача №2.
Сколько нулей будет в преобразованной строке после выполнения следующего алгоритма для строки, состоящей из 1 и идущих за ней 33 нулей?
ПОКА нашлось(1) или нашлось(100)
ТО заменить(100, 0001)
ИНАЧЕ заменить(1, 00)
Чтобы подсчитать количество вхождений конкретного символа в строке, воспользуйтесь командой count()
Пример записи: S.count(‘A’) — вернёт количество символов «A» в строке S.
Источник: www.veche.site