Алгоритмы и исполнители

1. Алгоритмы и исполнители................................................................................................... 3

2 Что такое алгоритм?............................................................................................................. 3

2 Исполнители......................................................................................................................... 3

2 Старинные задачи................................................................................................................ 5

2 Какие бывают алгоритмы?.................................................................................................. 5

2 Программы............................................................................................................................ 6

2 Задача о перевозчике........................................................................................................... 7

2 Ханойские башни (рекурсивные алгоритмы)................................................................... 8

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

2 Среда Робота....................................................................................................................... 10

2 Основные команды Робота............................................................................................... 10

2 Простейшая программа (задача z1-3.maz)........................................................................ 11

2 Какие ошибки могут быть у Робота?............................................................................... 11

2 Работа в системе Исполнители......................................................................................... 11

2 Задачи.................................................................................................................................. 12

3. Циклы..................................................................................................................................... 14

2 Что такое цикл (задача z2-3.maz)?.................................................................................... 14

2 Правила использования оператора цикла....................................................................... 14

2 Вложенные циклы (задача z3-3.maz)................................................................................ 15

4. Алгоритмы с обратной связью.......................................................................................... 16

2 Что такое обратная связь и зачем она нужна?................................................................. 16

2 Как Робот использует обратную связь?........................................................................... 16

2 Цикл с условием................................................................................................................. 17

2 Правила использования цикла пока............................................................................... 17

2 Задачи.................................................................................................................................. 20

5. Условный оператор............................................................................................................. 21

2 Что такое условный оператор (задача z5-3.maz)?........................................................... 21

2 Правила использования условного оператора................................................................ 22

2 Сокращенная форма........................................................................................................... 22

2 Что такое сложные условия (задача z6-3.maz)?............................................................... 23

2 Правила использования сложных условий..................................................................... 23

6. Переменные и арифметические выражения................................................................... 25

2 Зачем нужны переменные (задача z7-3.maz)?................................................................. 25

2 Что такое переменная?....................................................................................................... 26

2 Объявление переменных................................................................................................... 26

2 Правила работы с переменными...................................................................................... 27

2 Арифметические выражения............................................................................................ 28

2 Цикл с параметром............................................................................................................. 29

2 Задачи.................................................................................................................................. 30

7. Диалоговые программы..................................................................................................... 31

2 Что такое диалоговая программа?.................................................................................... 31

2 Вывод на экран (задача z8-3.maz)..................................................................................... 31

2 Правила использования оператора вывода..................................................................... 32

2 Ввод данных....................................................................................................................... 32

2 Правила использования оператора ввода........................................................................ 33

2 Задачи.................................................................................................................................. 33

2 Вычисления с циклами...................................................................................................... 34

2 Задачи.................................................................................................................................. 35

8. Процедуры............................................................................................................................. 36

2 Зачем нужны процедуры?................................................................................................. 36

2 Как ввести новую команду (задача z10-3.maz)?.............................................................. 36

2 Правила использования процедур................................................................................... 38

2 Процедуры с параметрами (задача z11-3.maz)................................................................ 39

2 Правила использования процедур с параметрами......................................................... 40

9. Методы составления программ......................................................................................... 42

2 Метод “сверху вниз”.......................................................................................................... 42

2 Метод “снизу вверх”.......................................................................................................... 42

2 Комбинированный способ................................................................................................ 43

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

10. Исполнитель Черепаха.................................................................................................... 48

2 Как работает Черепаха?..................................................................................................... 48

2 Какие команды понимает Черепаха?............................................................................... 48

2 Как управлять Черепахой?................................................................................................ 48

2 Как раскрасить рисунок?................................................................................................... 48

2 Окружности........................................................................................................................ 49

2 Циклы.................................................................................................................................. 50

2 Вложенные циклы............................................................................................................. 51

2 Процедуры.......................................................................................................................... 51

2 Процедуры с параметрами................................................................................................ 54

2 Переменные........................................................................................................................ 57

11. Исполнитель Чертежник................................................................................................ 62

2 Прямоугольная система координат.................................................................................. 62

2 Как управлять Чертежником?........................................................................................... 62

2 Использование процедур.................................................................................................. 64

2 Процедуры с параметрами................................................................................................ 65

2 Циклы и переменные......................................................................................................... 66

2 Сравнение Чертежника и Черепахи................................................................................. 67

2 Переменные и использование памяти............................................................................. 68

2 Цикл с параметром............................................................................................................. 69

2 Задачи.................................................................................................................................. 70

1. Алгоритмы и исполнители

2 Что такое алгоритм?

“Прежде, чем что-нибудь сделать, надо составить план”, — говорила Алиса из сказки Льюиса Кэрролла. И в жизни мы все время составляем планы наших действий, например, утром большинство из нас действует по такому плану:

встать

одеться

умыться

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

выйти из дома в школу или на работу

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

В информатике план действий называют алгоритмом. Алгоритм состоит из отдельных шагов – команд. Ни одну из них нельзя пропустить, чаще всего никакие команды нельзя поменять местами (что при этом произойдет?).

Для каждого шага этого алгоритма можно предложить более подробный план. Например, для действия “ позавтракать ”:

вскипятить чайник

сделать бутерброд

съесть бутерброд с чаем

вымыть посуду

И тут каждый шаг, в свою очередь, тоже можно расшифровать – составить более подробный план. Где же остановиться? Ответ прост – это зависит от исполнителя — того, кто будет выполнять этот алгоритм. Надо остановиться на таком плане, в котором исполнителю будет понятно, как выполнить каждый шаг.

2 Исполнители

4 Что такое исполнитель?

Исполнители часто встречаются в сказках. В одной из них Иван-Царевич говорит Избушке-На-Курьих-Ножках: “Избушка, избушка! Встань к лесу задом, ко мне передом!”. При этом команда должна быть задана очень точно, чтобы исполнитель ее понял. В сказке “Али-Баба и сорок разбойников” волшебная дверь открывалась по команде “Сезам, откройся!”. Жадный Касым, тайно проникший в пещеру, забыл эту фразу и не смог выйти из пещеры.

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

¨ Исполнитель – это тот, кто умеет понимать и выполнять некоторые команды.

¨ Среда исполнителя – это предметы, которые окружают исполнителя и с которыми он работает.

¨ Список (или система) Команд Исполнителя (СКИ) – набор команд, понятных исполнителю. Исполнитель может выполнить только те команды, которые входят в его СКИ.

Исполнителями могут быть

· люди: ученик, рабочий, учитель, бригада;

· животные: дрессированная собака (санитар, розыскная, охотничья), кошка;

· машины: станки, роботы, компьютеры;

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

Человек как исполнитель отличается от всех остальных исполнителей несколькими признаками, например:

1. Понимает команды в различных вариантах (например “Сядь!”, “Садись!”, “Присядь!”).

2. Выполняя команды, «додумывает» их с учетом своего опыта.

3. Может отказаться исполнять команду, если она ему не нравится (“Ешь манную кашу!”, “Выстрели в окно из рогатки!”). То есть человек обладает волей и отвечает за свои действия.

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

¨ Алгоритм – это точно определенный план действий исполнителя, направленный на решение какой-то задачи. В алгоритм можно включать только те команды, которые есть в СКИ исполнителя.

4 Ошибки при работе исполнителей

Работа исполнителя не всегда проходит гладко – иногда встречаются ошибки. Существует три вида ошибок исполнителей.

4 Как ввести нового исполнителя?

Введем теперь нового исполнителя, которого назовем дядя Федор (как у Э. Успенского). Чтобы ввести нового исполнителя надо:

· задать среду исполнителя – класс, столы, стулья;

· составить СКИ:

à ВСТАНЬ

à СЯДЬ

à ПОДНИМИ РУКУ

à ОПУСТИ РУКУ

à ПРЫГНИ

à МЯУКНИ

· определить, как передаются команды исполнителю (голосом, жестом, письменно, по рации или как-то иначе);

· определить, как исполнитель выполняет команды;

· определить, в каких случаях возникает ошибка “НЕ МОГУ”.

2 Старинные задачи

Переправа. Крестьянину надо переправить через реку волка, козу и капусту. Но кроме человека лодка вмещает только или волка, или козу, или капусту. Оставить на берегу без присмотра волка с козой или козу с капустой нельзя (съедят!). Как крестьянину переправить свой груз?

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

Фальшивые монеты. Из 9 монет одинакового достоинства одна фальшивая (более легкая). Как ее найти за два взвешивания с помощью чашечных весов без гирь?

2 Какие бывают алгоритмы?

4 Линейный алгоритм

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

вскипятить воду

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

насыпать заварку

залить заварку кипятком

закрыть чайник чем-нибудь теплым

подождать 5 минут

... теперь можно пить чай

4 Разветвляющийся алгоритм

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

подойти к пешеходному переходу

если есть светофор, то

ждать зеленого света

перейти улицу

иначе

ждать, пока слева не будет машин

перейти улицу до середины

ждать, пока справа не будет машин

перейти вторую половину улицы

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

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

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

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

2 Программы

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

В формальной записи алгоритма можно использовать только те команды, которые входят в СКИ исполнителя. Кроме того, надо соблюдать специальные правила оформления, которые позволят исполнителю распознать команды и определить последовательность их выполнения.

/* это название алгоритма */

/* эта скобка обозначает начало алгоритма */

посадить репку /*команда заканчивается знаком;*/

вырастить репку;

пытаться вытащить репку;

позвать Бабку; пытаться вытащить репку;

позвать Внучку; пытаться вытащить репку;

позвать Жучку; пытаться вытащить репку;

позвать Кошку; пытаться вытащить репку;

позвать Мышку; вытащить репку;

/* здесь алгоритм заканчивается */

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

4 Правила записи алгоритмов для компьютеров

Алгоритм можно записать разными способами и даже на разных языках. Хотя при этом исполнитель может, конечно, их не понять. Вы знаете, что есть специальные виды исполнителей алгоритмов — компьютеры. Они выполняют программы.

¨ Программа – это алгоритм, записанный в форме, понятной компьютеру.

Существуют специальные правила записи программ для компьютеров. На рисунке вверху страницы их характерные элементы выделены в рамках:

1. любой алгоритм имеет название;

2. алгоритм начинается с открывающей фигурной скобки “ {“ и заканчивается закрывающей фигурной скобкой “ }”; команды, расположенные между этими скобками, называются телом алгоритма;

3. в алгоритм могут входить только те команды, которые есть в СКИ исполнителя;

4. каждая команда заканчивается знаком “ ;”, который обозначает конец команды;

5. для того, чтобы нам было легче разбираться в программах, используют комментарии - текстовые пояснения, которые начинаются знаками /* и заканчиваются знаками */; исполнитель не обращает внимания на комментарии в алгоритме.

2 Задача о перевозчике

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

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

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

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

2 Ханойские башни (рекурсивные алгоритмы)

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

Однако есть страны, где в эту игру играют уважаемые и почтенные старцы. Придумали ее монахи древнего Ханоя (теперь это территория Вьетнама). У них была одна полная пирамидка с 64 кольцами и два пустых стержня. Считалось, что когда все кольца удастся перенести на другой стержень, соблюдая все правила (см. ниже), наступит конец света.

4 Правила игры

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

· за одно действие можно переносить только одно кольцо;

· кольцо можно укладывать либо на свободный стержень, либо на большее кольцо.

Решим сначала самую простую задачу - для пирамидки из двух колец.

Обозначим стержни номерами:

1 левый стержень, на котором находится пирамидка в начале игры

2 средний стержень, вспомогательный

3 правый стержень, на него надо перенести пирамидку

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

	Ханой-2 {   1 à 2;     1 à 3;     2 à 3; }

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

	Ханой-3 { /* переносим два кольца */ /* на второй стержень */ 1 à 3; 1 à 2; 3 à 2; /* переносим большое кольцо */ /* на третий стержень */ 1 à 3; /* переносим два маленьких кольца */ /* со второго на третий */ 2 à 1; 2 à 3; 1 à 3; }

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

Решение для пирамиды из n колец можно записать в таком виде:

Ханой (n, начальный, вспомогательный, конечный)

{

если n > 1, то

Ханой (n-1, начальный, вспомогательный, конечный);

начальный à конечный;

если n > 1, то

Ханой (n-1, вспомогательный, конечный, начальный);

}

Здесь в качестве начального, конечного и вспомогательного можно использовать любые стержни. Алгоритм Ханой фактически предлагает решать задачу для n колец через две задачи для меньшего числа колец (n-1). Такой прием в программировании называется рекурсия.

4 Что такое рекурсия?

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

Теперь мы познакомились с четвертым видом алгоритмов – рекурсивным алгоритмом. Заметим, что для переноса пирамидки из двухколец требуется всего 3 хода, для трех колец – уже 3+1+3=7 ходов, для четырех – 15 и т.д. Можно показать, что для переноса пирамидки из n колец нам потребуется ходов. У монахов древнего Ханоя была пирамидка из 64 колец и они верили, что когда удастся перенести всю пирамидку на третий стержень, наступит конец света. Конечно это легенда, но число в самом деле очень велико и для того, чтобы сделать столько ходов, не хватит нескольких человеческих жизней.

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

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

2 Среда Робота

Учебный исполнитель Робот предназначен для того, чтобы без участия человека сажать цветы в подготовленные для них грядки. В программе, с которой вы будете работать, Робот изображен в виде машинки, которая ездит по полю. Поле размечено на квадраты, каждый из которых может быть: 1) свободным местом ; 2) грядкой или 3) стенкой . Робот может переходить из клетки в клетку по грядкам или по свободным клеткам, ходить по клумбам с цветами запрещается. Он должен посадить цветы на всех грядках и вернуться на Базу, обозначенную значком , для пополнения запасов.

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

2 Основные команды Робота

Как и любой исполнитель, Робот понимает только ограниченный набор команд, которые входят в его СКИ (список команд исполнителя). Пока нам хватит нескольких команд, перечисленных ниже:

¨ СКИ Робота:

направо; повернуться на 90 градусов вправо

налево; повернуться на 90 градусов влево

кругом; развернуться кругом (на 180 градусов)

вперед (n); перейти на n клеток вперед

назад (n); перейти на n клеток назад

посади; посадить цветы на грядке в том месте, где стоит Робот

Позже мы немного расширим СКИ и добавим в него новые команды. Робот не может ходить по диагонали, проходить сквозь стенки и топтать цветы на клумбах.

2 Простейшая программа (задача z1-3.maz)

ТриКлумбы { вперед(3); посади; направо; вперед(2); налево; вперед(2); налево; вперед(1); посади; вперед(2); посади; вперед(1); налево; вперед(1); }

Имя программы должно состоять из одного «слова», обратите внимание, что внутри нет пробелов. Каждая команда заканчивается точкой с запятой. Можно записывать несколько команд в одну строчку.

2 Какие ошибки могут быть у Робота?

1. Синтаксические (“НЕ ПОНИМАЮ”) – появляются при ошибках в написании команд, например

в лево;

впере т (3);

направо (2);

2. Отказы (“НЕ МОГУ”) – появляются, например, если Роботу приказывают идти прямо на стенку или сажать цветы там, где нет грядки.

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

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

2 Работа в системе Исполнители

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

Окно состоит из трех частей: верху расположены меню и кнопки для управления исполнителем, слева – редактор программы, а справа – поле исполнителя.

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

Затем надо набрать программу в поле редактора. Для того, чтобы ускорить ввод команд, удобно использовать меню Шаблоны. Там есть все команды языка программирования и команды исполнителя Робот.

Для того, чтобы компьютер выровнял все строки программы (привел программу в «приличный» вид), можно нажать клавишу F6 или щелкнуть по кнопке на панели инструментов.

Когда программа готова, запишите ее на диск, нажав клавишу F2 или кнопку на панели инструментов. В ответ на это при первой записи файла на диск появляется окно для ввода имени файла, где вам надо ввести любое имя и затем щелкнуть на кнопку ОК. При записи файла в следующий раз имя уже известно, поэтому система переименует старую версию, сделав у нее расширение * .bak, а новую запишет с тем же именем.

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

Если ошибки есть, красным цветом будет выделена строка, в которой обнаружена ошибка, и выведено сообщение на экран. Посмотрите внимательно на эту строку и на предыдущую, нажмите на клавишу Enter и исправьте ошибку.

Если ошибок нет, но Робот не выполнил задание, в программе есть логическая ошибка. Для ее обнаружения воспользуйтесь режимом отладки: при нажатии на клавишу F8 исполнитель выполняет одну строку программы и останавливается. Такой режим называется пошаговым. Таким образом, можно определить, в какой строчке программа начинает выполняться не так, как вам хочется. Обнаружив ошибку, нажмите клавишу Esc для выхода из режима отладки. Когда все получилось, запишите новый вариант на диск и закончите работу, щелкнув по кнопке в правом верхнем углу окна или нажав клавиши Alt+F4.

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

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

2 Задачи

1. Определите, чего не хватает в условии этой задачи. Дополните условие и решите задачу.

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

3.Известна программа перехода Робота из одной клетки в другую. Составить программу обратного хода Робота.

4. Перевести Робота на Базу всеми возможными способами из трех команд. Можно ли сделать это в 2 шага (в 5 шагов? 10 шагов? 15 шагов? 1991 шаг?).

5. Составить и решить свою задачу для Робота (придумать интересное название).

3. Циклы

2 Что такое цикл (задача z2-3.maz)?

Часто исполнителю надо выполнить какую-то последовательность команд несколько раз. Например, в задаче на рисунке Робот должен подойти к ряду клеток, которые надо закрасить, и затем выполнить 6 раз команды вперед(1) и посади.

В данном случае эти команды надо повторить только 6 раза и можно легко 6 раз написать одинаковые команды. Но представьте, что надо сделать одинаковые операции 100 или 200 раз! В программировании в таких случаях используется специальная команда (оператор цикла), которая говорит исполнителю, что какую-то часть программы надо сделать несколько раз.

¨ Цикл — это многократное повторение одинаковых действий

¨ Тело цикла ­ – это команды, которые выполняются несколько раз.

¨ Шаг цикла ­ – это однократное выполнение тела цикла.

Для нашей задачи подходит цикл повтори (или repeat), в котором с известным числом шагов. Программа с использованием оператора цикла выглядит так:

Ряд

{

вперед (1); /* подойти к месту работы */

повтори (6)

{

вперед (1);

посади;

}

}

2 Правила использования оператора цикла

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

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

3. Тело цикла начинается открывающей фигурной скобкой { и заканчивается закрывающей }.

4. Если тело цикла включает всего один оператор, скобки можно не ставить.

5. Для того, чтобы легче разбираться в программе, применяют специальную систему записи с отступами: тело цикла смещают вправо на 2-3 символа — это позволяет сразу видеть, где начинается и где заканчивается цикл. Для того, чтобы компьютер автоматически сделал отступы в программе, можно нажать клавишу F6.

2 Вложенные циклы (задача z3-3.maz)

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

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

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

¨ Вложенный цикл – это такой цикл, который находится внутри другого цикла.

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

4. Алгоритмы с обратной связью

2 Что такое обратная связь и зачем она нужна?

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

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

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

Действие обратной связи можно описать такой схемой:

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

2 Как Робот использует обратную связь?

Робот имеет датчики, которые позволяют ему получать информацию об обстановке. Датчики определяют, например, есть ли стена в каком-то направлении. Чтобы использовать эту информацию в программе, в СКИ Робота есть специальные логические команды.

¨ Логическая команда – это условие, которое может быть верным (истинным) или неверным (ложным).

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

справа_стена справа_клумба справа_свободно

слева_стена слева_клумба слева_свободно

впереди_стена впереди_клумба впереди_свободно

сзади_стена сзади_клумба сзади_свободно

грядка база

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

Пример 1 (задача z4-3.maz). Роботу надо придти на Базу, которая расположена на краю стенки. Расстояние от Робота до стенки и длина стенки неизвестны.

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

1) выдать запрос впереди_свободно;

2) если Робот получил от датчиков ответ “нет”, то он выполнил задание и находится у стены;

3) если получен ответ “да”, то сделать шаг вперед и повторить весь процесс.

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

2 Цикл с условием

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

Тем не менее, есть четкое условие, по которому Робот должен закончить работу: если перед ним оказывается стена. Таким образом, Робот должен выполнять цикл пока впереди свободно. Для этой цели служит специальный вид цикла – цикл пока (или while,от английского while – пока). Такой вид цикла называется циклом с условием, поскольку он заканчивается, когда нарушается условие в заголовке цикла.

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

2 Правила использования цикла пока

1. Цикл пока используется тогда, когда число повторений цикла заранее неизвестно, но ограничено каким-то условием.

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

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

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

5. В цикле выполняются все операторы, заключенные в фигурные скобки;

Если тело цикла включает всего один оператор, скобки можно не ставить.

5. Для того, чтобы легче разбираться в программе, все команды, входящие в цикл, смещают вправо на 2-3 символа – это позволяет сразу видеть, где начинается и где заканчивается цикл.

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

Ничего

{

пока (справа_стена)

вперед (1);

}

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

Пример 3. В этом примере программа для Робота составлена так, что он врежется в стенку и сообщит об ошибке “ НЕ МОГУ ”.

Диверсия { пока (впереди_свободно) { вперед (2); } }

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

Пример 4. Эта программа приводит к зацикливанию, так как условие справа_стена выполняется всегда и Робот не меняет своего места.

Зацикливание { пока (справа_стена) { кругом; кругом; } }

Использование цикла пока позволяет нам решать задачи, в которых некоторые данные (например, длина стенок) заранее неизвестны.

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

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

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

Контур

{

пока (впереди_свободно)

вперед(1); /* подойти к стене */

налево;

пока (справа_стена)

назад(1); /* в левый нижний угол */

}

2 Задачи

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

2. Посадить цветы во всех грядках. Толщина стены – 1 клетка, остальные размеры считать неизвестными. Все размеры считать неизвестными.

5. Условный оператор

2 Что такое условный оператор (задача z5-3.maz)?

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

Словами это можно сформулировать так: если есть проход (условие есть проход выполняется), то выполни одну группу команд, если нет – выполни другие команды. В программе для этой цели используется специальный условный оператор если