Алгоритмические конструкции
Содержание
Виды алгоритмических конструкций
Для записи алгоритмов существуют разные способы (см. “Способы записи алгоритмов”): текстово-формульная запись, блок-схема, машина Тьюринга, машина Поста, программа на алгоритмическом языке и др. Каждый алгоритм записывается в системе команд исполнителя. Вне зависимости от выбранной формы записи элементарные шаги алгоритма объединяются в алгоритмические конструкции (структуры): последовательные, ветвящиеся, циклические, вспомогательные алгоритмы (см. “Подпрограммы”) и рекурсивные. В 1966 году Бом и Джакопини доказали, что для записи любого сколь угодно сложного алгоритма достаточно трех основных алгоритмических конструкций: последовательных, ветвящихся, циклических.
Алгоритм P (или его часть) реализован через последовательную алгоритмическую конструкцию (следование), если каждый шаг алгоритма выполняется один раз, причем после каждого i-го шага выполняется (i + 1)-й шаг, если i-й шаг — не конец алгоритма. Такой алгоритм или часть алгоритма еще называют линейным.
Пример 1. Линейным является алгоритм перевоза через реку Волка, Козы и Капусты, при условии, что в лодке можно перевозить только один из указанных объектов, а на берегу вместе не могут находиться Коза и Волк, а также Коза и Капуста:
1) перевези Козу;
2) вернись на исходный берег;
3) перевези Волка;
4) вернись на исходный берег с Козой;
5) перевези Капусту;
6) вернись на исходный берег;
7) перевези Козу.
Алгоритм 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.
Структурное программирование
Эдсгер В. Дийкстра, опираясь на теорему Бома и Джакопини, ввел понятие структурного программирования, которое часто называют “программирование без GOTO” (управляющая конструкция перехода не используется при написании программ).
В соответствии с данным способом разработки любая программа представляет собой структуру, построенную из трех типов базовых конструкций, рассмотренных выше. Еще один из принципов структурного программирования состоит в том, что программная единица (подпрограмма) должна иметь одну точку входа и одну точку выхода.
Соблюдение принципов структурного программирования делает тексты программ, даже довольно больших, нормально “читаемыми”, что существенно облегчает понимание программ, — появилась возможность разработки код в промышленном режиме, когда код может без особых затруднений понять не только ее автор, но и другие программисты.
Методические рекомендации
Знакомство с основными алгоритмическими конструкциями начинается в пропедевтическом курсе информатики. К сожалению, запись алгоритмов с помощью блок-схем не приучает к структурному мышлению и выделению циклических конструкций в явном виде (исключение составляют специальные циклические блоки, которые часто не изучаются, как избыточные). Поэтому роль учителя состоит в том, чтобы на примерах показать, насколько необдуманные переходы запутывают алгоритм. Саму же разработку алгоритмов надо сразу проводить со школьниками по структурной схеме, используя технологию “сверху вниз” (см. “Подпрограммы”).
В начальной школе, а также в 5–7-х классах при изучении алгоритмики отработке подлежит составление алгоритмов, содержащих циклическую алгоритмическую конструкцию, как наиболее сложную для понимания. При отработке конструкции ветвления очень полезно разобрать приведенный в материалах статьи алгоритм решения обобщенного квадратного уравнения (a может быть равно 0). Часто ученики не могут корректно сформулировать часть алгоритма, возникающую при a = 0. Кроме того, при написании соответствующей программы они часто используют сложные условия вида: if (a = 0) and (b = 0) and (c = 0) then …
На самом же деле в данном случае алгоритм реализуется через конструкцию ветвления, условием которой служит проверка на равенство a нулю, в зависимости от истинности этого условия выполняется либо последовательная конструкция (вычисление дискриминанта, проверка его знака и связанное с ней вычисление корней), либо снова конструкция ветвление и т.д.
В средней и старшей школе основное внимание необходимо уделять особенностям реализации базовых конструкций в различных языках программирования, т.е. синтаксису и семантике операторов выбора, цикла, присваивания (см. “Операторы языка программирования”).
