Программа по формированию навыков безопасного поведения на дорогах и улицах «Добрая дорога детства» 2

Алгоритмы и исполнители © К.Поляков, 1992-2010

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



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

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

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

встать

одеться

умыться

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

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

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

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

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

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

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

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

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

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

Исполнители

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

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

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

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

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

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

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

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

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

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

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

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

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

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

“НЕ ПОНИМАЮ”	Заданной команды нет в списке команд исполнителя, и он ее не понял. Вероятно, мы ошиблись в записи текста команды.
“НЕ МОГУ”	Исполнитель понял команду, но не может ее выполнить. Например, роботу дана команда “вперед”, а впереди стоит стенка, и он не может идти. Или собаке скомандовали “Сидеть!”, а она уже сидит.
ЛОГИЧЕСКИЕ ОШИБКИ	Исполнитель понял команду и выполнил ее, но сделал не то, что мы от него хотели. Причина этого – наша ошибка в составлении задания (алгоритма).

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

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

1. 
   задать среду исполнителя – класс, столы, стулья;
   
2. 
   составить СКИ:
   

1. 
   ВСТАНЬ
   
2. 
   СЯДЬ
   
3. 
   ПОДНИМИ РУКУ
   
4. 
   ОПУСТИ РУКУ
   
5. 
   ПРЫГНИ
   
6. 
   МЯУКНИ
   

3. 
   определить, как передаются команды исполнителю (голосом, жестом, письменно, по рации или как-то иначе);
   
4. 
   определить, как исполнитель выполняет команды;
   
5. 
   определить, в каких случаях возникает ошибка “НЕ МОГУ”.
   

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

иначе

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

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

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

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

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

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

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

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


/* Число шагов неизвестно,

но ограничено условием */

положить бревно на козлы

наметить место распила

пока полено не отвалится

пилить от себя

пилить на себя

положить полено в поленницу

/* Число шагов известно */

повторить 6 раз

проснуться

встать

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

пойти в школу

вернуться домой

пообедать

сделать уроки

поиграть в футбол

лечь спать

/* программа на воскресенье */

спать

...




Программы

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

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


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


{



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


;



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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

1. 
   алгоритм начинается с открывающей фигурной скобки “{“ и заканчивается закрывающей фигурной скобкой “}”; команды, расположенные между этими скобками, называются телом алгоритма;
   
2. 
   в алгоритм могут входить только те команды, которые есть в СКИ исполнителя;
   
3. 
   каждая команда заканчивается знаком “;”, который обозначает конец команды;
   
4. 
   для того, чтобы нам было легче разбираться в программах, используют комментарии - текстовые пояснения, которые начинаются знаками /* и заканчиваются знаками */; исполнитель не обращает внимания на комментарии в алгоритме.
   

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

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

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

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

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

Перевоз-1 { перевезти козу; вернуться; перевезти волка; вернуться с козой; перевезти капусту; вернуться; перевезти козу; }

Перевоз-2 { перевезти козу; вернуться; перевезти капусту; вернуться с козой; перевезти волка; вернуться; перевезти козу; }

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