Образовательный портал Павла Добряка

Начнем проверять ячейки с наиболее удаленной от места назначения клетки, потому что так быстрее и удобнее будет изучить поведение робота, выполняющего алгоритм (клетка старта отмечена кружочком):

Проверяем условие цикла ПОКА<справа свободно ИЛИ снизу свободно >. Оба условия верны, поэтому заходим внутрь этого цикла и проверяем условие внутреннего цикла ПОКА < снизу свободно >. Его условие также истинно, поэтому выполняем тело внутреннего цикла вниз. Поскольку речь идет о цикле, то это действие повторяем много раз. То есть робот идет вниз до тех пор, пока не встретит преграду снизу:

После того, как робот дойдет до низа, условие цикла ПОКА < снизу свободно > перестанет выполняться.

Начнет проверяться условие второго внутреннего цикла ПОКА < справа свободно >

Это условие истинно, поскольку речь идет о цикле, робот будет шагать вправо до тех пор, пока не встретится стена:

То есть клетка старта нам подходит:

Далее проверяем клетки по нашей траектории движения вниз и убеждаемся, что они подходят (заметим, что так бывает не всегда):

Проверим нижние клетки по траектории движения и убедимся, что они тоже подходят (для них первый внутренний цикл ПОКА < снизу свободно > не работает, зато работает второй внутренний цикл ПОКА < справа свободно >):

Наконец, проверяем точку финиша и убеждаемся, что робот, находящийся в ней, никуда не уйдет и не разобьется, так как условия внешнего цикла ПОКА<справа свободно ИЛИ снизу свободно > ложны:

Рассмотрим следующую дальнюю клетку лабиринта:

Условие внешнего цикла выполняются, начинается первый внутренний цикл ПОКА < снизу свободно >:

Когда перестает выполняться первый внутренний цикл, начинает работать второй цикла ПОКА < справа свободно >.

Робот уходит в тупик, поэтому наша точка старта не годится:

Не годится и следующая точка по изучаемой траектории (робот ведет себя так же, как и в уже проверенных клетках нижнего ряда):

А вот следующая клетка изучаемой траектории С2 породит новую траекторию, так как робот сперва стремится пойти вниз за счет первого внутреннего цикла:

Проверим и убедимся, что все эти клетки новой траектории ведут в тупик:

Мы изучили достаточно траекторий, чтобы вкратце сформулировать движение робота на естественном, а не на алгоритмическом языке: «Робот стремится идти до предела вниз, затем до предела вправо, затем до предела вниз, затем до предела вправо и т.д.». С такой формулировкой проверять становится проще.

Возвращаемся к старой траектории и убеждаемся, что следующая клетка D2 не годится:

А клетка E2 подойдет:

Подойдут и клетки по её траектории:

Клетка F2 не подойдет:

Рассмотрим неизученные клетки верхнего ряда. Заметим, что если под ними забракованные клетки, то верхние клетки не подойдут, а если в клетке снизу стоит галочка, то подойдут:

Левый не изученный и центральный не изученный столбцы не подходят:

Правый не изученный столбец подойдет:

Остается пересчитать галочки и написать ответ.

Ответ: 19

Сравним алгоритмы первой и второй задачи, жирным выделив различия:

Начнем решать также, как и в предыдущей задаче:

Поскольку вместо второго внутреннего цикла у нас условие ЕСЛИ < справа свободно >, то речь идет об однократном движении вправо:

Далее программа начнет проверять условие внешнего цикла ПОКА<справа свободно ИЛИ снизу свободно >. Оно истинно. Программа проверит условие внутреннего цикла ПОКА < снизу свободно >, оно ложно. Программа проверит условие ЕСЛИ < справа свободно >, оно истинно и программа шагнет вправо. И т.д. Пока траектория движения совпадает с траекторией старой задачи:

Убеждаемся, что все клетки траектории подойдут:

А траектория из клетки B1 не совпадает с траекторией старой задачи:

Текущая задача

Старая задача:

Мы можем сформулировать описание траекторий:

Убеждаемся, что клетки по рассматриваемой траектории не подходят:

Не подойдут и следующие клетки:

Рассмотрим траекторию из D1:

Они подойдут:

Также подойдут клетки:

Оставшиеся клетки не подходят:

Ответ: 21.

Описание траектории: робот пытается сделать один шаг вниз, затем идти вправо до предела, затем один шаг вниз, затем вправо до предела, и т.д.

Траектория робота из А1 сильно отличается от траектории предыдущих задач:

Текущая задача:

Предыдущие две задачи:

Таким образом, А1 не годится:

Проверяем А2:

А2 подходит:

Аналогично А2 подойдут С2 и Е2

Аналогично B2, D2 и F2 не подходят:

Рассмотрим траекторию из А3:

А3 подходит, и аналогично годится весь 3 ряд:

Рассмотрим траекторию из А4:

А4 не подходит, как и B4, C4, D4:

Рассмотрим траекторию из А5:

А5 подойдет, как и все клетки её траектории:

Клетки B5, C5, D5 не подходят, а Е4, Е5, F4, F5  подойдут:

Наконец, оставшиеся клетки верхнего ряда не подходят:

Ответ: 20.

Робот ходит лесенкой: шаг вниз, шаг вправо, шаг вниз, шаг вправо (если нет препятствий), и т.д.

Траектория из клетки А1:

А1 подходит, как и прочие верхние элементы ступеньки С2, D3, Е4, F5 и F6:

Рассмотрим траекторию из Е5:

Эти клетки подходят:

Подойдут также следующие клетки:

Рассмотрим траекторию из С3:

Эти клетки не годятся:

Рассмотрим траекторию из А2:

Верхние клетки траектории не годятся, нижние порождают новую траекторию:

Эти клетки не годятся, но А5 подходит:

Продолжая «строить лесенки», получаем следующую картину:

Ответ: 22.

Внешний цикл «Пока» содержит два условия, соединенные «или». В этом цикле переход «вправо» не имеет условий. Робот, дойдя до низа во вложенном цикле, далее сделает шаг вправо, даже если справа стена. То есть алгоритм потенциально содержит возможность разрушения робота. Еще один подвох задачи заключается в том, что робот, дойдя до нужной клетки, может и не остановиться (ученики часто забывают проверить, остановится ли робот в конечной клетке).

По клетке А1 изучим траекторию робота:

Начав движение из клетки В1, робот, в отличие от старта из А1, не остановится, а разобьется:

Остановки произойдут при старте из клеток А5 и B3:

Робот разобьется при старте из С1, В1 и F1:

Из Е1 робот дойдет и остановится в F6:

Аналогично нам подойдут клетки старта D3 и С5: