Примеры решения задач с Роботом Задача 1
Среда обитания Робота - прямоугольный лабиринт на клетчатой плоскости, где есть внутренние перегородки:
Система команд Робота:
Четыре команды движения: вверх вниз влево вправо. При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.
Четыре команды проверки условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: сверху свободно; снизу свободно; слева свободно; справа свободно.
Цикл ПОКА <условие> выполняется, пока условие истинно, иначе происходит переход на следующую строку.
Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ уцелеет (не врежется в стену) и остановится в той же клетке, с которой он начал движение? (0,1, 2, 3)
-
НАЧАЛО ПОКА <снизу свободно> вниз ПОКА <слева свободно> влево ПОКА <сверху свободно> вверх ПОКА <справа свободно> вправо КОНЕЦ
Последняя команда "ПОКА < справа свободно > вправо". Следовательно, для того, чтобы Робот остановился в той же клетке, с которой он начал движение, необходимо, чтобы у этой клетки была стенка справа. Этому условию удовлетворяют все клетки правой стенки Е1–Е6 и еще пять клеток А5, Б4, В2, Г3, Д1.
А5 отпадает, т.к. влево двигаться некуда из-за стены.
В2, Е4 отпадают, т.к. вниз идти некуда.
Г3 отпадает, т.к. вниз идти некуда.
Е1 отпадает, т.к., двигаясь вправо Робот упрется в левую стенку Е1.
Кандидатами остаются Е2, Е3, Е5, Е6, Б4, Д1.
Предпоследняя команда "ПОКА <сверху свободно> вверх". Значит, перед тем, как двигаться вправо, Робот должен упереться в стенку сверху и оказаться на той же строке, откуда начал движение.
Е2, Е3 отпадают, т.к. нет ограничения сверху ни в одной клетке этой строки.
Е5 отпадает, т.к. нет ограничения сверху ни в одной клетке этой строки, кроме исходной клетки Е5.
Б4 отпадает, т.к. по завершении движения вверх Робот оказывается в ячейке А3, т.е. на третьей строке, а не на четвертой, с которой начал движение.
Ответ – всем условиям удовлетворяет только одна клетка Д1.
Задача 2
Среда обитания Робота - прямоугольный лабиринт на клетчатой плоскости, где есть внутренние перегородки:
Система команд Робота:
Четыре команды движения: вверх вниз влево вправо. При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.
Четыре команды проверки условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: сверху свободно; снизу свободно; слева свободно; справа свободно.
Цикл ПОКА <условие> выполняется, пока условие истинно, иначе происходит переход на следующую строку.
Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение? (1, 2, 3, 4)
-
НАЧАЛО
ПОКА <слева свободно> вверх
ПОКА <сверху свободно> вправо
ПОКА <справа свободно> вниз
ПОКА <снизу свободно> влево
КОНЕЦ
6
5
4
3
2
1
A
B
C
D
E
F
Особенность этой задач в том, что РОБОТ проверяет стенку в одном направлении, а движется в другом.
В четвертом цикле ПОКА <снизу свободно> влево РОБОТ останавливается в клетке, где есть стена снизу. Этому условию удовлетворяют клетки A1, B1, C1, D1, E1, F1, B5, C2, E6, F3. Значит, именно эти клетки являются кандидатами.
При движении из клеток B5, D1, E1, Е6, F1 и F3 РОБОТ врежется в верхнюю стенку, потому что слева стены нет и условие «слева свободно» всегда истинно. Кандидатами остаются клетки A1, B1, C1, С2, E6.
Начав движение с клетки A1, C1 или C2, РОБОТ также врезается в стенку и разрушается. Кандидатами остаются B1, E6, F3.
Из этих кандидатов только В1 удовлетворяет условиям задачи, т.к. только путь, начатый в клетке B1, приводит РОБОТА обратно в точку старта:
|
|
|
|
|
|
6 |
|
|
|
|
|
|
5 |
|
|
|
|
|
|
4 |
|
|
|
|
|
|
3 |
|
|
|
|
|
|
2 |
|
|
|
|
|
|
1 |
A |
B |
C |
D |
E |
F |
|