6110 подписчиков

Разбор 12 задания из ЕГЭ по информатике

27 июня 202227 июн 2022

859

5 мин

Оглавление

Задача [ Тип 12 ]
Решение:
Способ 1

Приветствую, друзья! Сегодня заметка по информатике. Будет полезна тем учащимся, кто на данный момент испытывает трудности в решении экзамена по информатике, но очень хочет разобраться в этом. Я постараюсь максимально подробно Вам помочь в этом :)

А ещё я буду очень рад, есил Вы подпишитесь на мой канал в telegram: Репетитор IT mentor

Задача [ Тип 12 ]

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w) — Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

заменить (555, 63) — преобразует строку 12555550 в строку 1263550. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б) нашлось (v) — Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 1000 идущих подряд цифр 9? В ответе запишите полученную строку.

НАЧАЛО
ПОКА нашлось (999) ИЛИ нашлось (888)
ЕСЛИ нашлось (888)
ТО заменить (888, 9)
ИНАЧЕ заменить (999, 8)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На этом моменте попробуйте остановиться, взять в руки черновик и решить задачку самостоятельно... А после гифки будет решение :)

Итак, приступаем. Еще раз приведем код (нижние подчервкивания только для лучшей наглядности вложенности):

НАЧАЛО
__ПОКА нашлось (999) ИЛИ нашлось (888)
____ЕСЛИ нашлось (888)
________ТО заменить (888, 9)
____ИНАЧЕ заменить (999, 8)
____КОНЕЦ ЕСЛИ
__КОНЕЦ ПОКА
КОНЕЦ

Решение:

Задача по номером 12 является одной из самых запутанных в первой части экзамена. Очень часто учащиеся не знают как к ней можно подойти. Я покажу вам два способа.

Способ 1

Первый способ. Здесь решим задачу аналитически. Этот случай подойдет для той ситуации, когда у нас нет возможности написать программу для решения этой задачи (или с программированием у нас пока не очень хорошо).

Нужно рассмотреть несколько итераций, чтоб выделить некоторый период, состоящий из 5 итераций работы цикла while, после которых строка превращается в такую же строку с точки зрения топологии (состояющую из всех девяток), но более короткую. То есть фишка этого задания в том, что после нескольких итераций цикла, расписанных на черновике, мы получим строчку, которая опять будет равномерно состоять из исходных цифр (в нашем случае девяток). После того как период найден, мы можем убрать целое количество периодов. Но делать это лучше не до конца.

Мы видим, что за один период у нас идет уменьшение на 1000 — 992 = 8 девяток. Исходное число девяток кратно 8, то есть, на первый взгляд может сложиться впечатление, что мы имеем право убрать все девятки и получить пустую строку, так как 1000 : 8 = 125 (целое число).

Однако, это неправильно. Дело в том, что алгоритм убирает только по три девятки или по три восьмерки (то есть пачками с нечетным количеством), что должно нам дать подсказку — нельзя идти до конца. Нужно убрать не 125 периодов, а 124 периода. Тогда в остатке у нас останется 8. То есть строка будет состоять из 8 девяток. А далее всё делается в ручную в пару шагов. И мы получаем ответ: S = 8899. Задача решена.

Способ 2

Второй способ будет программный. Данная программа некоторого робота-исполнителя легко реализуется на языке, где просто можно работать со строками. Для примера возьмем язык Python. Для того, чтобы написать рабочий метод, нам понадобится цикл while, условная конструкция if-else и пара методов для работы со строками.

str.find(sub[, start[, end]]) — возвращает индекс первого совпадения подстроки sub в строке str, где подстрока или символ sub находится в пределах среза str[start:end]. Другими словами, находит и возвращает индекс первого совпадения подстроки в строке str.
Параметры:
sub — str, подстрока или символ;
start — int, индекс строки str для начала поиска;
end — int, индекс строки str для конца поиска.
Возвращаемое значение:
int — индекс первого совпадения.

str.replace(old, new[, count]) — вернет копию строки, в которой все вхождения подстроки old заменены на подстроку new. Если указан необязательный аргумент count, заменяются только первые вхождения count. Примечание. Производить поиск и замену подстроки/символа в строке можно так же при помощи регулярных выражений, используя функцию re.sub().
Параметры:
old — str, подстрока или символ который меняем
new — str, подстрока или символ на который меняем
count — int, сколько раз меняем
Возвращаемое значение:
измененная копия строки.

Хотите еще подобную задачку ? Без проблем, давайте рассмотрим.

Разбор задания 14 (ЕГЭ по информатике)

Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 101 единиц?

НАЧАЛО
ПОКА нашлось (1111)
заменить (1111, 22)
заменить (222, 1)
КОНЕЦ ПОКА
КОНЕЦ

Решение:

Расписав несколько итераций данного цикла, видно, что блок из 3 итераций убирает 101 - 91 = 10 единиц из строки. Но не всё так просто. Проблема задачи в том, что не все инструкции внутри цикла выполняются. Поэтому в этой задачи нужно подстраховаться и остановиться раньше, чем получим остаток от целочисленного деления 101 mod 10 = 1. То есть неверно будет оставить в ответе "1", как может показаться на первый взгляд. Cвязано это с тем, что все инструкции выполняются до тех пор, пока находим 4 единицы "1111". Поэтому возьмем 9 блоков по 3 итерации. После повторения 9 раз таких блоков по 3 итерации, из нашей строки уйдет 9 * 10 = 90 единиц. Останется строка, которая состоит из 101 - 90 = 21 единицы. Её уже довольно быстро можно исследовать аналитически. Смотри рисунок.