Сало. Выполнение алгоритмов для исполнителя

• Название: Выполнение алгоритмов для исполнителя
• Дата: 22.01.2021
• Размер: 1.59 Mb.
• Имя файла: ege14.doc
• Тип: Документы; #170407
• страница: 5 из 26

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

						6
						5
						4
						3
						2
						1
A	B	C	D	E	F

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

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

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

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

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

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

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

НАЧАЛО

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

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

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

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

КОНЕЦ

Решение:

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

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

2. 
   кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода
   
3. 
   обратим внимание, что возможны еще «вырожденные» варианты, вроде таких:
   
4. 
   итак, мы выяснили, что нужно рассматривать лишь те клетки, где есть стенка справа; отметим на исходной карте клетки-кандидаты:
   

						6
						5
						4
						3
						2
						1
A	B	C	D	E	F

5. 
   

   						6
   						5
   						4
   						3
   						2
   						1
   A	B	C	D	E	F

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

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

						6
						5
						4
						3
						2
						1
A	B	C	D	E	F

						6
						5
						4
						3
						2
						1
A	B	C	D	E	F

						6
						5
						4
						3
						2
						1
A	B	C	D	E	F

						6
						5
						4
						3
						2
						1
A	B	C	D	E	F

7. 
   итак, условию удовлетворяет только одна клетка – F4
   
8. 
   таким образом, правильный ответ – 1.
   

Возможные ловушки и проблемы: вариантов может быть достаточно много, важно не пропустить ни один из них можно попытаться выполнить алгоритм для каждой клетки лабиринта, но это займет много времени; поэтому лучше ограничиться только клетками-кандидатами нужно правильно определить свойства, по которым клетку можно считать «кандидатом» можно не заметить стенку и таким образом получить лишнее решение