Закрашивание коридора произвольной длины

Робот стоит в левом конце горизонтального коридора, нижняя стена которого сплошная, а в верхней имеется несколько выходов. Составить алгоритм, который переводит Робота из клетки А в клетку Б (рис. 16) и закрашивает все клетки коридора (на рис. 16 отмечены точками).

 

 

Рис. 16

 

Как составить такой алгоритм? Поскольку число клеток в коридоре неизвестно, то при записи алгоритма не обойтись без цикла пока. В какой же момент цикл должен окончиться? Он должен окончиться, когда Робот окажется в клетке Б. Чем клетка Б отличается от клеток коридора? Как видно из рисунка 16, у клетки Б нет стены снизу, а у всех клеток коридора стена снизу есть. Поэтому после пока можно написать условие снизу стена. За один шаг цикла Робот должен закрашивать очередную клетку и переходить в следующую. Количество закрашенных клеток здесь равно количеству шагов (клетка Б не закрашивается!), поэтому дополнительные команды не нужны.

 

А21

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

дано | Робот в левой клетке горизонтального коридора (рис. 15)

надо | Робот вышел из коридора вправо, коридор закрашен

нач

нц пока снизу стена

закрасить

вправо

Кц

Кон

 

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

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

 

 

 

Рис. 17

 

 

Поскольку размеры лабиринта неизвестны, нам не обойтись без цикла пока. Когда этот цикл должен закончиться, т. е. чем конечное положение Робота (клетка Б) отличается от всех остальных? Видно, что в клетке Б стены есть и слева и сверху, а во всех остальных клетках хотя бы одной из этих стен нет. Значит, условие окончания цикла — "сверху стена и слева стена", т. е. цикл нужно продолжать до тех пор, пока либо слева, либо сверху от клетки свободно. Это условие записывается так: "слева свободно или сверху свободно".

Внутри цикла надо смещать Робота по направлению к углу. Воспользуемся методом последовательного уточнения — введем вспомогательный алгоритм "сместиться к углу" (его мы составим потом) и запишем основной алгоритм:

А22

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

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

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

нач

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

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

кц

Кон

 

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

 

А23

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

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

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

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

нач

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

вверх

Кц

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

влево

Кц

Кон

 

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

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

 

А24

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

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

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

Нач

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

влево

Кц

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

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

вверх

Кц

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

влево

Кц

Кц

Кон

 

 

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

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

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

закрасить

кц

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

закрасить

кц

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

 

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

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

вправо

кц

 

Рис. 18

 

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

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

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

Кц

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

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

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

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

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

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

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

 

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

 

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

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

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

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

 

 

Рис. 19

 

 

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

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

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

 

Рис. 20

 

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

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

|положении (рис. 21)

 

Рис. 21

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

дано | Робот где-то в горизонтальном коридоре
надо | закрашены все клетки коридора, Робот в исходном положении (рис. 22)

 

Рис. 22

 

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

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

надо | закрашены все клетки правее и выше стартовой (рис. 23), Робот в исходном положении

 

Рис. 23

 

8. Дано, что на поле Робота только одна стена и эта стена расположена строго горизонтально. Робот находится в одной из клеток, прилегающих к стене сверху (рис. 24). Точные размеры стены и точное расположение Робота неизвестны. Составьте алгоритм, при выполнении которого Робот:

а) окажется в одной из клеток, прилегающих к стене снизу;

б) закрасит все клетки, прилегающие к стене сверху;

в) закрасит все клетки, прилегающие к стене снизу;

г) закрасит все прилегающие к стене клетки

 

Рис. 24

 

 

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

 

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

алг обход прямоугольника

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

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

надо | Робот под нижней стороной прямоугольника

 

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

 

Рис. 25

 

12. Составьте алгоритм для закраски всех клеток вокруг прямоугольной стены (рис.26).

Рис. 26

 

13. Составьте алгоритм для закраски всех клеток вокруг Т-образной стены неизвестного размера (рис. 27).

 

Рис. 27

 

11.Команды ветвления и контроля

11.1. Пример алгоритма с командой если

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

В режиме непосредственного управления Роботом задача решается просто. Чтобы узнать, в какой клетке сейчас находится Робот, зададим ему вопрос "справа свободно?". Ответ да означает, что Робот в левой клетке и должен сделать шаг вправо. При ответе нет Робот в правой клетке и должен сдвинуться влево.

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

если справа свободно, то скомандовать вправо, иначе — скомандовать влево.

 

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

	А25

алг дежурство

дано | Робот в одной из клеток "двухкомнатного" помещения (рис. 28)

надо | Робот в другой клетке

Нач

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

то вправо

иначе влево

Все

Кон

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

 

Рис. 29

 

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

 

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

то закрасить

иначе...

все

 

 

А что, собственно, «иначе»? Как записать, что иначе ничего делать не надо? Для таких случаев существует краткая форма команды если, в которой слова иначе вообще нет

 

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

то закрасить

Все

А26

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

алг разметка выходов из коридора

дано | Робот в левой клетке горизонтального коридора (рис. 29)

надо | Робот вышел из коридора вправо, клетки коридора,

| из которых есть выход вверх, закрашены

нач

нцпока снизу стена

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

то закрасить

все вправо

Кц

Кон

 

11.2. Общий вид команды если

Общий вид команды если таков:

если условие если условие

то серия 1 илито серия 1

иначе серия 2 все

Все

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

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

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

 

 

Рис. 30

 

 

Графическая схема выполнения команды если приведена на рисунке 30 (а — полная форма, б — сокращенная).

 

Команды контроля

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

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

Для записи контрольных условий в алгоритмическом языке есть специальная команда контроля

утв условие

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

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

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

 

11.4. Пример алгоритма с командой утв

 

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

 

 

Рис. 31

 

 

Для решения этой задачи мы можем составить следующий алгоритм:

 

 

алг закрасить тупики

А27

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

| выше некоторых клеток коридора есть тупики размером

| в одну клетку (рис. 31)

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

| закрашены

нач

нцпока снизу стена

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

то

вверх

утв | Робот в тупике

закрасить

вниз

Все

вправо

Кц

Кон

В этом алгоритме команда утв содержит только комментарий, поясняющий алгоритм. Мы можем, однако, заменить ее на команду

утв слева стена и сверху стена и справа стена

В этом случае при выполнении алгоритма компьютер будет проверять указанное условие и попытка выполнить алгоритм в неподходящей обстановке (т. е. в обстановке, отличающейся от рис. 31) приведет к отказу.

11.5. Выбор из многих вариантов

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

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

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

 

А28

алг уйти из клетки

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

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

Нач

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

то вверх

Иначе

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

то вправо

Иначе

если снизу свободно

то вниз

Иначе

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

влево

все

все

все

кон

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

А29

алг уйти из клетки

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

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

Нач

выбор

при сверху свободно: вверх

при справа свободно: вправо

при снизу свободно: вниз

иначеутв слева свободно; влево

Все

кон

 

 

11.6 Общий вид команды выбор

 

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

 

выбор при условие 1: серия 1 при условие 2: серия 2 …. при условие н: серия н иначе серия н+1 все

выбор при условие 1: серия 1 при условие 2: серия 2 …. при условие н: серия н все

 

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

Рис. 32

 

Допустимо любое количество условий и соответствующих им серий команд. Как и в команде если, серия н + 1 вместе со служебным словом иначе может отсутствовать.

При выполнении команды выбор компьютер последовательно проверяет условия: условие 1, условие 2 и т. д. Как только очередное условие окажется верным, компьютер выполняет соответствующую ему серию команд и прекращает выполнение команды выбор, переходя к командам, записанным после слова все. Оставшиеся условия не проверяются и серии не выполняются.

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

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

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

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

а) ниже каждой закрашенной;

б) выше и ниже каждой закрашенной;

в) левее каждой закрашенной;

г) правее каждой закрашенной;

д) левее и правее каждой закрашенной.

 

2. Воспользовавшись вспомогательными алгоритмами "вверх до стены", "вниз до стены", "вправо до стены", "влево до стены", составьте алгоритмы со следующими заголовками:

а) алг переход в противоположный угол

дано | Робот стоит в каком-то углу прямоугольника,

| огороженного стенами. Других стен нет

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

б) алг к противоположной стене

дано I Робот стоит у стены (но не в углу) внутри прямо-

| угольника, обнесенного со всех сторон стенами;

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

надо | Робот перешел к противоположной стене

3. Петя решил сделать алгоритм "уйти из клетки" более понятным и не использовать команду выбор. Вот что у него получилось:

А30

алг уйти из клетки '

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

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

Нач

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

| то вверх

все:'

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

| то вправо

Все

если снизу свободно

[ то вниз

Все

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

| то влево

Все

Кон

Всегда ли после выполнения этого алгоритма Робот выйдет из исходной клетки?

 

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

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

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