1.3. Структурное описание алгоритма.

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

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

Е3 [замещение]

Е1 [нахождение остатка]

Е2 [это нуль?]

да

окончание в n-искомое число

начало

нет

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

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

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

• линейная

структура описывает процесс, в котором операции (действия) выполняются по- следовательно, в порядке их описания. Вершины, отображающие эти действия, располагаются в линейной последовательности. Такие процессы имеют место, например, при вычислении ариф- метических выражений, когда имеются конкретные числовые данные и над ними выполняются соответствующие условию задачи действия. Например, для вычисления y = (b2 – a*c) / (a + c) имеем следующую алгоритмическую структуру.

• ветвящаяся

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

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

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

• циклическая

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

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

– подготовка (инициализация); здесь S ← 0, i ← 1;

– выполнение (тело цикла); здесь S ← S + xi;

– модификация параметров; здесь i ← i + 1;

– проверка условий; здесь i ≤ n.

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