Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Понятие алгоритма)..pdf

ВВЕДЕНИЕ

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

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

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

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

Объект исследования – теория алгоритмов и структур данных.

Предмет исследования – структуры алгоритмов.

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

В соответствии с поставленной целью выделены такие задания:

– рассмотреть основные понятия об алгоритмах, их свойства;

– описать методы подачи алгоритмов;

– охарактеризовать базовые структуры алгоритмов и провести их сравнительный анализ;

– провести рассмотрение операторов для реализации основных структур алгоритмов на языке С++;

– привести примеры использования базовых структур алгоритмов.

В работе используется язык С++, так как он на данное время является одним из самых используемых.

Проблему использования базовых структур алгоритмов изучали разные ученые: Б. Страуструп, Дж.Прата, Г Шилдт. Как результат исследования ими были выпущены учебники по изучению языка программирования С++.

1.Основные понятия теории алгоритмов

1.1.Понятие алгоритма

В жизнедеятельности постоянно нужно сталкиваться с различными правилами, что описывают последовательности действий с целью достичь какого-то определенного результата. Такие правила являются многочисленными. К примеру, мы придерживаемся каких-то правил, чтобы приготовить лекарство, позвонить, сварить суп или же решить какое-то математическое уравнение. Рассмотренные примеры можно объединять под понятием «алгоритм». [1]

Понятие алгоритма – это фундаментальная концепция информатики и математики. Оно возникло задолго до создания персональных компьютеров и на данный момент стало главным понятием. [2]

Термин «алгоритм» происходит от фамилии индийского математика Мугаммада аль-Хорезми (рис.1). [4]

Рис.1. Мугаммад аль-Хорезми

Это – один из круп­ней­ших уче­ных Сред­не­ве­ковья. Его ро­ди­на – Хо­резм. Свои зна­ния аль-Хо­рез­ми со­вер­шенст­во­вал в «До­ме муд­рос­ти» в Баг­да­де. Это уч­реж­де­ние бы­ло сво­е­го ро­да Ака­де­ми­ей на­ук, в ко­то­рой ра­бо­та­ли мно­гие уче­ные араб­ско­го Вос­то­ка. «Дом муд­рос­ти» сла­вил­ся сво­ей бо­га­той биб­лио­те­кой ста­рин­ных ру­ко­пи­сей и аст­ро­но­ми­чес­кой об­сер­ва­то­ри­ей.[3]

Ис­сле­до­ва­те­ли уста­но­ви­ли, что аль-Хо­рез­ми был ав­то­ром 9 со­чи­не­ний:

1. Кни­га об ин­дий­ской ариф­ме­ти­ке;
2. Крат­кая кни­га об ис­чис­ле­нии ал­геб­ры и ал­му­ка­ба­лы;
3. Аст­ро­но­ми­чес­кие таб­ли­цы (зидж);
4. Кни­га кар­ти­ны Зем­ли;
5. Кни­га о по­стро­е­нии аст­ро­ля­бии;
6. Кни­га о дейст­ви­ях с по­мощью аст­ро­ля­бии;
7. Кни­га о сол­неч­ных ча­сах;
8. Трак­тат об опре­де­ле­нии эры ев­ре­ев и их празд­ни­ках;
9. Кни­га ис­то­рии.[11]

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

Ал­геб­ра­и­чес­кая кни­га аль-Хо­рез­ми (Ки­таб мух­та­саб ал-джабр и ва-л-му­ка­ба­ла) со­сто­ит из двух час­тей – те­о­ре­ти­чес­кой (те­о­рия ре­ше­ния ли­ней­ных и квад­рат­ных урав­не­ний, не­ко­то­рые во­про­сы гео­мет­рии) и прак­ти­чес­кой (при­ме­не­ние ал­геб­ра­и­чес­ких ме­то­дов в ре­ше­нии хо­зяйст­вен­но-бы­то­вых, тор­го­вых и юри­ди­чес­ких за­дач – де­леж на­следст­ва, со­став­ле­ние за­ве­ща­ний, раз­дел иму­щест­ва, раз­лич­ные сдел­ки, из­ме­ре­ние зе­мель, стро­и­тельст­во ка­на­лов). Бла­го­да­ря араб­ско­му сло­ву «ал-джабр» воз­ник та­кой на­уч­ный тер­мин как «ал­геб­ра». Унас­ле­до­ван­ное от вос­точ­ных ма­те­ма­ти­ков уче­ние о ли­ней­ных и квад­рат­ных урав­не­ни­ях ста­ло ос­но­вой раз­ви­тия ал­геб­ры в Ев­ро­пе. Ла­ти­ни­зи­ро­ван­ное имя уче­но­го во­шло в на­уку под тер­ми­ном «ал­го­ритм».[13]

Гео­мет­ри­чес­кая часть трак­та­та по­свя­ще­на из­ме­ре­нию пло­ща­дей и объ­емов гео­мет­ри­чес­ких фи­гур (тре­уголь­ник, квад­рат, ромб, па­рал­ле­ло­грамм, круг, сег­мент кру­га, че­ты­рех­уголь­ник с раз­ны­ми сто­ро­на­ми и уг­ла­ми, па­рал­ле­ле­пи­пед, кру­го­вой ци­лин­др, приз­ма, ко­нус).[20]

Ог­ро­мен вклад уче­но­го и в аст­ро­но­мию, ко­то­рая бы­ла не­об­хо­ди­ма для оро­ша­е­мо­го зем­ле­де­лия, мор­ской и су­хо­пут­ной тор­гов­ли. Зидж (сбор­ник аст­ро­но­ми­чес­ких и три­го­но­мет­ри­чес­ких таб­лиц) аль-Хо­рез­ми по­свя­щен хро­но­ло­гии и ка­лен­да­рю (важ­ное на­уч­ное на­прав­ле­ние, так как раз­ные на­ро­ды поль­зо­ва­лись раз­лич­ны­ми сис­те­ма­ми вре­мен­но­го сче­та). Боль­шую важ­ность для аст­ро­но­мии то­го вре­ме­ни пред­став­ля­ла его кни­га об аст­ро­ля­бии.[14]

Algorithmi – латинское транскрипция его фамилии, это слово применялось для обозначения правил по таким арифметическим действиям: [1]

– сложение;

– вычитание;

– умножение;

– деление.

Совокупность таких правил в Европе начали называть «алгоризм». В следующих периодах это слово переродилось в термин «алгоритм» и стало при этом собирательным названием некоторых правил определенного вида, а не лишь правил арифметических действий.

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

Алгоритм – точное правило, которое определяет процесс преобразования начальных данных для получения результатных при решении определенного вида задач. [1]

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

Алгоритм – фундаментальное понятие программирования. Ученые выделяют 3 основных класса алгоритмов:

– информационные;

– вычислительные;

– управляющие [3].

Вычислительные алгоритмы – алгоритмы, что работают со сравнительно простыми форматами данных.

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

Эффективность работы таких алгоритмов прямо зависит от организации информации в программе.

Управляющие алгоритмы характеризуются тем, что информация для них поступает от внешних источников, которыми они и управляют. Результатами выполнения этих алгоритмов является создание своевременной управляющей реакции на изменение начальных данных.[2]

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

1.2.Свойства алгоритмов

Любые алгоритмы обладают такими свойствами:[6]

1. Массовость – возможность применить алгоритм к любым задачам четко определенного класса.

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

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

2. Детерминированность или определенность – набор указаний должен не зависеть от исполнителя алгоритма и быть точен. Такая характеристика обеспечивает однозначность и определенность результата процесса, который описан при заданных начальных данных. [14]

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

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

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

4. Ясность – это понимание исполнителя алгоритма о том, что нужно сделать для выполнения поставленного алгоритма. [15]

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

5. Формальность– это когда результат выполнения алгоритмов не должен зависеть от любого рода факторов, что не являются частью рассматриваемого алгоритма. [2]

Все исполнители, способные воспринимать и выполнять некоторые указания алгоритма (даже при этом не понимая их), действуя по нему, могут выполнить поставленную ранее задачу. [4]

6. Результативность – завершение процесса преобразования начальной информации в конечную. Это свойство указывает применение алгоритма к всем допустимым наборам исходных данных за некоторое число шагов обеспечивает получение результата. [1]

7. Корректность – означает, что если алгоритм создан для решения определенной задачи, то для всех исходных данных он должен всегда давать правильный результат и ни для каких исходных данных не будет получен неправильный результат. [11]

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

2.Базовые структуры алгоритмов

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

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

Методы, которые используются для этого, определяют квалификацию исполнителя, в значительной степени. К базовым методам для записи алгоритма относятся: [7]

– блок-схемы;

– формульно-словесный метод;

– языки программирования алгоритмов.

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

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

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

Внутри блока описывается конкретный этап реализации алгоритма.

Рассмотрим базовые фигуры, применимые в создании блок-схем:[19]

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

Рис.2. Блок «Процесс»

2.Решение. Выбор направления алгоритма или программы в зависимости от условий. [6]