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

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

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, переносим два меньших кольца на третий стержень.

В этом алгоритме мы два раза использовали алгоритм Ханой-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)

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

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

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

влево;

вперет ( 3 );

направо ( 2 );

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

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

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

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

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

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

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

Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 4 5