Известны два вспомогательных алгоритма робота узор 1. Исполнитель Робот. Вспомогательные алгоритмы

21.04.2019

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

Рис. 3.11

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

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

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

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

Пример алгоритма управления Роботом

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

Рис. 3.12

Программа может иметь вид:

Здесь мы использовали конструкцию повторения, так как совершенно одинаковые фрагменты повторяются на рисунке 5 раз. При записи тела цикла мы в одной строке через точку с запятой записывали несколько команд.

Если оформить процедуру виток, то основная программа окажется совсем короткой.

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

Цикл «пока»

А теперь попробуем написать программу для решения очень простой задачи: закрасить все клетки справа от Робота (рис. 3.13).

Рис. 3.13

Правда, сколько именно клеток следует закрасить, не уточнено. Известно только, что:

справа на неизвестном расстоянии есть стена;
клетки нужно красить, пока Робот не подойдет к стене вплотную.

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

Ясно, что пока будет выполняться условие справа свободно , нужно выполнять команды:

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

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

Блок-схема цикла «пока» имеет вид, показанный на рис. 3.14.

Рис. 3.14

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

проверяет записанное после служебного слова ПОКА условие;
если условие не соблюдается (Робот ответил «Нет»), то выполнение цикла прекращается, и Робот начинает выполнять команды, записанные после служебного слова КОНЕЦ. Если же условие соблюдается (Робот ответил «Да»), то Робот выполняет тело цикла и снова проверяет условие.

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

Виток меандра умещается на клетчатом поле, если между клеткой, занимаемой Роботом, и правой стеной есть 1 клетка.

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

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

Из-за логических ошибок, допущенных при составлении алгоритма, может возникнуть ситуация зацикливания. Это значит, что условие будет всегда соблюдаться, и выполнение цикла «пока» никогда не завершится.

Рассмотрим следующий пример:

Что будет происходить, если справа от Робота нет стены?

Условие в цикле «пока» проверяется только перед выполнением тела цикла, но не в процессе его выполнения.

Простые и составные условия

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

Составное условие образуется из одного или нескольких простых условий и служебных слов И, ИЛИ, НЕ.

Рассмотрим составное условие А И В, где А, В - простые условия. Условие А И В выполнено, когда выполнено каждое из двух входящих в него простых условий.

Пусть А - простое условие сверху свободно, В - простое условие справа свободно. Рассмотрим подробно проверку составного условия А И В - сверху свободно и справа свободно (рис. 3.15).

Рис. 3.15

В случае а выполнено условие А (сверху свободно), выполнено условие В (справа свободно). Составное условие АИВ (сверху свободно И справа свободно) также выполнено.

В случае б выполнено условие А, условие В не выполнено. Составное условие А И В не выполнено.

В случае в не выполнено условие А, условие В выполнено. Составное условие А И В не выполнено.

В случае г не выполнено условие А, не выполнено условие В. Составное условие А И В не выполнено.

Нужно ли проверять условие В в составном условии А И В, если условие А не выполнено?

Составное условие А ИЛИ В выполнено, когда выполнено хотя бы одно из двух входящих в него простых условий.

Рассмотрим проверку составного условия А ИЛИ В - сверху свободно ИЛИ справа свободно (см. рис. 3.15).

В случае а выполнено условие А (сверху свободно), выполнено условие В (справа свободно). Составное условие А ИЛИ В (сверху свободно ИЛИ справа свободно) выполнено.

В случае б выполнено условие А, не выполнено условие В. Составное условие А ИЛИ В выполнено.

В случае в не выполнено условие А, выполнено условие В. Составное условие А ИЛИ В выполнено.

В случае г не выполнено условие А, не выполнено условие В. Составное условие А ИЛИ В не выполнено.

Нужно ли проверять условие В в составном условии А ИЛИ В, если условие А выполнено?

Составное условие НЕ А выполнено, когда не выполнено условие А.

Пусть А - простое условие закрашено. Рассмотрим проверку составного условия НЕ А (рис. 3.16).

Рис. 3.16

В случае а условие А выполнено, условие НЕ А (НЕ закрашено) не выполнено.

В случае б условие А не выполнено, условие НЕ А (НЕ закрашено) выполнено.

Рассмотрим пример использования составного условия.

Известно, что Робот находится где-то в вертикальном коридоре. Ни одна из клеток коридора не закрашена.

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

Так как Роботу предстоит закрасить только клетки коридора, мы должны «научить» его их распознавать. Чем же клетки коридора отличаются от всех прочих клеток поля? Из рис. 3.17 видно, что каждая клетка коридора слева и справа ограничена стеной.

Рис. 3.17

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

Нужное условие примет вид:

Представим план действий Робота укрупненными шагами (рис. 3.18).

Рис. 3.18

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

1. Чтобы закрасить все клетки коридора, находящиеся выше Робота, прикажем Роботу шагнуть вверх и выполним цикл «пока»:

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

При каком исходном положении Робота этот цикл не выполнится ни разу?

2. Командой вниз вернем Робота в коридор. Наша задача - вернуть его в исходную точку. Эта точка имеет единственный отличительный признак - она не закрашена. Поэтому пока занимаемая Роботом клетка оказывается закрашенной, будем перемещать его вниз:

Под управлением этого алгоритма Робот окажется в исходной клетке.

3. Выполнив команду вниз , Робот пройдет исходную клетку и займет первую клетку, расположенную ниже исходной. Теперь можно закрашивать клетки коридора, расположенные ниже исходной:

Возможна ли ситуация, что этот цикл не выполнится ни разу?

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

5. По команде закрась Робот закрашивает исходную точку.

Полностью программа управления Роботом выглядит так:

Команда ветвления

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

Графически ветвление можно представить, как показано на рис. 3.19.

Рис. 3.19

Для организации ветвлений в СКИ Робота предусмотрена специальная команда ЕСЛИ. Ее общий вид:

Служебные слова ЕСЛИ, ТО, ИНАЧЕ имеют обычный смысл.

Между ТО и ИНАЧЕ записываются одно или несколько действий, составляющих серию действий 1. Между ИНАЧЕ и КОНЕЦ помещается серия действий 2. Служебное слово ИНАЧЕ вместе с серией действий 2 может отсутствовать (сокращенная форма ветвления).

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

Рис. 3.20

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

Рис. 3.21

Программа:

Коротко о главном

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

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

Робот может выполнять цикл «повторить n раз».

Если заранее не известно, сколько именно раз следует выполнить тело цикла, используется специальная конструкция алгоритмического языка - цикл «пока».

В цикле «пока» могут использоваться не только простые, но и составные условия. Составное условие образуется из одного или нескольких простых условий и служебных слов И, ИЛИ, НЕ.

Для организации ветвлений в СКИ Робота предусмотрена специальная команда ЕСЛИ.

Вопросы и задания

| §2.3 Конструирование алгоритмов

Урок 15
§2.3 Конструирование алгоритмов

2.3.1. Последовательное построение алгоритма

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

Процесс последовательного построения алгоритма выглядит следующим образом.

На первом шаге мы считаем, что перед нами совершенный исполнитель, который «всё знает и всё умеет». Поэтому достаточно определить исходные данные и результаты алгоритма, а сам алгоритм представить в виде единого предписания - постановки задачи (рис. 2.4).

Рис. 2.4. Линейный алгоритм, являющийся результатом первого этапа детализации задачи

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

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

Процесс продолжается до тех пор, пока все предписания не будут понятны исполнителю.

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

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

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

Система команд исполнителя Робот:

В одном условии можно использовать несколько команд, применяя логические операции И, ИЛИ, НЕ.

Известно, что Робот находится где-то в горизонтальном коридоре. Ни одна из клеток коридора не закрашена.

Составим алгоритм, под управлением которого Робот закрасит все клетки этого коридора и вернётся в исходное положение.

Представим план действий Робота следующими укрупнёнными шагами (модулями):

Детализируем каждый из пяти модулей.

1. Чтобы закрасить все клетки коридора, находящиеся левее Робота, прикажем Роботу шагнуть влево и выполнить цикл - ПОКА:

влево
нц пока сверху стена и снизу стена закрасить; влево
кц

Под управлением этого алгоритма Робот закрасит все клетки коридора, находящиеся левее от него, и окажется в клетке левее коридора.

2. Командой вправо вернём Робота в коридор. Наша задача - вернуть Робота в исходную клетку. Эта клетка - первая незакрашенная клетка, находящаяся правее Робота. Поэтому пока занимаемая Роботом клетка оказывается закрашенной, будем перемещать его вправо.

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

Под управлением этого алгоритма Робот окажется в исходной клетке.

3. Выполнив команду вправо, Робот пройдёт исходную клетку и займёт клетку правее исходной. Теперь можно закрашивать клетки коридора, расположенные правее исходной.

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

4. Так как, выполнив предыдущий алгоритм, Робот оказался правее коридора, командой влево вернём его в коридор. Возвращение в исходную клетку обеспечивается алгоритмом:

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

5. По команде закрасить Робот закрашивает исходную клетку. Полностью программа управления Роботом выглядит так:

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

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

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

Пример 1 . В среде КуМир составим алгоритм для исполнителя Робот, под управлением которого он нарисует узор:

Начальное положение Робота отмечено звёздочкой. В алгоритме использован вспомогательный алгоритм фигура.

При представлении алгоритмов с помощью блок-схем для обозначения команды вызова вспомогательного алгоритма используется блок «предопределённый процесс» (рис. 2.5), внутри которого записывается название (имя) вспомогательного алгоритма, после которого в скобках перечисляются параметры - входные данные и результаты.

Рис. 2.5. Блок «предопределённый процесс»

Вспомогательный алгоритм делает структуру алгоритма более понятной.

Пример 2 . Вспомним алгоритм вычисления степени с натуральным показателем у = а n . Соответствующая блок-схема:

Степень с целым показателем у = а х, где х - целое число, а ≠ 0 вычисляется так:

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

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

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

Команда вызова вспомогательного алгоритма исполняется следующим образом (рис. 2.6):

1) формальные входные данные вспомогательного алгоритма заменяются значениями фактических входных данных, указанных в команде вызова вспомогательного алгоритма;
2) для заданных входных данных исполняются команды вспомогательного алгоритма;
3) полученные результаты присваиваются переменным с именами фактических результатов;
4) осуществляется переход к следующей команде основного алгоритма.

Рис. 2.6. Схема выполнения команды вызова вспомогательного алгоритма

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

Рассмотрим несколько примеров рекурсивных алгоритмов.

Пример 3 . Алгоритм вычисления степени с натуральным показателем п для любого вещественного числа а можно представить в виде рекурсивного:

Число а в степени n (n-я степень числа а) есть не что иное, как произведение а n-1 а; в свою очередь, а n-1 = а n-2 а и т. д.

Пример 4 . Рекурсивный алгоритм положен в основу эффективного решения головоломки «Ханойская башня».

Интерактивная игра «Ханойские башни» (195747) поможет вам вспомнить условие и алгоритм решения головоломки (http://sc.edu.ru/).

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

С каждым шагом фигура становится всё причудливее. Граница снежинки Коха - положение кривой после выполнения бесконечного числа шагов.

САМОЕ ГЛАВНОЕ

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

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

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

Вопросы и задания

1. Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику. Дополняет ли презентация информацию, содержащуюся в тексте параграфа?

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

3. В чём заключается метод последовательного уточнения при построении алгоритма?

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

5. Известен рост каждого из n учеников 9А класса и m учеников 9Б класса. Опишите укрупнёнными блоками алгоритм сравнения среднего роста учеников этих классов.

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

7. Для чего нужны вспомогательные алгоритмы?

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

9. Сталкивались ли вы с идеей формальных и фактических параметров при изучении математики и физики? Приведите пример.

10. Какие алгоритмы называют рекурсивными? Приведите пример рекурсии из жизни.

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

Управление исполнителем Робот в системе КУМИР

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

Робот занимает ровно одну клетку поля.

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

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

О
шибки: 1 синтаксические; 2. логические

Описания обстановок хранятся в текстовых файлах специального формата (формат.fil).

Текущая - обстановка, в которой находится Робот в данный момент (включая информацию о положении Робота).

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

Порядок работы:

Задать стартовую обстановку по условию задачи:

Меню Инструменты → Сменить стартовую обстановку Робота (нарисовать обстаковку по условию задачи, дать имя, сохранить в Личной папке)

2. Указать Исполнителя:

Меню Вставка →Использовать Робот

3. Написать алгоритм решения задачи.

4. Выполнить алгоритм (Меню Выполнение →Выполнить непрерывно /F9)

Система команд исполнителя Робот в системе КУМИР

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

Циклические алгоритмы

Цикл – организация повторения действий, пока верно некоторое условие.

Тело цикла – набор повторяемых действий.

Условие – логическое выражение (простое или сложное (составное))
Типы циклов:

1.Цикл «Повторять n раз» 2. Цикл «Пока»
нц n раз нц пока
. . Тело цикла. . Тело цикла
кц кц

Пример: нц пока справа свободно

Общий вид цикла «Повторять n раз:

ПОВТОРИТЬ n РАЗ

КОНЕЦ
кц

Общий вид цикла «пока»:

ПОКА ДЕЛАТЬ

КОНЕЦ
Составные условия образуются из одного или нескольких простых условий и служебных слов И, ИЛИ, НЕ.

Составное условие А И В (где А, В - простые условия), выполнено, когда выполнено каждое из двух входящих в него простых условий.

Пусть А - сверху свободно, В - справа свободно, тогда составное условие А И В - сверху свободно И справа свободно.

Составное условие А ИЛИ В выполнено, когда выполнено хотя бы одно из двух входящих в него простых условий: сверху свободно ИЛИ справа свободно
Составное условие НЕ А - выполнено, когда не выполнено условие А.

Пример: Пусть А – клетка закрашена (простое условие).

Проверка составного условия НЕ А:

а) А - выполнено, НЕ А (НЕ закрашено) - не выполнено.

б) А - не выполнено, НЕ А (НЕ закрашено) - выполнено.

Команда ветвления

Ветвление - форма организации действий, при которой в зависимости от выполнения или невыполнения некоторого условия совершается либо одна, либо другая последовательность действий.

Общий вид команды ЕСЛИ:

ЕСЛИ ТО ИНАЧЕ

КОНЕЦ

В языке КУМИР:

Полное ветвление: Неполное ветвление:
если то если то

иначе

все все

Вспомогательный алгоритм - алгоритм, решающий некоторую подзадачу основной задачи.

В системе КУМИР вспомогательные алгоритмы пишутся в конце основной программы (после служебного слова кон ), вызываются на выполнение в основой программе по имени.

Вопросы и задания

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

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

а) два шага; б) четыре шага; в) пять шагов; г) семь шагов?

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

7. Известны два вспомогательных алгоритма Робота

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

а)

нц 5 раз

узор_1

вправо; вправо;

б)

нц 7 раз

узор_2

вправо; вправо

в)
вправо; вправо; вправо

вверх; вверх

вправо; вправо; вправо

вниз; вниз

г)
вправо; вправо
вправо; вправо

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

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

10. Известно, что где-то правее Робота есть закрашенная клетка.

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

11. Известно, что Робот находится рядом с левым входом в горизонтальный коридор.

12. Известно, что Робот находится где-то в горизонтальном коридоре. Ни одна из клеток коридора не закрашена.

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

13. В ряду из десяти клеток правее Робота некоторые клетки закрашены.

Составьте алгоритм, который закрашивает клетки:

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

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

14. Что можно сказать о правильности следующего фрагмента алгоритма?

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

ЕСЛИ справа свободно ТО

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

к
ц

15. Напишите программу, с помощью которой Робот сможет попасть в клетку Б во всех трех лабиринтах.

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

З

адачи ГИА

Коридор1. Робот находится где-то в вертикальном коридоре. Ни одна из клеток коридора не закрашена. Составить алгоритм, под управлением которого Робот закрасит все клетки этого коридора и вернется в исходное положение.

К
Надо
Дано
оридор2. Робот находится в верхней клетке узкого вертикального коридора. Ширина коридора – одна клетка, длина коридора может быть произвольной.

Возможный вариант начального расположения Робота приведён на рисунке (Робот обозначен буквой «Р»)

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

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

Надо

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

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

На бесконечном поле имеется длинная вертикальная стена. Длина стены неизвестна. Робот находится в одной из клеток, расположенной непосредственно справа от стены. Начальное положение робота также неизвестно. Одно из возможных положений робота приведено на рисунке (робот обозначен буквой «Р»):Напишите для работа алгоритм, закрашивающий все прилегающие к стене клетки: слева, начиная с верхней не закрашенной и через одну; справа, начиная с нижней закрашенной и через одну. Робот должен закрасить только клетки, удовлетворяющие данному условию. Например, для приведенного выше рисунка робот должен закрасить следующие клетки (см. рисунок): Конечное расположение робота может быть произвольным. Алгоритм должен решать задачу для произвольного размера стены и любой допустимой начальной позиции робота. При исполнении алгоритма Робот не должен разрушиться.

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

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

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



		Р

На бесконечном поле имеется длинная вертикальная стена. Длина стены неизвестна. Робот находится в одной из клеток, расположенной непосредственно слевав от стены. Начальное положение робота также неизвестно. Одно из возможных положений робота приведено на рисунке (робот обозначен буквой «Р»):

Напишите для работа алгоритм, закрашивающий все прилегающие к стене клетки:

слева все;
справа, начиная с верхней незакрашенной и через одну.

Робот должен закрасить только клетки, удовлетворяющие данному условию.

B
1102_ГИА2011

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

Конечное расположение робота может быть произвольным. Алгоритм должен решать задачу для произвольного размера поля и любого допустимого расположения стен внутри прямоугольного поля. При исполнении алгоритма Робот не должен разрушиться.

В
1103_ГИА_2011

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

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

обобщение и систематизация знаний по теме Алгоритмы,
формирование навыков практического применения знаний;

воспитательная:

воспитание ответственности, самостоятельности, самооценки, аккуратности при выполнении работы;
повышение информационной культуры учащихся;

развивающая:

формирование и развитие у учащихся познавательных интересов;
развитие умения оперировать ранее полученными знаниями, сопоставлять, анализировать, делать выводы.

Тип урока: комбинированный.

Оборудование:

проектор,
компьютерный класс

План урока

Организационный момент - 2 мин.
Актуализация знаний - 8 мин.
Объяснение материала и выполнение упражнений - 20 мин.
Закрепление материала - 10 мин.
Вопросы учеников, ДЗ, подведение итогов урока –5 мин.

Ход урока
Организационный момент
Приветствие, проверка присутствующих.
На предыдущих уроках мы говорили об алгоритмах, рассматривали их типы, виды, свойства, составляли алгоритмы для решения разных задач. Сегодня мы будем использовать алгоритмы для управления исполнителями. И для начала вспомним, что же такое «исполнитель».
Актуализация знаний
Учащиеся отвечают на следующие вопросы:

Определите понятие Исполнитель. Приведите примеры.
Чем формальный исполнитель отличается от неформального? Приведите примеры.
Что такое СКИ? Назовите СКИ Калькулятор.
Какие требования накладываются на алгоритмы, предназначенные для выполнения исполнителем?

Объяснение нового материала с использование проектора
Среда исполнителя Робот – клетчатое поле, ограниченное стеной. Внутри поля между некоторыми клетками также может быть стена. Исполнитель Робот может перемещаться на одну клетку с помощью команд перемещения вправо, влево, вверх, вниз . Также он может закрашивать клетки, на которых стоит, командой закрась . Если между клетками стена, то Робот не может ее пройти. Команды проверки отсутствия стены и закрашенности клетки: сверху свободно, снизу свободно, справа свободно, слева свободно, закрашено (рис. 1).
Упражнения :

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

В окончательном варианте алгоритм выполнения этой задачи будет выглядеть так:
Повторить 5 раз
вверх; вверх; вправо; вниз; вниз; вправо
конец
Упражнения (рис. 5).
А теперь рассмотрим следующую задачу: закрасить все клетки до стены справа от Робота при условии, что количество клеток до стены неизвестно (рис. 6). В этом случае воспользуемся алгоритмической конструкцией Цикл-после (т.е. цикл выполняется после проверки условия).

Рис. 5

Рис. 6

Упражнение: в предыдущей задаче нужно закрасить все клетки справа от Робота и вернуться в исходное положение.
Ответ: нц пока справа свободно
вправо
закрась
кц
нц пока закрашено
влево
кц
Составные условия образуются из одного или нескольких простых условий и служебных слов И, ИЛИ, НЕ. Чтобы составное условие, объединяющее простые условия логической связкой ИЛИ было истинным, достаточно истинности одного из простых условий, входящих в него. Чтобы составное условие, объединяющее простые условия логической связкой И было истинным, необходимо, чтобы истинны были все простые условия, входящие в него (рис. 7).

Рис. 7

Рис. 8

Закрепление материала
Задания выполняются в рабочих тетрадях с последующим обсуждением предложенных учащимися решений.
Задание 1. Используя команды повторить и пока перевести Робота из исходного положения в точку Б, если количество клеток по вертикали и длина стен в лабиринте неизвестны (рис. 8).
Ответ: повторить 5 раз
нц пока не справа свободно
вверх
кц
вправо
нц пока не справа свободно
вниз
кц
вправо
конец
Задание 2. Известно, что Робот находится рядом с входом в коридор (длина коридора неизвестна). Составить алгоритм для закрашивания Роботом всех клеток коридора и возвращения его в исходное положение (рис. 9).
Ответ: вправо
нц пока не сверху свободно и не снизу свободно
закрась
вправо
кц
влево
нц пока закрашено
влево
кц

Рис. 9

Рис. 10

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

Литература:
1. Л Босова. Информатика и ИКТ. Учебник для 7 класса. М., Бином, Лаборатория знаний, 2010.
2. А.Г. Кушниренко, Г.В. Лебедев, Я.Н. Зайдельман. Информатика 7-9 кл. М., Дрофа, 2003.

Дополнительно:

Демонстрационный материал к уроку информатики в 9 классе «Составление циклических алгоритмов для исполнителя Робот» (14 слайдов)

Слайд 1

Слайд 3

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

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

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

Пример алгоритма управления Роботом

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

Программа может иметь вид:

ПОВТОРИТЬ 5 РАЗ
вправо
закрась; влево
закрась; влево
закрась; вверх
закрась; вверх
закрась; вправо; закрась
вправо; вправо; вправо
вниз; вниз
КОНЕЦ

Здесь мы использовали конструкцию повторения, так как совершенно одинаковые фрагменты повторяются на рисунке 5 раз. При записи тела цикл а мы в одной строке через точку с запятой записывали несколько команд.

Если оформить процедуру виток, то основная программа окажется совсем короткой.

Вспомогательный алгоритм:
ПРОЦ виток
НАЧАЛО
вправо
закрась; влево
закрась; влево
закрась; вверх
закрась; вверх
закрась; вправо; закрась
вправо; вправо; вправо
вниз; вниз
КОНЕЦ

Основной алгоритм:
ПОВТОРИТЬ 5 РАЗ
виток
КОНЕЦ

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

Цикл «пока»

Правда, сколько именно клеток следует закрасить, не уточнено. Известно только, что:

1) справа на неизвестном расстоянии есть стена;
2) клетки нужно красить, пока Робот не подойдет к стене вплотную.

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

Ясно, что пока будет выполняться условие справа свободно, нужно выполнять команды:

вправо
закрась

ПОКА справа свободно ДЕЛАТЬ
вправо
закрась
КОНЕЦ

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

ПОКА <условие> ДЕЛАТЬ
<тело цикла (последовательность команд)>
КОНЕЦ

Блок-схема цикла «пока» имеет вид, показанный на рис. 3.14.

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

1) проверяет записанное после служебного слова ПОКА условие;

2) если условие не соблюдается (Робот ответил «Нет»), то выполнение цикла прекращается, и Робот начинает выполнять команды, записанные после служебного слова КОНЕЦ. Если же условие соблюдается (Робот ответил «Да»), то Робот выполняет тело цикла и снова проверяет условие.

ПОКА справа свободно ДЕЛАТЬ
вправо
закрась; влево
закрась; влево
закрась; вверх
закрась; вверх
закрась вправо; закрась
вправо; вправо; вправо
вниз; вниз
КОНЕЦ

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

Рассмотрим следующий пример:

ПОКА справа свободно ДЕЛАТЬ
вправо; влево
КОНЕЦ

Что будет происходить, если справа от Робота нет стены?

Условие в цикле «пока» проверяется только перед вы полнением тела цикла, но не в процессе его выполнения.

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

Что общего у циклов «повторить п раз» и «пока»? Какие между ними отличия? Нужны ли две конструкции для описания повторяющихся действий?

Простые и составные условия

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

Составное условие образуется из одного или нескольких простых условий и служебных слов И, ИЛИ, НЕ.

Пусть А - простое условие справа свободно, В - простое условие справа свободно. Рассмотрим подробно проверку составного условия А И В - сверху свободно. (рис. 3.15).

В случае а выполнено условие А (сверху свободно), выполнено условие В (справа свободно). Составное условие А И В(сверху свободно И справа свободно)также выполнено.

В случае б выполнено условие А, условие В не выполнено. Составное условие А И В не выполнено.

В случае в не выполнено условие А, условие В выполнено. Составное условие А И В не выполнено.

В случае г не выполнено условие А, не выполнено условие В. Составное условие А И В не выполнено.

Нужно ли проверять условие В в составном условии АИВ, если условие А не выполнено?

Составное условие А ИЛИ В выполнено, когда выполнено хотя бы одно из двух входящих в него простых условий.

Рассмотрим проверку составного условия А ИЛИ В - сверху свободно ИЛИ справа свободно (см. рис. 3.15).

В случае б выполнено условие А, не выполнено условие В. Составное условие А ИЛИ В выполнено.

В случае в не выполнено условие А, выполнено условие В. Составное условие А ИЛИ В выполнено.

В случае г не выполнено условие А, не выполнено условие В. Составное условие А ИЛИ в не выполнено.

Нужно ли проверять условие В в составном условии А ИЛИ В, если условие А выполнено?

Составное условие НЕ А выполнено, когда не выполнено условие А.

Пусть А - простое условие закрашено. Рассмотрим проверку составного условия НЕ А (рис. 3.16).

В случае а условие А выполнено, условие НЕ А (НЕ закрашено) не выполнено.

В случае б условие А не выполнено, условие НЕ А (НЕ закрашено) выполнено.

Рассмотрим пример использования составного условия.

Известно, что Робот находится где-то в вертикальном коридоре. Ни одна из клеток коридора не закрашена.

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

слева стена -> НЕ слева свободно
справа стена -> НЕ справа свободно

Нужное условие примет вид:
НЕ слева свободно И НЕ справа свободно.

Представим план действий Робота укрупненными шагами (рис. 3.18).

вверх
ДЕЛАТЬ
закрась
вверх
КОНЕЦ

При каком исходном положении Робота этот цикл не выполнится ни разу?

2. Командой вниз вернем Робота в коридор. Наша задача - вернуть его в исходную точку. Эта точка имеет единственный отличительный признак - она не закрашена. Поэтому пока занимаемая Роботом клетка оказывается закрашенной, будем перемещать его вниз:

вниз
ПОКА закрашено ДЕЛАТЬ
вниз
КОНЕЦ

Под управлением этого алгоритма Робот окажется в исходной клетке.

3. Выполнив команду вниз, Робот пройдет исходную клетку и займет первую клетку, расположенную ниже исходной. Теперь можно закрашивать клетки коридора, расположенные ниже исходной:

вниз
ПОКА НЕ слева свободно И НЕ справа свободно
ДЕЛАТЬ
закрась
вниз
КОНЕЦ

Возможна ли ситуация, что этот цикл не выполнится ни разу?

вверх
ПОКА закрашено ДЕЛАТЬ
вверх
КОНЕЦ

5. По команде закрась Робот закрашивает исходную точку.

Полностью программа управления Роботом выглядит так:

вверх
ПОКА НЕ слева свободно И НЕ справа свободно
ДЕЛАТЬ
закрась
вверх
КОНЕЦ
вниз
ПОКА закрашено ДЕЛАТЬ
вниз
КОНЕЦ
вниз
ПОКА НЕ слева свободно И НЕ справа свободно
ДЕЛАТЬ
закрась
вниз
КОНЕЦ
вверх
ПОКА закрашено ДЕЛАТЬ
вверх
КОНЕЦ
закрась

Команда ветвления

Графически ветвление можно представить, как показано на рис. 3.19.

Для организации ветвлений в СКИ Робота предусмотрена специальная команда ЕСЛИ. Ее общий вид:

ЕСЛИ <условие> ТО <серия действий 1>
ИНАЧЕ <серия действий 2>
КОНЕЦ

Служебные слова ЕСЛИ, ТО, ИНАЧЕ имеют обычный смысл.

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

Программа:

ПОКА НЕ снизу свободно ДЕЛАТЬ
ЕСЛИ сверху свободно ТО
закрась
КОНЕЦ
вправо
КОНЕЦ

Коротко о главном

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

Робот может выполнять цикл «повторить n раз».

Для организации ветвлений в СКИ Робота предусмотрена специальная команда ЕСЛИ.

Вопросы и задания

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

Существует ли для этой задачи алгоритм, при выполнении которого Робот делает: а) два шага; б) четыре шага; в) пять шагов; г) семь шагов; д) 2001 шаг; е) 2006 шагов?

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

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

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

5. Напишите программу, с помощью которой Робот сможет попасть в клетку Б во всех трех лабиринтах.