Алгоритмические конструкции
Виды алгоритмических конструкций
Для записи алгоритмов существуют разные способы (см. “Способы записи алгоритмов”): текстово-формульная запись, блок-схема, машина Тьюринга, машина Поста,
программа на алгоритмическом языке и др. Каждый алгоритм записывается в системе команд исполнителя. Вне зависимости от выбранной формы записи элементарные шаги алгоритма
объединяются в алгоритмические конструкции (структуры): последовательные, ветвящиеся, циклические, вспомогательные алгоритмы и рекурсивные.
В 1966 году Бом и Джакопини доказали, что для записи любого сколь угодно сложного алгоритма достаточно трех основных алгоритмических конструкций: последовательных, ветвящихся, циклических.
Алгоритм P (или его часть) реализован через последовательную алгоритмическую конструкцию (следование), если каждый шаг алгоритма выполняется один раз, причем после
каждого i-го шага выполняется (i + 1)-й шаг, если i-й шаг — не конец алгоритма. Такой алгоритм или часть алгоритма еще называют линейным.
Пример 1. Линейным является алгоритм перевоза через реку Волка, Козы и Капусты, при условии, что в лодке можно перевозить только
один из указанных объектов, а на берегу вместе не могут находиться Коза и Волк, а также Коза и Капуста:
- перевези Козу;
- вернись на исходный берег;
- перевези Волка;
- вернись на исходный берег с Козой;
- перевези Капусту;
- вернись на исходный берег;
- перевези Козу.
Алгоритм P реализован с использованием ветвящейся алгоритмической конструкции (ветвления), если на каком-либо шаге последовательное выполнение алгоритма прерывается,
и выбор следующего шага определяется входными данными алгоритма. Ветвление задает выполнение либо одной, либо другой группы операторов в зависимости от выполнения
какого-либо условия (в зависимости от истинности или ложности соответствующего логического выражения, см. “Логические выражения”). Затем исполнение алгоритма
выходит на общее продолжение. Для конкретных входных данных ветвящаяся алгоритмическая конструкция сводится к последовательной алгоритмической конструкции.
Ветвление бывает полным и неполным. В случае неполного ветвления при невыполнении условия никакие действия не выполняются.
Пример 2. Запишем в словесной форме алгоритм решения уравнения ax2 + bx + c = 0, где a, b, c — произвольные действительные числа, а x — искомая величина.
Если a 0, то для нахождения корней используются известные формулы, при этом существование корней зависит от знака дискриминанта квадратного уравнения.
Если a = 0, то уравнение становится линейным. Однако при b = 0 оно вырождается в равенство c = 0. Поэтому, если c действительно равно 0, то все
действительные числа являются корнями такого уравнения, в противном случае — корней нет. Ниже приведена блок-схема данного алгоритма.
Алгоритм P реализован с использованием циклической алгоритмической конструкции, если некая, подряд идущая группа шагов алгоритма, выполняется несколько раз.
Количество повторений либо фиксировано, либо зависит от входных данных алгоритма. Любая циклическая алгоритмическая конструкция содержит в себе элементы ветвящейся
алгоритмической конструкции: после очередного выполнения группы шагов, входящих в цикл (которое называется шагом цикла, или итерацией), проверяется некоторое условие,
формируемое в процессе вычислений. В зависимости от значения этого условия цикл либо завершается, либо начинается выполнение следующего шага цикла.
В качестве примера алгоритма с циклической конструкцией можно рассмотреть алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел.
Следование, ветвление и цикл называют базовыми конструкциями структурного программирования. Их особенностью является то, что любая из них имеет только один вход и
один выход, поэтому они могут вкладываться друг в друга. Например, цикл может содержать следование из двух ветвлений, каждое из которых включает вложенные циклы.
Запись конструкций
Следование не имеет специальной формы записи, а выражается в том, что входящие в него шаги записываются последовательно, а управление после выполнения
очередного шага этой конструкции переходит к следующему. В текстовой форме записи — это просто последовательная запись пунктов, соответствующих шагам алгоритма.
В блок-схемах — это последовательная запись блоков действия, соединенных стрелкой, направленной от предыдущего блока к следующему.
На процедурном языке программирования данная конструкция выражается просто последовательной записью инструкций (операторов языка программирования).
Ветвление в текстовой форме записи обычно выглядит так: если выполнено такое-то условие, то сделать то-то (или перейти на такой-то пункт алгоритма), в противном
случае сделать то-то (или перейти на такой-то пункт алгоритма). В блок-схемах для реализации конструкции ветвление предназначен специальный блок условия, имеющий форму ромба.
Данный блок имеет один вход и два выхода, соответствующих истинному или ложному значению логического выражения, записанного в этом блоке.
В языках программирования данная конструкция реализуется через условный оператор.
В машине Тьюринга ветвление реализуется через анализ текущего состояния машины и текущего символа на ленте машины Тьюринга (в зависимости от символа и от состояния машины
на ленту записывается определенный символ и совершается переход в определенное состояние).
Циклическая конструкция в явном виде во многих формах записи алгоритмов, к сожалению, отсутствует. На практике она реализуется с помощью проверки условия и управляющей
конструкции перехода. В текстовой форме записи переход осуществляется на тот же самый пункт или пункт с меньшим номером. В блок-схемах переход с помощью стрелок
осуществляется на часть схемы, по которой выполнение алгоритма уже ранее проходило. В языках программирования циклическая конструкция реализуется через различные
операторы цикла “с предусловием”, “с постусловием”, “с параметром”. На самом деле для реализации любой циклической конструкции хватило бы и одного вида оператора,
например, с “предусловием”, различные операторы циклов вводятся в тот или иной язык программирования только для удобства программистов.
Пример 3. Рассмотрим следующую задачу. Пусть на вход алгоритму подается последовательность символов “+”.
Требуется заменить каждый второй символ этой последовательности на “–”.
Для машины Тьюринга эта задача может быть переформулирована так. На ленте машины Тьюринга содержится последовательность символов “+”. Напишите программу
для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Автомат в состоянии q1 обозревает крайний левый символ в указанной последовательности.
Решение
В состоянии q1 машина пропускает знак “+”, а при достижении конца последовательности — останавливается. В состоянии q2 машина знак “+” заменяет на знак “–”,
при достижении конца последовательности она останавливается. “–” является символом алфавита этой машины, но он нам встретиться не может.
В данной машине неявным образом заложена последовательная смена состояний q1 и q2, до тех пор пока входная последовательность не закончится, т.е. алгоритм реализуется с использованием цикла.
Решение той же задачи с помощью блок-схемы можно записать так:
На языке программирования Pascal программа решения этой задачи может выглядеть так:
var S: string;
i: integer;
begin
readln(S);
for i := 1 to> length(S) do
if i mod 2 = 0 then S[i] := '–';
writeln(S)
end.