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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

Задачами данного исследования являются:

-изучить понятия об алгоритмах, их свойства и классификацию;

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

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

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

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

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

Глава 1. ОСНОВНЫЕ ПОНЯТИЯ ОБ АЛГОРИТМАХ

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

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

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

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

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

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

1. Книга об индийской арифметике;
2. Краткая книга об исчислении алгебры и алмукабалы;
3. Астрономические таблицы;
4. Книга картины Земли;
5. Книга о построении астролябии;
6. Книга о действиях с помощью астролябии;

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

– сложение;

– вычитание;

– умножение;

– деление. [^[4]]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Предопределенный процесс. Использование созданных ранее и описанных отдельно алгоритмов или же программ (функций, программных модулей, процедур). Символ служит для выполнения обращения к программным модулям (Рис.1.4). [^[18]]

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

5.Дисплей. Ввод или вывод данных, если непосредственно подключенное устройство воспроизводит их и позволяет пользователю вносить изменения (Рис.1.6). [^[19]]

6.Документ. Ввод или вывод данных на бумажный носитель (Рис.1.7).

7.Линия перехода. Указание последовательности перехода (Рис.1.8)

8.Соединитель. Указание связей между прерванными линиями перехода, связывающими блоки. Если блок-схема состоит из частей, расположенных на одной странице, то тогда линия перехода одной части заканчивается блоком соединитель, а линия перехода на продолжении блок-схемы будет начинаться с этого символа. [^[20]]

Внутри блока ставятся одинаковые номера, соответствующие для разорванной линии перехода (Рис.1.9).

9. Межстраничный соединитель. Указание связей между частями схем алгоритмов и программ, что являются расположенными на разных листах. [^[21]]

Этот блок служит для аналогичных целей, что и блок соединитель, но при расположении составных блок-схемы на других страницах (Рис.1.10) [^[22]]

10.Пуск - остановка. Начало или конец процесса обработки данных (Рис.1.11).

11.Комментарий. Связь между блоками схемы и пояснениями к ним. Позволяет включать пояснения в блок-схему, формулы и другую полезную информацию (Рис.1.12) [^[23]]

Самым популярным методом изображения алгоритмов являются языки программирования.

Языком программирования называется система условных обозначений, которая помогает более точно описать алгоритмы или инструкции программ.[^[24]]