Данная статья является дополнением ранее опубликованного видео, поэтому перед прочтением рекомендуется его просмотреть.
Алгоритм - четкая последовательность действий (однозначных предписаний), задающая вычислительный процесс, результат выполнения которого полностью определен исходными данными.
Алгоритмы обладают следующими основными свойствами:
- дискретность – свойство, отражающее выполнение вычислительного процесса, задаваемого алгоритмом по шагам;
- детерминированность – свойство, означающее, что на каждом шаге любой полученный результат определяется результатами, полученными на предшествующих шагах;
- элементарность – свойство, согласно которому действие, которое выполняется на каждом шаге должно быть простым;
- направленность – свойство, обуславливающее необходимость указания, что является результатом того шага, на котором нельзя выполнить определенную в нем операцию;
- массовость – свойство, согласно которому алгоритм может быть применен к любой совокупности из допустимого множества исходных данных.
Алгоритм в силу своих свойств должен быть универсальным, сходящимся к результату за определённое количество шагов.
Одной и той же задаче может соответствовать множество алгоритмов. Поэтому возникает вопрос - какой алгоритм выбрать? При выборе алгоритма следует руководствоваться следующими показателями, присущими алгоритмам:
- временная сложность – показатель, отражающий время выполнения алгоритма или количество шагов его выполнения;
- емкостная сложность – показатель, по которому производят оценку количества данных, необходимых для выполнения алгоритма;
- сложность описания – показатель, отражающий длину описания алгоритма, количество инструкций операторов.
В результате проведения анализа задачи и алгоритмического конструирования формулируется алгоритм, обладающей некоторой сложностью, которую всегда стремятся уменьшить.
Применение структурного построения, при формулировании алгоритмов, позволяет уменьшить их сложность.
Структурное построение базируется на двух основных принципах:
- последовательная декомпозиция сверху вниз, когда исходная задача разбивается на подзадачи, до тех пора пока не будет достигнут приемлемый уровень сложности;
- использование структурного кодирования, а точнее применение методологии программирования, базирующейся на структурном подходе. Одной из таких методологий является структурное императивное программирование, которая заключается в задании хорошей топологии императивных программ, в том числе отказе от использования глобальных данных и оператора безусловного перехода, разработке модулей со слабой связностью и обеспечении их независимости друг от друга, что обеспечивает их переносимость из одного проекта в другой с целью повторного использования.
Целью структурного императивного программирования является повышение надежности программ, обеспечение возможности дальнейшего сопровождения и модификации, облегчение и ускорение разработки.
В основе методологии структурного императивного программирования лежат исследования и опыт учёных Коррадо Бёма и Джузеппе Якопини, которые сформулировали теорему о структурировании (1966 год): любой исполняемый алгоритм может быть преобразован к структурированному виду, то есть такому виду, когда ход его выполнения определяется только при помощи трёх управляющих алгоритмических конструкций: следование, ветвление и цикл.
Таким образом в основе построения структурированных программ лежат три базовые алгоритмические конструкции следование, ветвление и цикл. Более подробно они будут рассмотрены ниже.
Из теоремы Бёма-Якопини существует несколько следствий.
Следствие 1: всякую программу можно привести к форме, не использующей оператор безусловного перехода.
Следствие 2: любой алгоритм можно реализовать на языке, реализующем три управляющие конструкции - следование, ветвление, цикл.
Следствие 3: сложность структурированных программ ограничена, даже в случае их неограниченного размера.
Теперь рассмотрим базовые алгоритмические конструкции более подробно.
В базовой конструкции следование инструкции выполняются последовательно в том порядке, как они записаны в алгоритме, то есть одна за другой.
В базовой конструкции ветвление последовательность выполнения инструкций зависит от заданного условия.
В базовой конструкции цикл инструкции повторяются до тех пор, пока не изменится заданное условие, прекращающее итерационный процесс.
Описанные с помощью блок-схем базовые алгоритмические конструкции можно представить в виде псевдокода.
Базовая алгоритмическая конструкция следование в виде псевдокода будет выглядеть следующим образом.
Базовая алгоритмическая конструкция ветвление в виде псевдокода будет выглядеть следующим образом.
Приведённый псевдокод выглядит громоздко и, возможно, некоторым покажется, что он трудно читаем. Это действительно так. Дело в том, что блинные строки всегда читать сложнее коротких, поэтому рекомендуется каждую инструкцию начинать с новой строки. Данный псевдокод содержит два блока условий. Ниже показано как по-другому может выглядеть псевдокод и как его следует читать.
Блок1.
Если Условие 1 тогда
Инструкция 1;
В этом блоке в случае истинности Условия 1 будет выполнена Инструкция 1, а когда это условие ложно Инструкция 1 будет пропущена и управление передано второму блоку условий, идущему сразу за первым.
Блок 2.
Если Условие 2 тогда
Инструкция 2;
Иначе Если Условие 3 тогда
Инструкция 3;
...
Иначе
Инструкция N;
Во втором блоке условий в случае истинности Условия 2 будет выполнена Инструкция 2 и управление будет передано инструкции, стоящей после блока условий, а иначе (когда Условие 1 ложно) Инструкция 2 будет пропущена и управление перейдёт к Условию 3. Если Условие 3 истинно будет выполнена Инструкция 3 и управление будет передано инструкции, стоящей после блока условий, а иначе (когда Условие 2 ложно) Инструкция 3 будет пропущена и управление перейдёт к условию, стоящему после Условия 3 и так далее. Если ни одно из условии в блоке не выполнилось управление будет передано Инструкции N, то есть в секцию "иначе".
Базовая алгоритмическая конструкция "Цикл (с предусловием)" в виде псевдокода будет выглядеть следующим образом.
Читается этот псевдокод следующим образом: пока Условие N истинно выполнять Инструкцию N. Как только Условие N становится ложным (false) - цикл прерывается и управление передаётся Инструкции N+1. При необходимости, в эту конструкцию можно добавить нц (начало цикла) и кц (конец цикла), что позволит более явно выделить границы тела цикла (набор исполняемых в цикле инструкций).
Базовая алгоритмическая конструкция "Цикл (с постусловием)" в виде псевдокода будет выглядеть следующим образом.
Читается этот псевдокод следующим образом: выполнять Инструкцию N пока Условие N истинно. Как только Условие N становится ложным (false) - цикл прерывается и управление передаётся Инструкции N+1.
В ближайшем времени выйдет ещё одна статья, в которой базовые алгоритмические конструкции ветвление и цикл будут рассматриваться в разных формах на конкретных примерах. Не пропустите :)