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