Алгоритмы управления исполнителями.

Алгоритмы управления исполнителями.

7.1. Исполнитель Робот

Робот действует на прямоугольном клетчатом поле. Между некоторыми клетками поля могут быть расположены стены. Какие-то клетки могут быть закрашены. Сам Робот всегда занимает ровно одну клетку поля (рис. 1).

Робот умеет выполнять всего 17 команд: 5 команд-приказов и 12 команд-вопросов. Мы пока изучим только команды-приказы Робота: вверх, вниз, вправо, влево, закрасить.

По командам вверх, вниз, вправо, влево Робот перемещается в соседнюю клетку в указанном направлении. Если на пути оказывается стена, команда не может быть выполнена. Например, в случае, показанном на рисунке 1, нельзя выполнить команду вверх.

По команде закрасить Робот закрашивает клетку, в которой стоит. Если клетка уже была закрашена, она останется закрашенной, т. е. команда будет выполнена, но никаких видимых изменений не произойдет.

 

Рис. 1. Поле Робота.

 

Программное управление исполнителем

Для программного управления недостаточно знать, какие команды, и в какой последовательности надо исполнить. Нужно еще записать эти команды в форме, понятной для компьютера, т. е. оформить их в виде алгоритма.

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

	А1

алг ход конем

дано | Робот в клетке А, стен на поле нет (рис. 1)

надо | Робот в клетке Б (рис. 1)

нач

вправо

вправо

вниз

Кон

 

Общий вид алгоритма

В простейшем случае алгоритм на алгоритмическом языке записывается так:

алг имя алгоритма

дано условия применимости алгоритма заголовок алгоритма

надо цель выполнения алгоритма

нач

| последовательность команд тело алгоритма

Кон

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

Имя (название) алгоритма — это одно или несколько слов. Обычно оно подбирается так, чтобы можно было понять, для чего служит алгоритм.

В строке дано описывается начальное состояние, при котором должен выполняться алгоритм, в строке надо — состояние после выполнения алгоритма.

Строки алг, дано и надо образуют заголовок алгоритма. Заголовок задает условие решаемой задачи, в нем указывается, что делает данный алгоритм.

Часть алгоритма от строки нач до строки кон называется телом алгоритма. Тело описывает решение задачи, в нем показано, как достигается цель алгоритма.

Исполнение алгоритма

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

1) Находит в памяти алгоритм с указанным именем.

2) Проверяет, соблюдаются ли начальные условия, указанные в строке дано (в примерах этого параграфа в дано пишутся только комментарии, но позднее мы научимся помещать там условия, которые компьютер сможет проверять).

3) Последовательно читает команды после строки нач и передает их исполнителю. Каждый такой приказ на выполнение команды называется вызовом этой команды.

4) Встретив строку кон, проверяет, достигнута ли цель алгоритма, указанная в строке надо (см. примечание к п. 2).

5) Заканчивает выполнение алгоритма.

 

Пример. Компьютер получает приказ исполнить алгоритм "ход конем".

1) Компьютер находит в памяти алгоритм А1.

2) В строке дано записан комментарий — компьютер его пропускает.

3) Компьютер последовательно командует Роботу вправо, вправо, вниз. Робот исполняет эти команды.

4) В строке надо помещен комментарий — компьютер его пропускает.

5) Компьютер заканчивает выполнение алгоритма "ход конем".

Ошибки в алгоритмах

Если при составлении алгоритма мы случайно вместо вниз напишем внис или вместо вправо — направо, то компьютер нашу запись не поймет и, даже не приступая к выполнению алгоритма, сообщит об ошибке. Ошибки в записи алгоритма называются синтаксическими.

Но даже если все команды записаны правильно, это еще не значит, что алгоритм составлен без ошибок. Ошибки в составлении алгоритма называются логическими.

Иногда логическая ошибка может привести к отказу — невозможности выполнить очередную команду. Например, при попытке выполнить алгоритм "ход конем" (А1) в обстановке, изображенной на рисунке 2, компьютер попытается последовательно вызвать команды вправо, вправо, вниз. Однако вторую команду вправо Робот выполнить не сможет — возникает отказ. Получив от исполнителя сигнал отказа, компьютер сообщает об ошибке и прекращает выполнение алгоритма.

 

Рис. 2

У каждого исполнителя могут быть свои причины отказов. Отказ Робота возникает при попытке идти сквозь стену.

Ошибки в алгоритме не всегда приводят к отказам. Возможны логические ошибки, не обнаруживаемые компьютером ни до, ни во время выполнения алгоритма. Так, если в алгоритме А1 мы вместо вправо случайно напишем влево, то компьютер выполнит алгоритм, Робот из клетки А переместится в клетку В (см. рис. 2), но никаких сообщений об ошибках мы не получим (да и откуда компьютеру знать, куда мы на самом деле хотели переместить Робота!).

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

 

Таблица 1. Ошибки в алгоритмах.

 

№	Смысл ошибки	Название	Пример
	Цель не достигнута	Логическая	Робот не попал куда надо
	Команда не входит в СКИ	Синтаксическая	наверх, направо
	Авария при попытке исполнения команды	Семантическая (отказ)	Попытка пройти сквозь стену

Нач

вверх; вверх; вправо; вниз; вниз; вправо

вверх; вверх; вправо; вниз; вниз; вправо

вверх; вверх; вправо; вниз; вниз; вправо

вверх; вверх; вправо; вниз; вниз; вправо

вверх; вверх; вправо; вниз; вниз; вправо

Кон

 

 

ЗАДАЧИ И УПРАЖНЕНИЯ

1. Дан алгоритм, в котором стерты комментарии и название:

А3

а) алг

дано |

надо |

Нач

вверх; закрасить; вниз

вправо; закрасить; влево

вниз; закрасить; вверх

влево; закрасить; вправо

Кон

А4

б) алг

дано |

надо |

Нач

вверх; вправо; закрасить

вниз; вниз; закрасить

влево; влево; закрасить

вверх; вверх; закрасить

вправо; вниз

Кон

Для каждого случая — а) и б) — опишите движение Робота в процессе выполнения соответствующего алгоритма. Нарисуйте начальное и конечное положения Робота и закрашенные в результате выполнения клетки. Придумайте подходящее название алгоритма и впишите комментарии после слов дано и надо

2. Измените алгоритм решения задачи 1б) так, чтобы при его исполнении Робот:

а) прошел тем же маршрутом, но ничего не закрашивал;

б) закрасил все клетки, в которых он побывал.

 

3. Известно, что на поле Робота нет стен и закрашенных клеток. Не делая рисунка, определите, сколько клеток будет закрашено после выполнения следующих команд:

 

 

а)	закрасить	б)	закрасить
	вправо		вправо
	вверх		закрасить
	закрасить		закрасить
	вправо		вправо
	закрасить		вправо
	вверх		закрасить
	закрасить		закрасить
	закрасить		закрасить
	вправо		вправо

 

4. Известно, что на поле Робота имеется одна стена, равная по длине стороне клетки, а попытка выполнить последовательность команд из задачи 3а) приводит к отказу. Составьте последовательность команд, при выполнении которой сохранится конечное положение Робота, закрашены будут те же клетки, а отказа не возникнет.

 

5. Составьте алгоритм, при выполнении которого Робот переместится из клетки А в клетку В (рис. 4)

 

 

Рис. 4

6. Составьте алгоритм, который переводит Робота из А в Б и закрашивает клетки, отмеченные точками (рис. 5)

 

 

 

Рис. 5

 

7. Петя составил алгоритм, а Коля стер в нем одну команду:

 

	А5

Алг

дано | стен на поле нет

надо | Робот погулял и вернулся в исходное положение

Нач

вверх

вправо

???

вниз

влево

влево

Кон

 

Определите, какую команду стер Коля, если известно, что при выполнении составленного Петей алгоритма Робот возвращался в исходное положение.

8. Петя составил алгоритм, при выполнении которого Робот вернулся в исходное положение. Коля стер одну из команд. При выполнении Колиного алгоритма Робот также вернулся в исходное положение. Какую команду стер Коля?

9. Петя составил алгоритм, при выполнении которого на поле без стен Робот вернулся в исходное положение. Коля переставил две команды местами. Докажите, что при выполнении Колиного алгоритма Робот также вернется в исходное положение.

10. Петя составил алгоритм для Робота, который на поле без стен и закрашенных клеток закрашивает 5 клеток. Коля переставил в алгоритме две соседние команды. Может ли новый алгоритм закрашивать: а) 3; б) 4; в) 5; г) 6; д) 7 клеток?

11. Петя составил алгоритм, при выполнении которого Робот закрашивает 5 клеток. Коля переставил в алгоритме две команды (необязательно соседние). Может ли новый алгоритм закрашивать: а) 0; б) 1; в) 5; г) 7; д) 100 клеток?

12. Петя составил алгоритм, переводящий Робота из клетки А в клетку Б с закрашиванием каких-то клеток. Что должен сделать Коля с этим алгоритмом, чтобы получить алгоритм, переводящий Робота из Б в А и закрашивающий те же клетки?

 

 

Вспомогательные алгоритмы

Нач

I вверх; вверх; вправо; вниз; вниз; вправо

Кон

Теперь, составляя алгоритм прохождения лабиринта, можно не переписывать команды прохождения участка, а вызвать уже написанный алгоритм "участок".

 

алг из А в Б

дано | Робот в клетке А (рис. 3 а)

надо | Робот в клетке Б (рис. 3 а)

Нач

| участок; участок; участок; участок; участок

Кон

 

Запись "участок" в алгоритме "из А в Б" — это команда вызова вспомогательного алгоритма с именем "участок". Выполняя эту команду, компьютер приостанавливает выполнение алгоритма "из А в Б", выполняет алгоритм "участок", а затем продолжает выполнение алгоритма "из А в Б".

 

Пример использования вспомогательных алгоритмов

Пусть требуется написать алгоритм, который проводит Робота из клетки А в клетку Б и закрашивает клетки, отмеченные точками (рис. 6). На рисунке показан один из возможных путей Робота при решении этой задачи. Видно, что Робот должен закрасить три прямоугольных «блока» размером 3x5 клеток, а между закрашиваниями два раза обойти стену. Запишем эту мысль в виде основного алгоритма:

А8

алг из А в Б с закрашиванием

дано | Робот в точке А (рис. 6)

надо | Робот в точке Б (рис. 6), нужные клетки закрашены

Нач

закрашивание блока

обход стены

закрашивание блока

обход стены

закрашивание блока

кон

Теперь составим вспомогательные алгоритмы, используемые в основном алгоритме "из А в Б с закрашиванием" (А8):

 

А9

алг закрашивание блока

дано |. Робот в левом верхнем углу блока 3x5 клеток

надо | блок закрашен, Робот в его правом нижнем углу

Нач

закрасить; вправо; закрасить; вправо; закрасить; вниз

закрасить; влево; закрасить; влево; закрасить; вниз

закрасить; вправо; закрасить; вправо; закрасить; вниз

закрасить; влево; закрасить; влево; закрасить; вниз

закрасить; вправо; закрасить; вправо; закрасить

Кон

	А10

алг обход стены

дано | Робот в правом нижнем углу блока (рис. 6)

надо | Робот в левом верхнем углу следующего блока (рис. 6)

Нач

вправо; вверх; вверх; вверх; вверх; вверх; вверх

вправо; вправо; вниз; вниз

Кон

 

 

Рис. 6

 

Нач

| фрагмент; фрагмент; фрагмент; фрагмент; фрагмент

Кон

А12

алг фрагмент

Нач

закрасить; вправо; закрасить; вправо; закрасить; вправо

закрасить; вниз; закрасить; вниз; закрасить; вниз

закрасить; влево; закрасить; влево; закрасить; влево

закрасить; вверх; закрасить; вверх; закрасить

вправо; вправо; вправо; вниз; вниз

Кон

 

Нарисуйте результат выполнения алгоритма "фигура" (закрашенные клетки, начальное и конечное положения Робота).

4. Измените вспомогательный алгоритм "фрагмент" (А12) так, чтобы при выполнении алгоритма А11 Робот переместился из А в Б и закрасил клетки, отмеченные точками (рис. 8).

 

 

 

 

 

Рис. 8

 

 

9 Цикл n раз

9.1. Пример алгоритма с циклом n раз

При составлении алгоритмов довольно часто встречаются случаи, когда некоторую последовательность команд нужно выполнить несколько раз подряд (см., например, алгоритм A2). Для упрощения записи алгоритма в таких случаях можно использовать специальную составную команду алгоритмического языка — цикл n раз;

 

А13

алг из А в Б

дано | Робот в клетке А (рис. 3 а)

надо | Робот в клетке Б (рис. 3 а)

Нач

нц 5 раз

|вверх; вверх; вправо; вниз; вниз; вправо

кц

Кон

При выполнении этого, алгоритма компьютер 5 раз повторит последовательность вызовов вверх; вверх; вправо; вниз; вниз; вправо и Робот окажется в клетке Б (рис. 3 а).

9.2. Общий вид цикла n раз

В общем виде цикл n раз записывается так:

нц число повторений раз

| тело цикла (последовательность команд)

кц

Служебные слова нц (начало цикла) и кц (конец цикла) пишутся строго одно под другим и соединяются вертикальной чертой. Правее этой черты записывается повторяемая последовательность команд (тело цикла).

Число повторений — произвольное целое число.

При выполнении алгоритма последовательность команд в теле цикла повторяется указанное число раз. Правила алгоритмического языка допускают задание любого целого числа повторений. Оно может быть нулевым и даже отрицательным. Эти случаи не считаются ошибочными, просто тело цикла не будет выполнено ни разу, а компьютер сразу перейдет к выполнению команд, записанных после кц

 

 

Кон

При выполнении этого короткого алгоритма компьютер даст Роботу 30 команд: сначала 10 раз будет выполнена пара команд закрасить; вправо, а затем 10 команд влево.

Если вместо числа 10 поставить 100, Робот выполнит уже 300 команд, а ведь длина алгоритма при этом не увеличится!

Таким образом, короткие алгоритмы могут описывать очень длинные последовательности действий.

 

 

А15

9.4. Внутри цикла можно вызывать вспомогательные алгоритмы

 

алг закрасить прямоугольник

дано | на поле Робота стен нет

надо | закрашен прямоугольник размером 10х6

| Робот в исходное положение (рис. 9)

нач

нц 6 раз

закрасить ряд из 10 клеток

вниз

кц

нц 6 раз

I вверх

кц

Кон

Рис. 9

Кон

 

Цикл, который находится внутри другого, называется вложенным циклом.

 

ЗАДАЧИ И УПРАЖНЕНИЯ

1. Решите задачи 6 и 9 из § 7 с использованием цикла n раз.

2. Решение каких задач из § 8 можно упростить, воспользовавшись циклом n раз? Составьте соответствующие алгоритмы.

 

10. Цикл пока

10.1. Команды-вопросы Робота

До сих пор все составленные нами алгоритмы управления Роботом приводили к выполнению определенной, заранее известной последовательности действий. Компьютер лишь приказывал Роботу выполнить какие-то действия, но никак не анализировал их результаты и обстановку на поле Робота.

Представьте себе начальника, который отдает приказы, но не получает никаких донесений о результатах их выполнения; повара, который не имеет возможности попробовать блюдо; шофера, ведущего автомобиль с закрытыми глазами. Понятно, что так далеко не уедешь; если мы хотим составлять алгоритмы для решения сложных задач, то надо уметь не только командовать исполнителем, но и анализировать обстановку, в которой он оказался.

У Робота для этого есть 12 команд-вопросов, отвечая на которые он сообщает информацию об обстановке вокруг себя. В этом параграфе мы рассмотрим 10 из них. Вот они:

сверху стена сверху свободно

снизу стена снизу свободно

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

слева стена слева свободно

клетка закрашена клетка чистая

Смысл этих вопросов ясен из их названий. Получив команду-вопрос, Робот проверяет соответствующее условие и отвечает да или нет.

 

 

10.2. Цикл пока

 

Задача. Где-то ниже Робота на неизвестном расстоянии есть стена. Нужно подвести Робота к ней вплотную.

Спросим у Робота снизу свободно?. Если Робот ответит, нет, значит, он уже у стены и задача решена. Если же Робот ответит да, то можно скомандовать вниз и опять спросить снизу свободно?. Если Робот ответит да — снова скомандовать вниз, спросить снизу свободно? и т. д., пока Робот не ответит, нет. Скомандуем ли мы при этом вниз 0, 3, 8 или 2000 раз, заранее неизвестно — это зависит от начального расположения Робота относительно стены

 

Наша цель, однако, не ручное управление Роботом, а составление алгоритма для компьютера. Поэтому приведенную выше последовательность действий надо описать на алгоритмическом языке. Алгоритм должен быть универсальным, т. е. не должен зависеть от расстояния между Роботом и стеной. Для этого в алгоритмическом языке есть специальная составная команда — цикл пока:

А17

алг вниз до стены

нач

нцпока снизу свободно

вниз

Кц

Кон

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

10.3. Диалог Компьютер — Робот при выполнении цикла пока

 

Пусть в начальный момент Робот находится в клетке А (рис. 10). Тогда при выполнении алгоритма "вниз до стены" (А18) диалог Компьютер (ЭВМ) — Робот будет таким:

ЭВМ: снизу свободно? Робот: да

ЭВМ: вниз Робот: смещается вниз (в клетку Б)
ЭВМ: снизу свободно? Робот: да
ЭВМ: вниз Робот: смещается вниз (в клетку В)

ЭВМ: снизу свободно? Робот: нет

Рис. 10

Поскольку Робот ответил нет, т. е. записанное после пока условие не соблюдается, то на этом выполнение цикла пока и алгоритма "вниз до стены" заканчивается.

10.4. Общий вид цикла пока

В общем виде цикл пока записывается так:

нц пока условие

I тело цикла (последовательность команд)

кц

Слова нц и кц имеют тот же смысл, что и в цикле n раз — они отмечают начало и конец цикла.

Графическая схема выполнения цикла пока изображена на рисунке 11.

При выполнении цикла компьютер повторяет следующие действия:

а) проверяет записанное после служебного слова пока условие;

б) если условие не соблюдается (Робот ответил нет), то выполнение цикла завершается и компьютер начинает выполнять команды, записанные после кц. Если же условие соблюдается (Робот ответил да), то компьютер выполняет тело цикла и снова проверяет условие и т. д.

Рис. 11

10.5. Цикл n раз и цикл пока

Циклы n раз и пока оформляются в алгоритмическом языке почти одинаково. Это неудивительно, ведь обе эти команды задают цикл — повторяющуюся последовательность команд. Служебные слова нц и кц указывают, что исполняется цикл, а заголовок цикла задает конкретный механизм его выполнения.

Однако у этих двух циклов есть одно существенное отличие. Начиная выполнять цикл n раз, компьютер знает, сколько раз придется повторить тело цикла. При исполнении цикла пока это не так: компьютер каждый раз проверяет условие цикла и не может заранее определить, когда выполнение закончится. Узнать количество повторений цикла пока можно только после того, как цикл завершен.

Отсюда ясно, в каких случаях, какой цикл следует использовать. Если к моменту начала цикла количество повторений известно, удобно воспользоваться циклом n раз. Если же количество повторений заранее определить нельз я, необходим цикл пока.

10.6. Условия в цикле пока

В цикле пока могут использоваться простые и составные условия.

Простое условие — это обычно какая-то проверка. Примером может служить любая команда-вопрос Робота или операции сравнения: >, <, =, ≤, ≥, ≠. Позже мы познакомимся с ними.

Составное условие формулируется из одного или нескольких простых с использованием служебных слов и _, или, не. Смысл этих слов и правила построения с их помощью составных условий те же, что и в случае запросов к базе данных.

Рассмотрим подробнее проверку составного условия с или. Сначала проверяется первое простое условие. Если оно выполнено, то составное условие заведомо выполнено и второе простое условие даже не проверяется. Если же первое условие не выполнено, проверяется второе условие и результат этой проверки становится результатом всего составного условия.

Например, если Робот стоит в углу (рис. 12), то при проверке условия "сверху стена или

справа стена" окончательный ответ ясен уже после первой проверки (сверху стена), поэтому второе условие не проверяется, компьютер даже не будет задавать Роботу вопрос "справа стена". Если записать то же самое составное условие как "справа стена или сверху стена", то после первой проверки окончательный результат может оказаться любым, поэтому будет проверено и второе условие.

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

Если в составном условии с и первое условие оказалось неверным, второе уже не проверяется, так как результатом все равно будет, нет.

10.7. Свойства цикла пока

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

Закрашивание ряда

Робот находится у левой стены внутри прямоугольника, огороженного со всех сторон стенами (рис. 15). Внутри прямоугольника стен нет, его размеры неизвестны. Требуется закрасить горизонтальный ряд клеток от исходного положения Робота до правой стены и вернуть Робота в исходное положение.

 

Рис.15

 

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

 

 

А18

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

дано | Робот стоит у левой стены внутри огороженного

| с четырех сторон прямоугольника (рис. 15)

надо | горизонтальный ряд, в левой клетке которого стоял Робот

| полностью закрашен. Робот в исходном положении

Нач

вправо до стены с закрашиванием

влево до стены

Кон

Вспомогательный алгоритм "влево до стены" составляется аналогично А17

А19

алг влево до стены

нач

нцпока слева свободно

влево

Кц

Кон

 

Займемся теперь алгоритмом "вправо до стены с закрашиванием". В соответствии с методом последовательного уточнения, записав вызов этого алгоритма, мы фактически задали его заголовок:

алг вправо до стены с закрашиванием

дано | где-то справа от Робота есть стена

надо | Робот у стены, все клетки от исходной до стены закрашены

 

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

На каждом шаге цикла Робот должен сместиться вправо и закрасить клетку. Получится такой цикл:

нцпока справа свободно

вправо

закрасить

Кц

Ясно, что зацикливания не произойдет: по условию задачи стена где-то справа есть, при каждом выполнении цикла Робот делает шаг вправо и расстояние до стены уменьшается. Когда оно станет равным нулю, цикл закончится.

При выполнении этого цикла окажутся закрашенными все клетки правее исходного положения Робота, но сама исходная клетка останется незакрашенной. Поэтому перед выполнением цикла ее нужно закрасить отдельно. Необходимость дополнительной команды закрасить можно объяснить и так: количество закрашенных клеток должно быть на одну больше, чем количество шагов, сделанных Роботом (это видно из рисунка); в цикле выполняется один шаг и одно закрашивание, следовательно, требуется одно дополнительное закрашивание вне цикла.

Окончательно получаем алгоритм:

А20

алг вправо до стены с закрашиванием

дано | где-то справа от Робота есть стена

надо | Робот у стены, все клетки от исходной до стены закрашены

Нач

закрасить

нц пока справа свободно

вправо

закрасить

Кц

кон

Кц

Кон

 

Кон

 

Теперь составим вспомогательный алгоритм "сместиться к углу":

 

А23

алг сместиться к углу

дано | Робот где-то в лабиринте без углов (рис. 17), либо слева,

| либо сверху от Робота свободно

надо | Робот сместился к левому верхнему углу

нач

нцпока сверху свободно

вверх

Кц

нцпока слева свободно

влево

Кц

Кон

 

Как проверить, что цикл в алгоритме А22 рано или поздно закончится? Можно рассуждать так: при каждом выполнении тела цикла (т. е. при каждом выполнении алгоритма "сместиться к углу") расстояние от Робота до левого верхнего угла лабиринта уменьшается. Значит, рано или поздно Робот окажется в углу и цикл закончится.

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

 

А24

алг в левый верхний угол лабиринта

дано | Робот в лабиринте, вид которого изображен на рис. 16

надо | Робот в левом верхнем углу лабиринта

Нач

нцпока слева свободно

влево

Кц

нцпока сверху свободно

нцпока сверху свободно

вверх

Кц

нцпока слева свободно

влево

Кц

Кц

Кон

 

 

ЗАДАЧИ И УПРАЖНЕНИЯ

1. Составьте диалог компьютера и Робота при выполнении цикла

а) нцпока клетка чистая

закрасить

кц

б) нцпока клетка закрашена

закрасить

кц

в ситуации, когда Робот стоит. 1) в закрашенной клетке; 2) в незакрашенной.

 

2. Расположение Робота показано на рисунке 18. Составьте диалог компьютера и Робота при выполнении цикла

нцпока сверху свободно

вправо

кц

 

Рис. 18

 

3. Переделайте алгоритм «вправо до стены с закрашиванием» (А18), используя в нем цикл

нцпока справа свободно

закрасить; вправо

Кц

4. Составьте алгоритм для закрашивания прямоугольника:

алг закрасить прямоугольник

дано | Робот стоит в левом верхнем углу внутри огороженного

| с четырех сторон прямоугольника

надо | весь прямоугольник закрашен, Робот в исходном положении

5. Решите задачу 4, считая, что про начальное положение Робота в прямоугольнике не известно.

6. На поле Робота стен нет. Робот находится в левом верхнем углу прямоугольника из закрашенных клеток. Составьте алгоритм, переводящий Робота в правый нижний угол прямоугольника.

 

7. Составьте алгоритмы со следующими заголовками:

 

а) алг закрасить до стены вправо и вернуться

дано | где-то правее Робота есть стена

надо | закрашен ряд клеток между Роботом и стеной

| (рис. 19), Робот в исходном положении

 

 

Рис. 19

 

 

б) алг закрасить до закрашенной клетки вправо и вернуться

дано | где-то правее Робота есть закрашенная клетка (рис. 20)

надо | закрашен ряд клеток между Роботом и этой клеткой, Робот в исходном положении

 

Рис. 20

 

в) алг закрасить коридор

дано | Робот где-то в горизонтальном коридоре
надо | закрашены все клетки коридора, кроме стартовой