2,7K subscribers

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

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

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

А ещё я буду очень рад, есил Вы подпишитесь на мой канал в 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)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

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

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

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

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

Решение:

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

Способ 1

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

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

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

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

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

Способ 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, сколько раз меняем

Возвращаемое значение:
измененная копия строки.

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

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

Разбор задания 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 единицы. Её уже довольно быстро можно исследовать аналитически. Смотри рисунок.

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

Два года назад я уже разбирал эту задачку в своем блоге в VK (КЛИК)

А ещё одну сложную задачку такого же типа я разбирал в статье на Дзен (на данном канале). Вот формулировка этой задачи:

Задача

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

Какая строка получится в результате применения приведённой программы к строке вида 1…12…2 (2019 единиц и 2050 двоек) ?

ЧИТАТЬ РЕШЕНИЕ ДАННОЙ ЗАДАЧИ

Понравилась статья ? Поставьте лайк, подпишитесь на канал! Вам не сложно, а мне очень приятно :)

Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Библиотека с книгами для физиков, математиков и программистов
Репетитор IT mentor в telegram