Виды алгоритмических конструкций
Для записи алгоритмов существуют разные способы (см. п. 2.1.3). Каждый алгоритм записывается в системе команд исполнителя. Вне зависимости от выбранной формы записи элементарные шаги алгоритма объединяются в алгоритмические конструкции (структуры): последовательные, ветвящиеся, циклические, вспомогательные алгоритмы и рекурсивные.
В 1965 г. итальянские ученые Бом и Джакопини выполнили ряд работ, определяющих количество и характер действий, которыми следует пользоваться при записи произвольных алгоритмов. Они доказали, что для записи любого сколь угодно сложного алгоритма достаточно трех основных алгоритмических конструкций: последовательных, ветвящихся, циклических.
Одновременно с ними профессор Эйндховенского университета (Нидерланды) Э. Дейкстра начал пропагандировать новый стиль программирования, который постепенно утвердился во всем мире и получил название структурного программирования. Это не язык, а стиль, его основные принципы состоят в том, чтобы пользоваться при записи алгоритмов (программ) ограниченным набором конструкций. Эти конструкции называются базовыми управляющими конструкциями структурного программирования.
К основным алгоритмическим конструкциям относят:
1. Следование.
2. Ветвление.
3. Цикл.
Рис 22. Основные алгоритмические конструкции
Линейные алгоритмы
Алгоритм P (или его часть) реализован через последовательную алгоритмическую конструкцию (следование), если каждый шаг алгоритма выполняется один раз, причем после каждого i-го шага выполняется (i + 1)-й шаг, если i-й шаг — не конец алгоритма. Такой алгоритм или часть алгоритма называют линейным.
|
|
|
Пример. Линейным является алгоритм перевоза через реку Волка, Козы и Капусты, при условии, что в лодке можно перевозить только один из указанных объектов, а на берегу вместе не могут находиться Коза и Волк, а также Коза и Капуста:
1) перевези Козу;
2) вернись на исходный берег;
3) перевези Волка;
4) вернись на исходный берег с Козой;
5) перевези Капусту;
6) вернись на исходный берег;
7) перевези Козу.
Т.е. следование, это когда в записи алгоритма друг за другом написаны несколько действий, и они выполняются последовательно.
Однако в реальной жизни очень мало задач, для решения которых достаточно последовательного выполнения действий.
Разветвляющиеся алгоритмы
Алгоритм P реализован с использованием ветвящейся алгоритмической конструкции (ветвления), если на каком-либо шаге последовательное выполнение алгоритма прерывается, и выбор следующего шага определяется входными данными алгоритма. Ветвление задает выполнение либо одной, либо другой группы операторов в зависимости от выполнения какого-либо условия (в зависимости от истинности или ложности соответствующего логического выражения). Затем исполнение алгоритма выходит на общее продолжение. Для конкретных входных данных ветвящаяся алгоритмическая конструкция сводится к последовательной алгоритмической конструкции. Ветвление бывает полным и неполным. В случае неполного ветвления при невыполнении условия никакие действия не выполняются.
|
|
|
Условная конструкция записывается как ЕСЛИ – ТО – ИНАЧЕ, по-английски IF – THEN – ELSE.
Запись полной формы в общем виде:
ЕСЛИ условие
ТО последовательность действий 1
ИНАЧЕ последовательность действий 2.
Сокращенная или усеченная форма:
ЕСЛИ условие
ТО последовательность действий.
Рис 23. Блок – схемы сокращенной и полной формы условной конструкции.
Пример. Запишем в словесной форме алгоритм решения уравнения ax2 + bx + c = 0, где a, b, c — произвольные действительные числа, а x — искомая величина. Если a¹0, то для нахождения корней используются известные формулы, при этом существование корней зависит от знака дискриминанта квадратного уравнения. Если a = 0, то уравнение становится линейным. Однако при b = 0 оно вырождается в равенство c = 0. Поэтому, если c действительно равно 0, то все действительные числа являются корнями такого уравнения, в противном случае — корней нет. Ниже приведена блок-схема данного алгоритма.
|
|
|
Рис 24. Блок-схема алгоритма решения квадратного уравнения.
Циклические алгоритмы
Алгоритм P реализован с использованием циклической алгоритмической конструкции, если некая, подряд идущая группа шагов алгоритма, выполняется несколько раз. Количество повторений либо фиксировано, либо зависит от входных данных алгоритма. Любая циклическая алгоритмическая конструкция содержит в себе элементы ветвящейся алгоритмической конструкции: после очередного выполнения группы шагов, входящих в цикл (которое называется шагом цикла, или итерацией), проверяется некоторое условие, формируемое в процессе вычислений. В зависимости от значения этого условия цикл либо завершается, либо начинается выполнение следующего шага цикла. Команды, которые повторяются, называются телом цикла.
Все циклические конструкции можно классифицировать следующим образом:
· Определенные (количества повторений тела цикла известно). Такие циклы называют циклами с параметром.
|
|
|
· Неопределенные (количества повторений тела цикла не известно и зависит от некоторого условия).
Неопределенные циклы в свою очередь делятся на:
· Цикл - ДО (цикл с пост - условием). Команды тела цикла выполняются хотя бы один раз, ДО выполнения проверки условия продолжения цикла. Обычно цикл продолжается, если условие ложно.
· Цикл - ПОКА (цикл с пред - условием). Команды тела цикла выполняются после выполнения проверки условия продолжения цикла. Обычно цикл продолжается, если до тех пор ПОКА условие истинно. В таком цикле тело цикла может не выполниться ни разу, если условие при первой проверке окажется ложным.
Блок-схемы циклов различных видов и особенности их реализации подробно представлены в главе 3 данного пособия.
Примером алгоритма с циклической конструкцией является рассмотренный выше алгоритм Евклида для нахождения наибольшего общего делителя двух натуральных чисел.
Языки программирования
Дата добавления: 2018-09-22; просмотров: 921; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!