 |
ПОКА слева свободно ИЛИ сверху свободно
|
|
|
|
ЕСЛИ слева свободно
ТО влево
ИНАЧЕ вверх
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
Решение:
1) в программе один цикл со сложным условием, внутри которого расположен условный оператор «если»
2) в этой программе Робот не может разрушиться, так как возможность шага влево проверяется, а если влево ходить нельзя, то можно идти вверх, так как условие цикла «слева свободно ИЛИ сверху свободно» выполнено
3) Робот останавливается в клетке, где нарушается условие «слева свободно ИЛИ сверху свободно», в этой клетке должны быть стенки слева и сверху; таких клеток на поле всего три: конечная цель маршрута А1 и две «ложные цели» в В3 и Е1:
| A | B | C | D | E | F |
4) из п. 2 и 3 следует, что Робот успешно придет в клетку А1, если только он не попадёт в клетки В3 и Е1
5) подсчитаем, сколько есть клеток, из которых Робот попадает в клетку В3; Робот сначала идет влево до упора, потом – вверх, пока не упрётся в стенку сверху или не откроется «окно» влево; отметим голубым цветом все клетки, из которых Робот попадает в В3, их всего 13
| · | ||||||
| A | B | C | D | E | F |
6) кроме того, есть две клетки, из которых Робот попадает в Е1, они показаны фиолетовым цветом:
| · | ||||||
| · | ||||||
| A | B | C | D | E | F |
7) таким образом, на поле есть всего 15 клеток, из которых Робот при выполнении заданной программы не попадает в клетку А1
|
|
|
8) следовательно, «нужных» клеток 36 – 15 = 21
9) Ответ: 4.
Ещё пример задания:
Р-04. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
Вверх вниз влево вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
Сверху свободно снизу свободно
слева свободно справа свободно
Цикл
ПОКА < условие >
Последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно. В конструкции
ЕСЛИ < условие >
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если
| A | B | C | D | E | F |
условие ложно).
Если РОБОТ начнёт движение в сторону находящейся рядом с ним
стены, то он разрушится и программа прервётся.
Сколько клеток лабиринта соответствуют требованию, что, начав
движение в ней и выполнив предложенную программу, РОБОТ уцелеет
и остановится в закрашенной клетке (клетка F6)?
1) 8 2) 15 3) 24 4) 27
НАЧАЛО
ПОКА < справа свободно ИЛИ снизу свободно >
ПОКА < справа свободно >
Вправо
КОНЕЦ ПОКА
ПОКА < снизу свободно >
Вниз
КОНЕЦ ПОКА
КОНЕЦ ПОКА
КОНЕЦ
Решение:
1) обратим внимание, что в программе три цикла, причем два внутренних цикла вложены в один внешний
2) цикл
ПОКА < справа свободно >
Вправо
КОНЕЦ ПОКА
означает «двигаться вправо до упора», а цикл
|
|
|
ПОКА < снизу свободно >
Вниз
КОНЕЦ ПОКА
означает «двигаться вниз до упора»
3) тогда программу можно записать в свободном стиле так:
ПОКА не пришли в угол
Двигаться вправо до упора
Двигаться вниз до упора
КОНЕЦ ПОКА
где угол – это клетка, в которой есть стенки снизу и справа
4) за каждый шаг внешнего цикла Робот проходит путь в виде «сапога», двигаясь сначала вправо до упора, а затем – вниз до упора:
| → | → | ↓ | |
| ↓ | |||
| ↓ |
клетка, выделенная красным фоном особая – в ней заканчивается один шаг внешнего цикла и начинается следующий:
а) Робот может попасть в эту клетку, двигаясь вниз из клетки, где справа – стенка
б) снизу есть стенка;
в) снизу стенка есть, справа – нет, поэтому будет выполнен еще один шаг внешнего цикла.
5) в клетку F6 (это угол, где Робот остановился), Робот мог придти за один шаг внешнего цикла (за один «сапог») только из отмеченных клеток:
| → | → | → | → | → | ↓ | |
| → | → | ↓ | ||||
| → | → | → | → | → | ||
| A | B | C | D | E | F |
6) теперь отметим красным фоном особые клетки, которые удовлетворяют условиям а-в пункта 4 (см. выше), их всего 2:
| → | → | → | → | → | ↓ | |
| → | → | ↓ | ||||
| → | → | → | → | → | ||
| A | B | C | D | E | F |
7) отметим все пути в форме «сапога», которые приводят в особые клетки:
| → | → | ↓ | ||||
| → | → | ↓ | ||||
| → | → | → | → | → | ↓ | |
| → | → | ↓ | → | → | ↓ | |
| → | → | → | → | → | ||
| A | B | C | D | E | F |
8) больше особых клеток (см. пункт 4) нет; всего отмечено 24 клетки (считая конечную клетку F6)
9) таким образом, правильный ответ – 3.
| Возможные ловушки и проблемы: · нужно помнить, что внешний цикл может выполняться более одного раза; неучет этого обстоятельства приводит к неверному ответу 2 (15 клеток) · важен порядок выполнения внутренних циклов (в данном случае сначала Робот идет вправо, а затем – вниз); при изменении этого порядка изменится и результат, в частности, изменятся условия, определяющие особую клетку |
Еще пример задания:
|
|
|
| A | B | C | D | E | F |
Р-03. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
Вверх вниз влево вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
Сверху свободно снизу свободно
слева свободно справа свободно
Цикл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение?
1) 1 2) 2 3) 3 4) 0
НАЧАЛО
ПОКА <снизу свободно> вниз
ПОКА <слева свободно> влево
ПОКА <сверху свободно> вверх
ПОКА <справа свободно> вправо
КОНЕЦ
 
|  
| |||||
| ||||||
Решение:
1) легко понять, что для того, чтобы исполнитель вернулся обратно в ту клетку, откуда он начал движения, четыре стенки должны быть расставлены так, чтобы он упирался в них сначала при движении вниз, затем – влево, вверх и, наконец, вправо:
на рисунке красная точка обозначает клетку, начав с которой РОБОТ вернется обратно;
2) кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода
3) обратим внимание, что возможны еще «вырожденные» варианты, вроде таких:
 
|
| |||||
4) итак, мы выяснили, что нужно рассматривать лишь те клетки, где есть стенка справа; отметим на исходной карте клетки-кандидаты:
|
|
|
| · | · | |||||
| · | · | |||||
| · | ||||||
| · | ||||||
| · | · | |||||
| · | · | |||||
| A | B | C | D | E | F |
| · | ||||||
| · | ||||||
| · | ||||||
| · | ||||||
| · | ||||||
| · | ||||||
| A | B | C | D | E | F |
5) этих «подозрительных» клеток не так много, но можно еще сократить количество рассматриваемых вариантов: если РОБОТ начинает движение с любой клетки на вертикали F, он все равно приходит в клетку F4, которая удовлетворяет заданному условию, таким образом, одну клетку мы нашли, а остальные клетки вертикали F условию не удовлетворяют:
6) проверяем оставшиеся четыре клетки-кандидаты, но для каждой из них после выполнения алгоритма РОБОТ не приходит в ту клетку, откуда он стартовал:
| · | |||||
| A | B | C | D | E | F |
| ||||||
| · | ||||||
| A | B | C | D | E | F |
| · | |||||
| A | B | C | D | E | F |
| ||||||
| · | ||||||
| A | B | C | D | E | F |
7) итак, условию удовлетворяет только одна клетка – F4
8) таким образом, правильный ответ – 1.
| Возможные ловушки и проблемы: · вариантов может быть достаточно много, важно не пропустить ни один из них · можно попытаться выполнить алгоритм для каждой клетки лабиринта, но это займет много времени; поэтому лучше ограничиться только клетками-кандидатами · нужно правильно определить свойства, по которым клетку можно считать «кандидатом» · можно не заметить стенку и таким образом получить лишнее решение |
Еще пример задания:
| A | B | C | D | E | F |
Р-02. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
|
|
|
Вверх вниз влево вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
|
|
|
