Заметили ошибку ?
Выделите это место и нажмите Ctrl + Q

ЕГЭ по информатике - Задание 14 (Укрощение Робота)



Продолжаем подготовку к ЕГЭ по информатике, и сегодня тренируемся решать 14 задание.


14 задание из ЕГЭ по информатике проверят умение управлять исполнителями команд (Роботом, Машинкой, Корабликом, Редактором и т.д.).


Давайте посмотрим, как его решать.



Задача (Редактор)

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


А) заменить(v, w)

Эта команда заменяет в строке первое слева вхождение цепочки v на w. Например, выполнение команды заменить(222, 34) преобразует строку 77222277 в строку 7734277.


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


Б) нашлось(v)

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение "истина", в противном случае возвращает значение "ложь". Строка исполнителя при этом не изменяется.


Цикл

ПОКА условие
    последовательность команд
КОНЕЦ ПОКА

выполняется, пока условие истинно.


В конструкции

ЕСЛИ условие
    ТО команда1
    ИНАЧЕ команда2
КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).


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


НАЧАЛО
ПОКА нашлось(331) ИЛИ нашлось(166)
    ЕСЛИ нашлось(331)
        ТО заменить(331, 16)
        ИНАЧЕ заменить(166,31)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Решение:

В подобных задачах из ЕГЭ по информатике даются все те команды управления, которые присутствуют в большинстве языках программирования (циклы, условия).


На вход программе подаётся строка:


ЕГЭ по информатике - задание 14 (строка цифр)

Рассмотрим нашу программу более подробно.



ЕГЭ по информатике - задание 14 (строка цифр алгоритм)

Сформулируем словами алгоритм: Проверяем есть ли в строке подстрока 331 или 166. Пока есть та или иная подстрока (или обе вместе), работаем в цикле. Внутри цикла ищем подстроку 331. Если она есть, то заменяем 331 на 16, но если нет подстроки 331, а мы всё равно находимся в цикле, то значит есть подстрока 166. Мы её должны заменить на 31. И так будет происходить, пока хотя бы одна из подстрок 331 или 166 будут присутствовать в основной строке.


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

Пока есть сочетание 331, эта подстрока будет заменяться на 16. Т.е. каждые две цифры 3 заменяются на одну 6, а единица так и остаётся одной единицей.


Изначально было 90 троек. Они превратятся в 45 шестёрок.


ЕГЭ по информатике - задание 14 (преобразование строки 2)

После этого начнёт работать вторая ветка условия - ИНАЧЕ. И будет выполняться команда заменить(166,31).



ЕГЭ по информатике - задание 14 (преобразование строки 2)

На рисунке видно, что т.к. нету больше подстроки 331, то Редактор заменит 166 на 31. Во второй строчке так же нету подстроки 331, снова будет заменена подстрока 166 на 31. В третьей строке уже появляется 331, это значит, что условие пойдёт по основной ветке, а не по ветке ИНАЧЕ, следовательно, выполнится снова команда заменить(331, 16).


Мы пришли к ситуации, когда была строка, где первая стояла единица, а после неё шло 45 шестёрок. А после определённого преобразования снова идёт единица, а затем уже 42 шестёрки. Т.е. 3 шестёрки просто исчезли в результате преобразования. Если продолжит Редактор выполнять программу, то снова исчезнут 3 шестёрки и т.д.


Рассмотрим ситуацию когда останется 1 и последние три шестёрки.


ЕГЭ по информатике - задание 14 (строка цифр - финальное преобразование)

В результате останется строка 316, где нет ни 331, ни 166, значит, цикл завершит свою работу, а 316 будет ответом!


Ответ: 316

Разберём ещё один пример с исполнителем Редактором. Задачи со строками очень часто встречаются в последние время в 14 задании на реальном ЕГЭ по информатике.


Задача (ЕГЭ по информатике, 2020, Москва)

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


заменить(v, w)
нашлось(v)

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.


Дана программа для Редактора:


НАЧАЛО

    ПОКА нашлось(49) ИЛИ нашлось(97) ИЛИ нашлось(47)
        
        ЕСЛИ нашлось(47)
        ТО заменить(47, 74)
        КОНЕЦ ЕСЛИ

        ЕСЛИ нашлось(97)
        ТО заменить(97, 79)
        КОНЕЦ ЕСЛИ

        ЕСЛИ нашлось(49)
        ТО заменить(49, 94)
        КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

КОНЕЦ

На приведённой ниже программе поступает строка, содержащая 40 цифр 7, 40 цифр 9 и 50 цифр 4, расположенных в произвольном порядке. Запишите без разделителей символы, которые имеют порядковые номера 25, 71, 105 в получившийся строке.


Решение:

В этой задаче цикл будет работать пока хотя бы одно сочетание 49, 97, 47 встречается в строке. Внутри цикла идут три равноправных условия. Эти условия "отлавливают" три выше перечисленные сочетания цифр и меняют цифры местами.


Видим, что если стоит 7 (семёрка) с любой цифрой (кроме себя), то в результате работы программы, 7 (семёрка) всегда окажется слева:


97 -> 79
47 -> 74

Если стоят вместе 4 и 9, то слева всегда оказывается 9:


49 -> 94

Таким образом, после выполнения всей программы строка будет выглядеть:



ЕГЭ по информатике - задание 14 (строка после выполнения программы)


Пример, если бы каждая цифра встречалась 3 раза:


479449797
749494779
794497479
794974479
799744479
797944749
779947494
779974944
779799444
777999444

Здесь были преобразованы строки цифр по описанным выше правилам (Т.е. если встречается нужное сочетание цифр, они меняются местами). Каждая новая строчка - это новое прохождение цикла. За один проход цикла может меняться только один раз каждое сочетание цифр.


Тогда в нашей финальной строке на 25 месте будет цифра 7, на 71 месте 9, на 105 месте цифра 4.


Ответ: 794


Задача (Робот)

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, состоит из 8 команд. Четыре команды - это команды-приказы:


вверх вниз влево вправо

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх , вниз , влево , вправо .


Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:


сверху свободно снизу свободно слева свободносправа свободно

Цикл
   ПОКА условие
       последовательность команд
   КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
    ТО команда1
    ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно)

В конструкциях ПОКА и ЕСЛИ условие может содержать команды проверки, а также слова И, ИЛИ, НЕ, обозначающие логические операции.


Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится и программа прервётся.


Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)?


НАЧАЛО
  ПОКА снизу свободно ИЛИ справа свободно
    ПОКА справа свободно
        вправо
    КОНЕЦ ПОКА
    ЕСЛИ снизу свободнo
        ТО вниз
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
КОНЕЦ
ЕГЭ по информатике - задание 14 (Лабиринт, где живёт Робот)

Решение:

Проанализируем внимательно программу для Робота.


В программе есть главный цикл, внутри цикла проверяется сначала возможность двигаться вправо. Если есть такая возможность, робот будет двигаться до упора с помощью ещё одного цикла. Потом после того как больше нет возможности двигаться вправо, с помощью основного цикла и записанного условия будет перемещаться вниз, пока есть такая возможность.


Если нет возможности двигаться ни вправо, ни вниз, то Робот завершает программу.


Поняв этот алгоритм не сложно отметить те клетки, стартовав с которых, Робот остановится на клетке F6.


ЕГЭ по информатике - задание 14 (клетки лабиринта соответствуют требованию)

Ещё раз, Робот до упору будет двигаться вправо, потом до упору вниз, насколько это возможно. Вот алгоритм в двух словах.



Важно в этих задачах простыми словами сформулировать алгоритм, чтобы можно было проверять целые блоки лабиринта.


Количество клеток, удовлетворяющие условию будет 21.


Ответ: 21

14 Задание из ЕГЭ по информатике выглядит обычно объёмным, но на деле описываются обычные конструкции (Циклы и условия), которые есть в большинстве языках программирования.


Задача (Чертёжник)

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнить команду сместиться на(a, b), где a, b - целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b).


Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на(2, -3) переместит Чертёжника в точку (6, -1).


Цикл
ПОВТОРИ число РАЗ
последовательность команд
КОНЕЦ ПОВТОРИ

означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).


Чертёжнику был дан для исполнения следующий алгоритм (число повторений и величины смещения в первой из повторяемых команд неизвестны):

НАЧАЛО
сместиться на(8, -60)
  ПОВТОРИ ... РАЗ
    сместиться на(..., ...)
    сместиться на(4, -6)
  КОНЕЦ ПОВТОРИ
сместиться на(-35, -3)
КОНЕЦ

В результате выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшие число повторений могло быть указано в конструкции "ПОВТОРИ ... РАЗ" ?


Решение:

Эта задача похоже на задачу Кузнечик, которую рассматривали в 6 задании.


Напишем для переменной x уравнение.


8 + n * x + n * 4 - 35 = 0

Всё выражение приравниваем к нулю, т.к. Чертёжник возвращается в исходную точку, т.е. как ни ходил Чертёжник, он никуда в итоге не сдвинулся.


n - положительное целое число, количество повторений.


x - целое число, смещение по координате x.



n * x + n * 4 = 27

n * ( x + 4 ) = 27

Нужно подобрать x и n, чтобы равенство было верным.


Число n может быть 27, 9, 3, 1. Нам нужно выбрать число n, как можно больше.


Проверим число 27! Тогда выражение x + 4 = 1 => x = -3. Теперь нужно проверить это число для координаты y.


-60 + n * y - n * 6 - 3 = 0

27 * y - 27 * 6 = 63

27 * ( y - 6 ) = 63

Видим, что нельзя подобрать такое целое число для 27, чтобы при умножении получалось 63.


Проверим число 9! Тогда выражение x + 4 = 3 => x = -1. Теперь нужно проверить это число для координаты y.


-60 + n * y - n * 6 - 3 = 0

9 * y - 9 * 6 = 63

9 * ( y - 6 ) = 63

Видим, что можно подобрать такое целое число для 9, чтобы при умножении получалось 63. Это число 7. Значит, y - 6 = 7 => y = 13


Мы подобрали все нужные числа и нашли наибольшее число n=9.


Ответ: 9

Последняя на сегодня репетиционная задача 14 задания ЕГЭ по информатике.


Задача (Кораблик)

Исполнитель КОРАБЛИК «живет» в ограниченном прямоугольном водоеме-лабиринте, разделенном на клетки и изображенном на рисунке (вид сверху). Серые клетки — скалистые берега, светлые — свободное пространство, безопасное для передвижения КОРАБЛИКА. По краю водоема-лабиринта также находятся скалы с нанесенными на них номерами и буквами для удобства идентификации клеток.


ЕГЭ по информатике - задание 14 (Исполнитель Кораблик)


Система команд исполнителя КОРАБЛИК:


вверх, вниз, влево, вправо

При выполнении любой из этих команд КОРАБЛИК перемещается на одну клетку соответственно (по отношению к наблюдателю): вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится КОРАБЛИК (также по отношению к наблюдателю):


сверху свободно
снизу свободно
слева свободно
справа свободно

Цикл

ПОКА <условие> команда

выполняется, пока условие истинно, иначе происходит переход на следующую строку. При попытке передвижения на любую серую клетку КОРАБЛИК разбивается о скалы.


Сколько клеток приведенного лабиринта соответствуют требованию, что, стартовав в ней и выполнив предложенную ниже программу, КОРАБЛИК не разобьется?


 
НАЧАЛО
  ПОКА <сверху свободно> вверх
  ПОКА <слева свободно> влево
  вверх
  вправо
КОНЕЦ

Решение:

Кораблик разбивается нарвавшись на серую клетку.


Сформулируем в простом виде алгоритм программы: Сначала идём вверх до упора, потом влево до упора. Потом ещё один раз вверх и один раз вправо.


Последние две команды выполняются без какой-либо проверки, это и есть слабое место программы, где Кораблик может разбиться.


ЕГЭ по информатике - задание 14 (Исполнитель Кораблик, анализируем область)

На рисунке показано область, где ни одна клетка не подходит, т.к. Кораблик разобьётся в клетках отмеченные красным цветом.


ЕГЭ по информатике - задание 14 (Исполнитель Кораблик, анализируем область 2)

На этом рисунке жёлтым цветом отмечены клетки, которые подходят, и стартовав из этих клеток, Кораблик попадёт в одну из зелёных клеток, где выполнить последние команды вверх и вправо, Кораблик останется целым. Клетка С8 отмечена и жёлтым и зелёным цветом.


Остальные же клетки нам не подходят. Кораблик, стартовав с них, попадёт на одну из красных клеток, где он разобьётся, выполняя последние две команды вверх, влево. Клетка I5 окрашена и красным, и жёлтым цветом.


ЕГЭ по информатике - задание 14 (Исполнитель Кораблик, анализируем область 3)

Посчитаем жёлтые клетки. Всего получилось 17 клеток.


Ответ: 17

Успешной подготовки к ЕГЭ по информатике!






08-07-2020 в 20:44:57





Похожая статья:

ЕГЭ по информатике - Задание 2 (Мощнейший метод)

Сегодня разберём, как решать второе задание из ЕГЭ по информатике 202...

Категория: ЕГЭ  Подкатегория: -
Дата: 15-01-2018 в 16:47:34 0



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:


Последние
видео:



ЕГЭ по информатике - Задание 18
ЕГЭ по информатике - Задание 17





Давайте
дружить!


Группа Вконтакте Code-Enjoy

Твиттер Александра Калужского

YouTube канал Code-Enjoy