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

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

Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.

Базовая структура «следование»

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

Запись псевдокодом	Графическое изображение
действие 1 действие 2 .......... действие n

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

q ввод исходных данных;

q вычисление по формулам;

q вывод результата.

Базовая структура «ветвление»

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

q Если-То;

q Если-То-Иначе;

q Выбор;

q Выбор-Иначе.

Запись псевдокодом	Графическое изображение
1. Если-то
если условието действия все
2. Если-то-иначе
если условие то действия 1 иначе действия 2 все
3. Выбор
выбор при условие 1: действия 1 при условие 2: действия 2........................... при условие N: действия N все
4. Выбор-иначе
выбор при условие 1: действия 1 при условие 2: действия 2........................... при условие N: действия N иначедействия N+1 все

Базовая структура «цикл»

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

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

Различают три вида циклов:

q с предусловием;

q с постусловием;

q с параметром.

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

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

 

Запись псевдокодом	Графическое изображение
1. Цикл с предусловием (Цикл-Пока). Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова «пока».
нц пока условие тело цикла (последовательность действий) кц
2. Цикл с постусловием (Цикл-До). Предписывает выполнять тело цикла до тех пор, пока не выполняется условие, записанное после слова «до».
нц повторять тело цикла (последовательность действий) до условие Кц
3. Цикл с параметром (Цикл-Для). Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне
нц для i от i1до i2 шаг i3 тело цикла (последовательность действий) кц

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

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

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

1. Задание начального значения используемого параметра цикла (например, если переменной цикла является i, то ей присваивается значение i 1, т.е. i:= i 1).

2. Выполнение действий, предусмотренных в теле цикла.

3. Изменение параметра цикла, который обеспечивает вычисление результата с новыми начальными данными (например, если параметр цикла i изменяется с шагом i 3, i:= i + i 3) и переход к следующему шагу.

4. Проверка текущего значения параметра цикла с заданным конечным значением (i <= i 2).

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