јлгоритм


»сточник: »нтернет


јлгоритм Ч набор,инструкций описывающих пор€док действий исполнител€ дл€ достижени€ результата решени€ задачи за конечное число действий. ¬ старой трактовке вместо слова Ђпор€докї использовалось слово Ђпоследовательностьї, но по мере развити€ параллельности в работе компьютеров слово Ђпоследовательностьї стали замен€ть более общим словом Ђпор€докї

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

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

ѕон€тие алгоритма относитс€ к первоначальным, основным, базисным пон€ти€м математики. ¬ычислительные процессы алгоритмического характера (арифметические действи€ над целыми числами, нахождение наибольшего общего делител€ двух чисел и т. д.) известны человечеству с глубокой древности. ќднако в €вном виде пон€тие алгоритма сформировалось лишь в начале XX века

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

ѕон€тие алгоритма относитс€ к первоначальным, основным, базисным пон€ти€м математики. ¬ычислительные процессы алгоритмического характера (арифметические действи€ над целыми числами, нахождение наибольшего общего делител€ двух чисел и т. д.) известны человечеству с глубокой древности. ќднако, в €вном виде пон€тие алгоритма сформировалось лишь в начале XX века.

Ћюбой алгоритм составл€етс€ в расчете на конкретного исполнител€ с учетом его возможностей. »сполнитель Ч субъект, способный исполн€ть некоторый набор команд. —овокупность команд, которые исполнитель может пон€ть и выполнить, называетс€ системой команд исполнител€.

ƒл€ выполнени€ алгоритма исполнителю недостаточно только самого алгоритма. ¬ыполнить алгоритм Ч значит применить его к решению конкретной задачи, т. е. выполнить запланированные действи€ по отношению к определенным входным данным. ѕоэтому исполнителю необходимо иметь исходные (входные) данные Ч те, что задаютс€ до начала алгоритма.

јлгоритм


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

—войства алгоритмов


јлгоритм должен обладать определенными свойствами. Ќаиболее важные свойства алгоритмов:
ƒискретность. ѕроцесс решени€ задачи должен быть разбит на последовательность отдельных шагов Ч простых действий, которые выполн€ютс€ одно за другим в определенном пор€дке.  аждый шаг называетс€ командой (инструкцией). “олько после завершени€ одной команды можно перейти к выполнению следующей.
 онечность. »сполнение алгоритма должно завершитьс€ за конечное число шагов; при этом должен быть получен результат.
ѕон€тность.  ажда€ команда алгоритма должна быть пон€тна исполнителю. јлгоритм должен содержать только те команды, которые вход€т в систему команд его исполнител€.
ќпределенность (детерминированность).  ажда€ команда алгоритма должна быть точно и однозначно определена. “акже однозначно должно быть определено, кака€ команда будет выполн€тьс€ на следующем шаге. –езультат выполнени€ команды не должен зависеть ни от какой дополнительной информации. ” исполнител€ не должно быть возможности прин€ть самосто€тельное решение (т. е. он исполн€ет алгоритм формально, не вника€ в его смысл). Ѕлагодар€ этому любой исполнитель, имеющий необходимую систему команд, получит один и тот же результат на основании одних и тех же исходных данных, выполн€€ одну и ту же цепочку команд.
ћассовость. јлгоритм предназначен дл€ решени€ не одной конкретной задачи, а целого класса задач, который определ€етс€ диапазоном возможных входных данных.

—пособы представлени€ алгоритмов:
словесна€ запись (на естественном €зыке). јлгоритм записываетс€ в виде последовательности пронумерованных команд, кажда€ из которых представл€ет собой произвольное изложение действи€;
блокЦсхема (графическое изображение). јлгоритм представл€етс€ с помощью специальных значков (геометрических фигур) Ч блоков;
формальные алгоритмические €зыки. ƒл€ записи алгоритма используетс€ специальна€ система обозначений (искусственный €зык, называемый алгоритмическим);
псевдокод. «апись алгоритма на основе синтеза алгоритмического и обычного €зыков. Ѕазовые структуры алгоритма записываютс€ строго с помощью элементов некоторого базового алгоритмического €зыка.

—ловесна€ запись алгоритма
ѕроизвольное изложение этапов алгоритма на естественном €зыке имеет свои недостатки. —ловесные описани€ строго не формализуемы, поэтому может быть нарушено свойство определенности алгоритма: исполнитель может неточно пон€ть описание этапа алгоритма. —ловесна€ запись достаточно многословна. —ложные задачи трудно представить в словесной форме.

■ ѕример 1. «аписать в словесной форме правило делени€ обыкновенных дробей.

–ешение.
Ўаг 1. „ислитель первой дроби умножить на знаменатель второй дроби.
Ўаг 2. «наменатель первой дроби умножить на числитель второй дроби.
Ўаг 3. «аписать дробь, числителем которой €вл€ет результат выполнени€ шага 1, знаменателем Ч результат выполнени€ шага 2.

ќписанный алгоритм применим к любым двум обыкновенным дроб€м. ¬ результате его выполнени€ будут получены выходные данные Ч результат делени€ двух дробей (исходных данных).

‘ормальные исполнители алгоритма
‘ормальный исполнитель Ч это исполнитель, который выполн€ет все команды алгоритма строго в предписанной последовательности, не вника€ в его смысл, не внос€ ничего в алгоритм и ничего не отбрасыва€. ќбычно под формальным исполнителем понимают технические устройства, автоматы, роботов и т. п.  омпьютер можно считать формальным исполнителем.

ѕрограммы на €зыке произвольного формального исполнител€ могут состо€ть только из элементарных команд, которые вход€т в его систему (которые исполнитель Ђпонимаетї).

»сполнитель может иметь свою среду (например, систему координат, клеточное поле и др.). —реда исполнител€ Ч это совокупность объектов, над которыми он может выполн€ть определенные действи€ (команды), и св€зей между этими объектами. јлгоритмы в этой среде выполн€ютс€ исполнителем по шагам.

■ ѕример 2. »сполнитель  рот имеет следующую систему команд:
вперед k Ч продвижение на указанное число шагов вперед;
поворот s Ч поворот на s градусов по часовой стрелке;
повторить m [команда1 Е командаN] Ч повторить m раз серию указанных команд.

 акой след оставит за собой исполнитель после выполнени€ следующей последовательности команд?

ѕовторить 5 [вперед 10 поворот 72]

–ешение.  оманда вынуждает исполнител€ 5 раз повторить набор действий: пройти 10 шагов вперед и повернуть на 72∞ по часовой стрелке. “ак как поворот происходит на один и тот же угол, то за весь путь исполнитель повернет на 5 х 72∞ = 360∞. ѕоскольку все отрезки пути одинаковой длины и сумма внешних углов любого многоугольника составл€ет 360∞, то в результате будет оставлен след в форме правильного п€тиугольника со стороной в 10 шагов исполнител€.

«аметим, что если увеличить количество повторов серии команд, то исполнитель будет повторно передвигатьс€ по тем же отрезкам (произойдет повторное движение по тому же п€тиугольнику).

јлгоритм


■ ѕример 3. ¬ системе команд предыдущего исполнител€  рот сформировать алгоритм вычерчивани€ п€тиступенчатой лестницы (длина ступеньки Ч 10 шагов исполнител€).

–ешение. «а каждый шаг цикла должно происходить 4 действи€: движение вперед на 10 шагов исполнител€, поворот на 90∞ по часовой стрелке, еще 10 шагов вперед и поворот на 90∞ против часовой стрелки (= 270∞ по часовой). ¬ результате за один шаг цикла формируетс€ ломана€ из двух отрезков длиной 10 под пр€мым углом. «а п€ть таких шагов сформируетс€ 5Цступенчата€ лестница (ломана€ будет содержать 10 звеньев).
ѕовторить 5 [вперед 10 поворот 90 вперед 10 поворот 270]

ЅлокЦсхема


ЅлокЦсхема Ч нагл€дный способ представлени€ алгоритма. ЅлокЦсхема отображаетс€ в виде последовательности св€занных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. ќпределенному типу действи€ соответствует определенна€ геометрическа€ фигура блока. Ћинии, соедин€ющие блоки, определ€ют очередность выполнени€ действий. ѕо умолчанию блоки соедин€ютс€ сверху вниз и слева направо. ≈сли последовательность выполнени€ блоков должна быть иной, используютс€ направленные линии (стрелки).

ќсновные элементы блокЦсхемы алгоритма:

ќсновные элементы блокЦсхемы алгоритма


ќбщий вид блокЦсхемы алгоритма:

јлгоритм целочисленных преобразований


■ ѕример 4. јлгоритм целочисленных преобразований представлен в виде фрагмента блокЦсхемы. «наком := в нем обозначен оператор присваивани€ некоторого значени€ указанной переменной. «апись X := 1 означает, что переменна€ ’ принимает значение 1.

ќпределить результат работы алгоритма дл€ исходных данных ’ = 7, Y = 12.

результат работы алгоритма


–ешение.

Ѕлок ввода данных определит исходные значени€ переменных ’ и Y (7 и 12 соответственно).
¬ первом условном блоке осуществл€етс€ сравнение значений ’ и Y. ѕоскольку условие, записанное в блоке, неверно (7 < 12), происходит переход по линии Ђнетї.
¬о втором условном блоке выполн€етс€ второе сравнение, которое дл€ исходных данных оказываетс€ верным. ѕроисходит переход по линии Ђдаї.
¬ычисл€етс€ результат выполнени€ алгоритма: X := 0, Y := 1.

ќтвет: X := 0, Y := 1.

јлгоритмические €зыки


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

¬ алгоритмическом €зыке используютс€ формальные конструкции, но нет строгих синтаксических правил дл€ записи команд. –азличные алгоритмические €зыки различаютс€ набором служебных слов и формой записи основных конструкций.

јлгоритмический €зык, конструкции которого однозначно преобразуютс€ в команды дл€ компьютера, называетс€ €зыком программировани€. “екст алгоритма, записанный на €зыке программировани€, называетс€ программой.

ѕсевдокод


ѕсевдокод занимает промежуточное положение между естественным €зыком и €зыками программировани€. ѕример псевдокода Ч учебный алгоритмический €зык. јлфавит учебного алгоритмического €зыка €вл€етс€ открытым. —ущественным достоинством этого €зыка €вл€етс€ то, что его служебные слова, конструкции и правила записи алгоритма весьма схожи с теми, что примен€ютс€ в распространенных €зыках программировани€. Ѕлагодар€ этому учебный алгоритмический €зык позвол€ет легче освоить основы программировани€.

—лужебные слова учебного алгоритмического €зыка:

јлгоритм


—тандартна€ структура алгоритма
ѕредставление алгоритма на алгоритмическом €зыке (в том числе и €зыке программировани€) состоит из двух частей. ѕерва€ часть Ч заголовок Ч задает название алгоритма и включает описание переменных, которые используютс€ в нем. ¬тора€ часть Ч тело алгоритма Ч содержит последовательность команд алгоритма.

ќбщий вид записи алгоритма на учебном алгоритмическом €зыке:
јлгоритм


¬ начале заголовка записываетс€ служебное слово алг, после чего указываетс€ им€ алгоритма. ќписание переменных, €вл€ющихс€ аргументами алгоритма и его результатами, приводитс€ после названи€ в круглых скобках.

¬ следующих строках конкретизируют, какие именно переменные €вл€ютс€ аргументами алгоритма (входными данными), а какие Ч его результатами (выходными данными). ƒл€ этого после служебного слова арг приводитс€ список имен переменныхЦаргументов; в следующей строке после служебного слова рез приводитс€ список имен переменныхЦрезультатов.

ћежду служебными словами нач и кон размещаетс€ тело алгоритма Ч конечна€ последовательность команд, выполнение которых предписывает алгоритм.  оманды алгоритма записывают одну за одной в отдельных строках. ¬ случае необходимости можно записать две или более команд в одной строке, тогда соседние команды раздел€ют точкой с зап€той. ≈сли в алгоритме примен€ютс€ промежуточные переменные, их описание привод€т в начальной строке тела алгоритма р€дом со словом нач.

ѕримеры заголовков алгоритмов:
јлгоритм


¬ первом примере алгоритм имеет название ќбъем_шара, один вещественный аргумент –адиус и один вещественный результат ќбъем. ¬о втором примере алгоритм под названием Choice имеет три аргумента Ч целые M и N и логический b, а также два результата Ч вещественные Var1 и Var2.

ѕример алгоритма вычислени€ гипотенузы пр€моугольного треугольника:
јлгоритм


Ќа вход алгоритму даютс€ два вещественных аргумента a и b (величины катетов), результатом €вл€етс€ вещественна€ переменна€ с (гипотенуза). ƒл€ ее расчета используетс€ функци€ вычислени€ квадратного корн€ sqrt.

ќписание величин и действи€ над ними
ѕри описании алгоритма необходимо указать названи€ (обозначени€) всех величин, которые будут в нем найдены или использованы.

ѕри представлении алгоритма решени€ в виде блокЦсхемы выбранные обозначени€ величин привод€тс€ отдельно от блокЦсхемы (как объ€снение к ней). ≈сли алгоритм представлен на €зыке программировани€, то характеристика обрабатываемых величин включаетс€ в программу. ”чебный алгоритмический €зык также предусматривает описание величин, используемых в алгоритме.

¬се величины в алгоритме раздел€ют на посто€нные (константы) и переменные.  онстанта не может измен€ть свои значени€ в процессе работы алгоритма. ѕеременна€ может приобретать различные значени€, которые сохран€ютс€ до тех пор, пока она не получит новое значение. ѕеременным величинам назначают имена. “аким образом, переменна€ Ч это именуема€ величина, котора€ в процессе выполнени€ алгоритма может приобретать и хранить различные значени€.

¬ алгоритмическом €зыке не существует специальных правил именовани€ переменных. ќднако их названи€ не должны совпадать со служебными словами алгоритмического €зыка. ¬о многих €зыках программировани€ дл€ имен можно использовать только латинские буквы, цифры, знак подчеркивани€. »мена об€зательно должны начинатьс€ с буквы, при этом строчные и прописные буквы в именах не различаютс€. ¬ одном алгоритме не могут существовать разные объекты с одинаковыми именами. ¬се имена €вл€ютс€ уникальными. »мена переменных и констант стараютс€ выбирать так, чтобы они напоминали их смысл. Ќапример, имена переменных и констант: S, p12, result, итог.

ѕри представлении алгоритма на алгоритмическом €зыке именуютс€ не только величины, но и сам алгоритм, и другие объекты. »м€ алгоритма выбирают так же, как и имена переменных.

¬еличина Ч переменна€, с которой св€зываетс€ определенное множество значений. Ётой величине присваиваетс€ им€ (в €зыках программировани€ его называют идентификатор).

«начение Ч то, чему равна переменна€ в конкретный момент. «начение переменной можно задать двум€ способами: присваиванием и с помощью процедуры ввода.

“ип переменной определ€ет диапазон всех значений, которые может принимать данна€ переменна€, и допустимые дл€ нее операции. —уществует несколько предопределенных типов переменных.   стандартным типам относ€тс€ числовые, литерные и логические типы.

„исловой тип предназначен дл€ обработки числовых данных. –азличают целый и вещественный числовые типы. ÷елый тип в учебном алгоритмическом €зыке обозначаетс€ служебным словом цел, к нему относ€тс€ целые числа некоторого определенного диапазона. ќни не могут иметь дробной части, даже нулевой. „исло 123,0 €вл€етс€ не целым, а вещественным числом. ¬ещественные величины относ€тс€ к вещественному типу данных и обозначаютс€ в учебном алгоритмическом €зыке служебным словом вещ. “акие величины могут отображатьс€ двум€ способами: в форме с фиксированной зап€той (например, 0,0511 или Ц712,3456) и с плавающей зап€той (те же примеры: 5,11*10-2 и Ц7,123456*102).

Ќад целыми числами можно также выполн€ть две операции целочисленного делени€ div и mod. ќпераци€ div обозначает деление с точностью до целых чисел (остаток от делени€ игнорируетс€). ќпераци€ mod позвол€ет узнать остаток при делении с точностью до целых чисел. Ќапример, результатом операции 100 div 9 будет число 11, а результатом 100 mod 9 Ч число 1.

Ћитерный тип представл€ет собой символы и строки, он дает возможность работать с текстом. Ћитерные величины Ч это произвольные последовательности символов. Ёти последовательности заключаютс€ в двойные кавычки: Ђрезультатї, Ђsum_priceї. ¬ качестве символов могут быть использованы буквы, цифры, знаки препинани€, пробел и некоторые другие специальные знаки (возможными символами могут быть символы таблицы ASCII). ¬ учебном алгоритмическом €зыке литерные величины обозначаютс€ лит.

Ќад литерными величинами возможны операции сравнени€ и сли€ни€. —равнение литерных величин производитс€ в соответствии с их упор€дочением: Ђaї < Ђbї, Ђbї < Ђсї и т. д. —ли€ние (конкатенаци€) литерных величин приводит к образованию новой величины: Ђполї + Ђеї образует Ђполеї.

Ћогический тип определ€ет логические переменные, которые могут принимать только два значени€ Ч истина (True) или ложь (False). Ќад логическими величинами можно выполн€ть все стандартные логические операции.

 лючевые слова:
алгоритм
јлгоритмические €зыки
блок-схема
свойства алгоритмов
блокЦсхемы алгоритма
ќписание величин
робот
робототехника


¬ернутьс€ в рубрику:

—ловарик робототехника


≈сли вы хотите видеть на нашем сайте больше статей то кликните ѕоделитьс€ в социальных сет€х! —пасибо!
—мотрите также:

ќбратите внимание полезна€ информаци€.