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

Различают три базовые алгоритмические структуры:

· следование,

· ветвление,

· повторение.

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

<команда – предшественник>;

<команда – преемник>.

Такую структуру ещё называют линейным вычислительным процессом, в котором этапы вычислений выполняются в линейной последовательности и каждый этап выполняется только один раз. На схеме блоки размещаются сверху вниз в порядке их выполнения. Для таких процессов характерно, что направление вычислений не зависит от исходных данных или промежуточных результатов. В виде блок-схемы линейный вычислительный процесс можно представить следующим образом:

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

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

Структура имеет вид

if <условие>

then <команда, выполняемая при выполнении условия>

else <команда, выполняемая при невыполнении условия>;.

Структура типа ветвления в неполной форме – частный случай ветвления в полной форме, в которой, при невыполнении условия, управление просто передается следующей команде и больше никаких действий команда ветвления не осуществляет.

.

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

Цикл с проверкой условия до исполнения действия (с предусловием). Действие может не исполниться ни одного раза.

Цикл с проверкой условия после исполнения действия (с постусловием). Действие обязательно исполнится хотя бы один раз.

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

Этот цикл выполняется по правилу: для начального значения переменной выполняются команды тела цикла по порядку и затем проверяется, превысило ли текущее значение переменной ее заданного конечного значения; если превысило – цикл заканчивается, иначе значение переменной увеличивается на единицу и снова повторяется тело цикла и т.д.

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

Для организации цикла необходимо предусмотреть:

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

· изменение значения этой переменной перед каждым новым повторением цикла;

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

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

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

· последовательности двух или более операторов;

· выбора (ветвления);

· повторения (цикла).

Эти структуры, имеющие единственный вход и единственный выход допускают включение их во все линейные блоки («действия») в любых комбинациях.

Э. Дейкстра в 1975г. предложил отказаться от оператора безусловного перехода и ограничиться этими тремя конструкциями. Дональд Кнут продемонстрировал случаи, в которых оператор безусловного перехода (GOTO) оказывался полезным (например, выход из нескольких вложенных циклов) и подверг критике утверждение Э.Дейкстры. Академик В.М. Глушков обратил внимание на то, что структурированные программы можно рассматривать как формулы в некоторой алгебре. Зная правила преобразования выражений в такой алгебре, можно осуществлять глубокие формальные (и, следовательно, автоматизированные) преобразования программ.

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

Контрольные вопросы и задания

1. Дайте определение алгоритма, укажите его свойства.

2. Каковы способы записи алгоритмов?

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

4. Что такое алгоритмический язык и какими свойствами он должен обладать?

Дата добавления: 2014-01-06