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

• Название: Выполнение алгоритмов для исполнителя
• Дата: 02.02.2022
• Размер: 1.82 Mb.
• Имя файла: ege12.doc
• Тип: Документы; #349572
• страница: 5 из 30

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

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

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

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

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

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

Цикл

ПОКА < условие >

последовательность команд

КОНЕЦ ПОКА

выполняется, пока условие истинно. В конструкции

ЕСЛИ < условие >

ТО команда1

ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если

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

условие ложно).

Если РОБОТ начнёт движение в сторону находящейся рядом с ним

стены, то он разрушится и программа прервётся.

Сколько клеток лабиринта соответствуют требованию, что, начав

движение в ней и выполнив предложенную программу, РОБОТ уцелеет

и остановится в закрашенной клетке (клетка F6)?

1) 8 2) 15 3) 24 4) 27

НАЧАЛО

ПОКА < справа свободно ИЛИ снизу свободно >

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

вправо

КОНЕЦ ПОКА

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

вниз

КОНЕЦ ПОКА

КОНЕЦ ПОКА

КОНЕЦ

Решение:

1. 
   обратим внимание, что в программе три цикла, причем два внутренних цикла вложены в один внешний
   
2. 
   цикл
   

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

вправо

КОНЕЦ ПОКА

означает «двигаться вправо до упора», а цикл

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

вниз

КОНЕЦ ПОКА

означает «двигаться вниз до упора»

3. 
   тогда программу можно записать в свободном стиле так:
   

ПОКА не пришли в угол

двигаться вправо до упора

двигаться вниз до упора

КОНЕЦ ПОКА

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

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

→	→	↓
		↓
		↓

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

1. 
   Робот может попасть в эту клетку, двигаясь вниз из клетки, где справа – стенка
   
2. 
   снизу есть стенка;
   
3. 
   снизу стенка есть, справа – нет, поэтому будет выполнен еще один шаг внешнего цикла.
   

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

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

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

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

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

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

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

Возможные ловушки и проблемы: нужно помнить, что внешний цикл может выполняться более одного раза; неучет этого обстоятельства приводит к неверному ответу 2 (15 клеток) важен порядок выполнения внутренних циклов (в данном случае сначала Робот идет вправо, а затем – вниз); при изменении этого порядка изменится и результат, в частности, изменятся условия, определяющие особую клетку