Элементарные алгоритмические структуры

 

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

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

можно представить следующей линейной структурой:

Ветвящаяся структура – это процесс, для реализации которого предусмотрено несколько направлений (ветвей). Каждое отдельное направление является отдельной ветвью. Направление ветвления выбирается в соответствии с результатом проверяемого условия, если условием является логическое выражение, то предполагается альтернативный выбор. Такой ветвящийся процесс включает в себя две ветви и называется простым или альтернативным. Например,

Эта структура реализует вычисление:

^y={

Если процесс предполагает более двух ветвей, то он называется сложным. Например,

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

В описании цикла можно выделить следующие этапы:

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

2) выполнение (тело цикла) включает действия, составляющие цикл (S ← S + x_i)

3) модификация параметров включает действия, изменяющие значения тех параметров, от которых зависит условие окончания цикла (i ← i + 1).

4) проверка условия окончания цикла (i ≤ n?).

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

Различают цикл с нижним окончанием или с постусловием (условие проверяется после тела цикла) и цикл с верхним окончанием или с предусловием (условие проверяется перед телом цикла). Отличие заключается в том, что в первом случае тело цикла обязательно выполняется по крайней мере один раз, а во втором – может не выполниться ни разу.

Требования, предъявляемые к алгоритмам

Алгоритмы это не просто последовательность действий для решения задачи, он должен удовлетворять следующим, основным требованиям:

1) конечность (результативность)

2) определенность

3) наличие описания входных и выходных данных

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

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

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

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

2) Массовость. Алгоритм можно применить для решения множества задач.

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