Раздел A • Категория A13 (демонстрационный вариант-2012)

 
 
 

Условие задачи

Дано:
система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:

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

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

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

Цикл
    ПОКА < условие > команда
выполняется, пока условие истинно, иначе происходит переход на следующую строку. Если РОБОТ начнёт движение в сторону стены, то он разрушится и программа прервётся.

 

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

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

Варианты ответа:

1) 1          2) 3          3) 5          4) 7

 

Теоретические сведения

Алгоритм – последовательность понятных для исполнителя действий, приводящих к решению поставленной задачи за разумное время.

Фундаментальные свойства алгоритма:

  • дискретность;

  • детерминированность;

  • массовость;

  • понятность;

  • результативность.

Исполнитель алгоритма – автомат (как правило, рассматривается персональный компьютер) или человек, способный выполнять определенный набор действий. Как правило, в роли конкретного исполнителя выступают следующие существа: Робот, Инвентор, Делитель, Сумматор, Дробитель, Утроитель, Вычитатель, Модулятор, Калькулятор и т. п.

Базовые характеристики исполнителя:

  • среда выполнения;

  • система элементарных действий;

  • система отказов (или обработка исключительных ситуаций).

 

Решение

Хочу отметить, что алгоритм движения Робота заданный по условию является усложненным вариантом, так как зачастую команды имеют вид:
ПОКА < справа свободно > вправо
или
ПОКА < снизу свободно > вниз

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

 

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

Я хочу детально показать, как производится анализ движения траектории Робота на конкретной ячейке.

 

Стартовая позиция:

 

Проверяем условие < справа свободно >? - да, следовательно, Робот движется вниз:

 

Проверяем условие < справа свободно >? - да, следовательно, Робот движется вниз:

 

Проверяем условие < справа свободно >? - да, следовательно, Робот движется вниз:

 

Проверяем условие < справа свободно >? - нет, следовательно, переходим к анализу условия < снизу свободно >.
Проверяем условие < снизу свободно >? - да, следовательно, Робот движется влево.

 

Проверяем условие < снизу свободно >? - да, следовательно, Робот движется влево.

 

Проверяем условие < снизу свободно >? - нет, следовательно, переходим к анализу условия < слева свободно >.
Проверяем условие < слева свободно >? -да, следовательно, Робот движется вверх.

 

Проверяем условие < слева свободно >? -да, следовательно, Робот движется вверх.

 

Проверяем условие < слева свободно >? -да, следовательно, Робот движется вверх.

 

Проверяем условие < слева свободно >? - нет, следовательно, переходим к анализу условия < сверху свободно >.
Проверяем условие < сверху свободно >? - да, следовательно, Робот движется вправо.

 

Проверяем условие < сверху свободно >? - да, следовательно, Робот движется вправо.

 

Проверяем условие < сверху свободно >? - нет, следовательно, нужно переходить к следующей команде, но цикл закончен. То есть Робот завершил свое движение.

Видно, что Робот остановился в той же клетке, из которой начал свой путь.

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

 

Сейчас я продемонстрирую те клетки, удовлетворяющие граничным условиям:

В итоге, количество совпадающих клеток равно 3.

 

Вывод:

три клетки лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ уцелеет и остановится в той же клетке, с которой он начал движение.
Среди предложенных вариантов ответа, вариант под номер 2 имеет абсолютно идентичное значение.

Ответ:

2

 
Рейтинг:
 
Проголосовало: 0
Количество просмотров: 1005
 
 
 

Раздел A • Категория A13 (демонстрационный вариант-2012)

 

Комментарии

Для комментирования или зарегистрируйтесь
 
 
© 2011-2019 ООО "СтадиМен". Все права сохранены.
Перепечатка и использование материалов с данного сайта, разрешена только по согласию с владельцем.
Владелец оставляет за собой право воспользоваться 146 статьей УК РФ при нарушении авторских и смежных прав.
 
 
 
 
Авторизация на сайте
 
 
 
Обнаружили
ошибку на сайте?