Разбор задачи A18 (демо ЕГЭ 2010)
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
| вверх | вниз | влево | вправо |
При выполнении этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.
Четыре команды служат для проверки истинности условия отсутствия соответствующей стены у той клетки, где находится РОБОТ:
| сверху свободно | снизу свободно | слева свободно | справа свободно |
Цикл ПОКА < условие > команда выполняется, пока условие истинно, иначе происходит переход на следующую строку.
Если РОБОТ начнет движение в сторону стены, то он разрушится и выполнение программы прервется.
Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ уцелеет и остановится в той же клетке, с которой он начал движение?
НАЧАЛО
ПОКА < сверху свободно > вправо
ПОКА < справа свободно > вниз
ПОКА < снизу свободно > влево
ПОКА < слева свободно > вверх
КОНЕЦ
- 1
- 2
- 3
- 4
Сначала построим траекторию движения робота. Она изображена на рисунке:
Черной точкой обозначена клетка, из которой начнет движение робот. Из рисунка видно,что клетка, из которой должен начать движение робот, должна быть слева ограничена барьером. Стена, окружающая лабиринт, также является барьером. Если это условие не будет выполняться, то робот пройдет дальше и не остановится в клетке, с которой начал движение. Отметим клетки,ограниченные слева барьером. Это и будут потенциальные клетки,которые нам нужно найти.
Теперь проверим каждую из этих точек. Для каждой точки нарисуем траекторию движения робота:
Там, где стрелочка касается барьера или стены лабиринта, произошло разрушение робота. Только одна клетка удовлетворяют требованиям задачи: робот не разрушится и вернется в ту же клетку,с которой начал движение. На рисунке она обозначена розовым большим овалом.