Закрашивание коридора произвольной длины
Робот стоит в левом конце горизонтального коридора, нижняя стена которого сплошная, а в верхней имеется несколько выходов. Составить алгоритм, который переводит Робота из клетки А в клетку Б (рис. 16) и закрашивает все клетки коридора (на рис. 16 отмечены точками).
 |
Рис. 16
Как составить такой алгоритм? Поскольку число клеток в коридоре неизвестно, то при записи алгоритма не обойтись без цикла пока.В какой же момент цикл должен окончиться? Он должен окончиться, когда Робот окажется в клетке Б. Чем клетка Б отличается от клеток коридора? Как видно из рисунка 16, у клетки Б нет стены снизу, а у всех клеток коридора стена снизу есть. Поэтому после покаможно написать условие снизу стена. За один шаг цикла Робот должен закрашивать очередную клетку и переходить в следующую. Количество закрашенных клеток здесь равно количеству шагов (клетка Б не закрашивается!), поэтому дополнительные команды не нужны.
|
дано| Робот в левой клетке горизонтального коридора (рис. 15)
надо| Робот вышел из коридора вправо, коридор закрашен
нач
нц покаснизу стена
закрасить
вправо
Кц
Кон
Выход в левый верхний угол в лабиринте
Робот находится внутри прямоугольного лабиринта, огороженного с четырех сторон стенами. Внутри лабиринта стены имеют вид отрезков прямых и не касаются друг друга и наружных стен (рис. 17). Составить алгоритм, который в любом таком лабиринте перемещает Робота в левый верхний угол.
Рис. 17
Поскольку размеры лабиринта неизвестны, нам не обойтись без цикла пока.Когда этот цикл должен закончиться, т. е. чем конечное положение Робота (клетка Б) отличается от всех остальных? Видно, что в клетке Б стены есть и слева и сверху, а во всех остальных клетках хотя бы одной из этих стен нет. Значит, условие окончания цикла — "сверху стена ислева стена", т. е. цикл нужно продолжать до тех пор, пока либо слева, либо сверху от клетки свободно. Это условие записывается так: "слева свободно илисверху свободно".
Внутри цикла надо смещать Робота по направлению к углу. Воспользуемся методом последовательного уточнения — введем вспомогательный алгоритм "сместиться к углу" (его мы составим потом) и запишем основной алгоритм:
|
дано| Робот где-то в лабиринте без углов (рис. 17)
надо| Робот в левом верхнем углу лабиринта
нач
нцпокаслева свободно илисверху свободно
сместиться к углу
кц
Кон
Теперь составим вспомогательный алгоритм "сместиться к углу":
|
дано| Робот где-то в лабиринте без углов (рис. 17), либо слева,
| либо сверху от Робота свободно
надо| Робот сместился к левому верхнему углу
нач
нцпокасверху свободно
вверх
Кц
нцпокаслева свободно
влево
Кц
Кон
Как проверить, что цикл в алгоритме А22 рано или поздно закончится? Можно рассуждать так: при каждом выполнении тела цикла (т. е. при каждом выполнении алгоритма "сместиться к углу") расстояние от Робота до левого верхнего угла лабиринта уменьшается. Значит, рано или поздно Робот окажется в углу и цикл закончится.
Заметим, что Робота можно провести той же дорогой и не используя составных условий, например, так:
|
дано| Робот в лабиринте, вид которого изображен на рис. 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). Неизвестно, в какой из двух клеток находится Робот. Необходимо перевести его в другую клетку.
В режиме непосредственного управления Роботом задача решается просто. Чтобы узнать, в какой клетке сейчас находится Робот, зададим ему вопрос "справа свободно?". Ответ да означает, что Робот в левой клетке и должен сделать шаг вправо. При ответе нет Робот в правой клетке и должен сдвинуться влево.
Наши действия при непосредственном управлении Роботом можно описать так:
если справа свободно, то скомандовать вправо, иначе — скомандовать влево.
При решении этой задачи мы задавали Роботу вопрос и в зависимости от ответа выбирали следующее действие. Для описания такого выбора в алгоритмическом языке существует специальная команда если.Вот как можно записать алгоритм решения рассмотренной задачи:
|
алг дежурство
дано| Робот в одной из клеток "двухкомнатного" помещения (рис. 28)
надо| Робот в другой клетке
Нач
еслисправа свободно
товправо
иначевлево
Все
Кон
Рассмотрим еще одну задачу. Робот стоит в левом конце горизонтального коридора, нижняя стена которого сплошная, а в верхней имеется несколько выходов. Надо перевести Робота из клетки А в клетку Б и закрасить все клетки коридора, из которых есть выход вверх (рис. 29). Длина коридора, количество выходов и их точное расположение заранее неизвестны.
Рис. 29
Вспомним алгоритм А21 из предыдущего параграфа, решающий аналогичную задачу, но с закрашиванием всех клеток коридора. Новая задача отличается только тем, что красить надо не все клетки коридора, а лишь те, где есть выход вверх. Другими словами, если сверху свободно, то клетку надо закрасить, иначе — красить не надо. Попробуем записать это в виде команды если:
еслисверху свободно
то закрасить
иначе...
все
А что, собственно, «иначе»? Как записать, что иначе ничего делать не надо? Для таких случаев существует краткая форма команды если, в которой слова иначе вообще нет
еслисверху свободно
то закрасить
Все
|
алгразметка выходов из коридора
дано| Робот в левой клетке горизонтального коридора (рис. 29)
надо| Робот вышел из коридора вправо, клетки коридора,
| из которых есть выход вверх, закрашены
нач
нцпокаснизу стена
еслисверху свободно
то закрасить
все вправо
Кц
Кон
11.2. Общий вид команды если
Общий вид команды если таков:
еслиусловие еслиусловие
то серия 1 илито серия 1
иначесерия 2 все
Все
Служебные слова если, то, иначеимеют обычный смысл. Слово все означает конец команды. Это слово пишется строго под словом еслии соединяется с ним вертикальной чертой. Между тои иначе— в одной или нескольких строках — записывается последовательность команд алгоритмического языка (серия 1). Между иначеи всепомещается другая последовательность команд (серия 2). Серия 2 вместе со служебным словом иначеможет отсутствовать.
При выполнении команды есликомпьютер сначала проверяет условие, записанное между еслии то(задает Роботу вопрос). Если условие соблюдается, то выполняется серия 1, а если нет — то серия 2 (если она есть).
Если условие не соблюдается {Робот ответил нет),а серия 2 вместе с иначеотсутствует, то компьютер сразу переходит к выполнению команд, записанных после слова все.
Рис. 30
Графическая схема выполнения команды еслиприведена на рисунке 30 (а — полная форма, б — сокращенная).
Команды контроля
Вспомните: когда вы объясняете, как пройти к определенному месту, то наверняка говорите что-нибудь вроде «заверните за угол, там будет видна булочная». Это значит, что после выполнения команды «заверните за угол» надо проверить условие «видна булочная». Проверка этого условия нужна не для выбора каких-то действий (как в командах еслии выбор),а для того, чтобы убедиться: все идет нормально. Если булочной нет, значит, где-то раньше была допущена ошибка и дальнейшие действия бессмысленны.
Подобные контрольные утверждения применяются и при записи алгоритмов. Смысл их состоит в том, чтобы проверить, соответствуют ли условия выполнения алгоритма нашим представлением о них. Если что-то не так, это свидетельствует либо о несоответствии условий, либо об ошибке в алгоритме. В обоих случаях работу лучше прекратить.
Для записи контрольных условий в алгоритмическом языке есть специальная команда контроля
утвусловие
После служебного слова утв (утверждение) записывается контрольное условие. Если при выполнении команды утв контрольное условие оказывается нарушенным, компьютер прекращает выполнение алгоритма и сообщает, что возник отказ. Если же условие верно, то выполнение алгоритма продолжается так, как если бы команды утв не было вовсе.
Контрольные условия можно указать не только в команде утв, но и после слов дано и надо в заголовке алгоритма. Условие после дано проверяется в начале выполнения алгоритма, а условие после надо в конце.
Вместо контрольного условия, которое проверяет компьютер, в команде утв (так же как и в дано/надо) можно записать комментарий, предназначенный только для человека и облегчающий понимание алгоритма.
11.4. Пример алгоритма с командой утв
Задача. Робот стоит в левой клетке горизонтального коридора, от которого вверх отходят тупики размером в одну клетку. Требуется вывести Робота из коридора вправо (в клетку Б), а тупики закрасить (рис. 31).
Рис. 31
Для решения этой задачи мы можем составить следующий алгоритм:
алгзакрасить тупики
|
| выше некоторых клеток коридора есть тупики размером
| в одну клетку (рис. 31)
надо| Робот вышел из коридора вправо, клетки всех тупиков
| закрашены
нач
нцпокаснизу стена
еслисверху свободно
то
вверх
утв| Робот в тупике
закрасить
вниз
Все
вправо
Кц
Кон
В этом алгоритме команда утвсодержит только комментарий, поясняющий алгоритм. Мы можем, однако, заменить ее на команду
утвслева стена исверху стена исправа стена
В этом случае при выполнении алгоритма компьютер будет проверять указанное условие и попытка выполнить алгоритм в неподходящей обстановке (т. е. в обстановке, отличающейся от рис. 31) приведет к отказу.
11.5. Выбор из многих вариантов
Команда еслипозволяет выбрать один из двух вариантов возможных действий. Но иногда бывают ситуации, когда выбор нужно сделать из большего числа вариантов. Рассмотрим, например, такую задачу.
Задача. Робот на распутье. Робот находится в клетке, из которой есть выход (вокруг клетки меньше четырех стен). Необходимо перевести Робота в соседнюю клетку.
Для решения этой задачи нужно, задавая Роботу вопросы, узнать, в каком направлении есть выход, и дать соответствующую команду движения. Однако запись этого алгоритма с помощью команды еслиоказывается очень громоздкой:
|
дано| Робот в клетке, из которой есть выход
надо| Робот вышел из исходной клетки
Нач
еслисверху свободно
товверх
Иначе
еслисправа свободно
товправо
Иначе
еслиснизу свободно
товниз
Иначе
утвслева свободно
влево
все
все
все
кон
Для упрощения записи алгоритма при выборе из многих вариантов в алгоритмическом языке существует команда выбор.Используя эту команду, решение нашей задачи можно записать намного понятнее:
|
дано| Робот в клетке, из которой есть выход
надо| Робот вышел из исходной клетки
Нач
выбор
присверху свободно: вверх
присправа свободно: вправо
приснизу свободно: вниз
иначеутвслева свободно; влево
Все
кон
11.6 Общий вид команды выбор
В общем виде команда выбор записывается так:
выбор  при условие 1 : серия 1 при условие 2 : серия 2 …. при условие н : серия н иначе серия н+1 все | выбор при условие 1 : серия 1 при условие 2 : серия 2 …. при условие н : серия н все |
Графическая схема выполнения команды выбор показана на рисунке 32.
Рис. 32
Допустимо любое количество условий и соответствующих им серий команд. Как и в команде если,серия н + 1 вместе со служебным словом иначеможет отсутствовать.
При выполнении команды выборкомпьютер последовательно проверяет условия: условие 1, условие 2 и т. д. Как только очередное условие окажется верным, компьютер выполняет соответствующую ему серию команд и прекращает выполнение команды выбор,переходя к командам, записанным после слова все.Оставшиеся условия не проверяются и серии не выполняются.
Например, если Робот стоит в чистом поле без стен, то при выполнении алгоритма "уйти из клетки" первое условие (сверху свободно) оказывается верным, компьютер командует Роботу вверх, и на этом исполнение алгоритма заканчивается.
Если все условия проверены и ни одно из них не соблюдается, то выполняется серия команд, записанная после слова иначе,или, если слова иначенет, никакие команды не выполняются.
ЗАДАЧИ И УПРАЖНЕНИЯ
1. На поле Робота стен нет. В ряду из десяти клеток правее Робота некоторые клетки закрашены. Составьте алгоритм, который закрашивает клетки:
а) ниже каждой закрашенной;
б) выше и ниже каждой закрашенной;
в) левее каждой закрашенной;
г) правее каждой закрашенной;
д) левее и правее каждой закрашенной.
2. Воспользовавшись вспомогательными алгоритмами "вверх до стены", "вниз до стены", "вправо до стены", "влево до стены", составьте алгоритмы со следующими заголовками:
а) алг переход в противоположный угол
дано| Робот стоит в каком-то углу прямоугольника,
| огороженного стенами. Других стен нет
надо| Робот в противоположном углу
б) алг к противоположной стене
даноI Робот стоит у стены (но не в углу) внутри прямо-
| угольника, обнесенного со всех сторон стенами;
| внутри прямоугольника других стен нет
надо| Робот перешел к противоположной стене
3. Петя решил сделать алгоритм "уйти из клетки" более понятным и не использовать команду выбор.Вот что у него получилось:
|
дано| Робот в клетке, из которой есть выход
надо| Робот вышел из исходной клетки
Нач
еслисверху свободно
| то вверх
все:'
еслисправа свободно
| то вправо
Все
еслиснизу свободно
[ то вниз
Все
еслислева свободно
| то влево
Все
Кон
Всегда ли после выполнения этого алгоритма Робот выйдет из исходной клетки?
4. Робот внутри коридора без боковых выходов, идущего в неизвестном направлении. Составьте алгоритм, выводящий Робота из коридора.
5. Робот внутри тупика неизвестного направления. Составьте алгоритм, выводящий Робота из тупика.
6. Робот на перекрестке, от которого отходят один коридор (без боковых выходов) и три тупика. Составьте алгоритм, после выполнения которого, Робот окажется с противоположной стороны коридора.