Материал: Алгоритмы пособие

1.Основы алгоритмизации

1.1.Алгоритм, его свойства

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

К основным свойствам алгоритмов можно отнести:

1.Универсальность - применимость алгоритма к различным наборам исходных данных.

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

3.Однозначность - правила и порядок выполнения действий алгоритма имеют единственное толкование.

4.Конечность - действия и алгоритм в целом обязательно завершаются.

5.Результативность - по завершении выполнения алгоритма обязательно получается конечный результат.

Выделяют три крупных класса алгоритмов:

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

информационные алгоритмы, представляющие собой набор процедур, работающих с большими объемами информации (алгоритмы баз данных);

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

Для записи алгоритмов используют самые разнообразные средства. Выбор средства определяется типом исполняемого алгоритма.

Выделяют следующие основные способы записи алгоритмов:

вербальный (словесный)- последовательность действий, описанная на естественном языке;

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

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

Из всех рассмотренных выше способов описания алгоритмов графический способ является общепринятым представлением алгоритма. Он

6

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

Для графического описания алгоритмов используются стандартные графические блоки, начертание и размеры которых регламентируются соответствующим ГОСТом[1]. В табл.1.1-1 приведен перечень основных обозначений, принятых в схемах алгоритмов.

Таблица 1.1-1

7

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

В блоках допускается запись в произвольном виде (текст, формулы или условные обозначения). Если запись в блоке не умещается или требует пояснений, то к этому блоку добавляется комментарий.

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

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

Базовыми алгоритмическими структурами принято называть подмножество алгоритмических структур, которые позволяют составить алгоритм решения сколь угодно сложной задачи[2]. Эти структуры могут быть использованы в качестве составляющих разработчиком программы в зависимости от специфики решаемой задачи. К базовым алгоритмическим структурам относятся:

последовательные структуры;

разветвляющиеся структуры;

циклические структуры регулярного типа;

циклические структуры итеративного типа.

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

Рис. 1.2-1. Последовательная алгоритмическая структура

8

Разветвляющимися называются такие алгоритмические структуры, в которых порядок выполнения функциональных блоков определяется значениями логических выражений. Если логическое выражение принимает значение «Истина», то выполняется часть алгоритма, расположенная по ветви «Да», если принимает значение «Ложь», то – часть алгоритма по ветви «Нет».Разветвляющиеся структуры могут быть достаточно сложными, но среди них можно выявить три основных типа разветвлений: стандартное,

усеченное и вложенное.

Стандартное разветвлениесодержит функциональные блоки как в ветви «Да», так и в ветви «Нет» (рис.1.2-2).

Рис.1.2-2. Стандартное разветвление

Усеченное разветвление содержит функциональные блоки только в ветви «Да» или только в ветви «Нет» (рис.1.2-3).

Рис. 1.2-3. Типы усеченных разветвлений

Вложенное разветвление содержит одно или несколько дополнительных разветвлений (рис.1.2-4).

9

Рис. 1.2-4. Вложенное разветвление

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

Циклическими называются структуры, в которых предусмотрена возможность многократного повторения выполнения участка алгоритма. Этот участок называется телом цикла. Различают циклические структуры двух видов:

-регулярные циклические структуры– это циклические структуры с заранее известным числом повторений;

-итеративной циклической структурой– это циклические структуры

сзаранее неизвестным числом повторений цикла.

Общий вид алгоритма регулярной циклической структуры приведен нарис.1.2-5.

Рис.1.2-5. Регулярная циклическая структура

10