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