Конец ПОКА. Где угол – это клетка, в которой есть стенки снизу и справа

где угол – это клетка, в которой есть стенки снизу и справа

4) за каждый шаг внешнего цикла Робот проходит путь в виде «сапога», двигаясь сначала вправо до упора, а затем – вниз до упора:

клетка, выделенная красным фоном особая – в ней заканчивается один шаг внешнего цикла и начинается следующий:

а) Робот может попасть в эту клетку, двигаясь вниз из клетки, где справа – стенка

б) снизу есть стенка;

в) снизу стенка есть, справа – нет, поэтому будет выполнен еще один шаг внешнего цикла.

5) в клетку F6 (это угол, где Робот остановился), Робот мог придти за один шаг внешнего цикла (за один «сапог») только из отмеченных клеток:

6) теперь отметим красным фоном особые клетки, которые удовлетворяют условиям а-в пункта 4 (см. выше), их всего 2:

7) отметим все пути в форме «сапога», которые приводят в особые клетки:

8) больше особых клеток (см. пункт 4) нет; всего отмечено 24 клетки (считая конечную клетку F6)

9) таким образом, правильный ответ – 3.

Еще пример задания:

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

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

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

Сверху свободно снизу свободно

слева свободно справа свободно

Цикл ПОКА < условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение?

1) 1 2) 2 3) 3 4) 0

НАЧАЛО

ПОКА < снизу свободно> вниз

ПОКА < слева свободно> влево

ПОКА < сверху свободно> вверх

ПОКА < справа свободно> вправо

КОНЕЦ

Решение:

10) легко понять, что для того, чтобы исполнитель вернулся обратно в ту клетку, откуда он начал движения, четыре стенки должны быть расставлены так, чтобы он упирался в них сначала при движении вниз, затем – влево, вверх и, наконец, вправо:

на рисунке красная точка обозначает клетку, начав с которой РОБОТ вернется обратно;

11) кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода

12) обратим внимание, что возможны еще «вырожденные» варианты, вроде таких:

13) итак, мы выяснили, что нужно рассматривать лишь те клетки, где есть стенка справа; отметим на исходной карте клетки-кандидаты:

14) этих «подозрительных» клеток не так много, но можно еще сократить количество рассматриваемых вариантов: если РОБОТ начинает движение с любой клетки на вертикали F, он все равно приходит в клетку F4, которая удовлетворяет заданному условию, таким образом, одну клетку мы нашли, а остальные клетки вертикали F условию не удовлетворяют:

15) проверяем оставшиеся четыре клетки-кандидаты, но для каждой из них после выполнения алгоритма РОБОТ не приходит в ту клетку, откуда он стартовал:

		·
A	B	C	D	E	F

	·
A	B	C	D	E	F

				·
A	B	C	D	E	F

·
A	B	C	D	E	F

16) итак, условию удовлетворяет только одна клетка – F4

17) таким образом, правильный ответ – 1.

Еще пример задания:

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