Структурные элементы алгоритма
Структурным элементом алгоритма является простое действие. Но данный подход в плане систематики ничего не даст. Именно поэтому за структурный элемент логичнее принять шаг алгоритма.
По определению шаг алгоритма может быть простым, если содержит только одно действие. И он будет сложным, если шаг алгоритма состоит из нескольких действий. Именно эти различия шагов алгоритма и позволяют ввести понятия базовых структур алгоритмики и понятие вспомогательного алгоритма.
Базовые структуры алгоритмики
К базовым структурам алгоритмики относятся основные типы алгоритма:
- линейный,
- ветвящийся,
- циклический.
Линейного тип алгоритма имеет внешне простую структуру. В пределе – это простой шаг.
Ветвящийся тип алгоритма имеет более сложную структуру относительно линейного типа, так как в ветвях ветвления имеем и линейные блоки, в частности – это вспомогательные алгоритмы, но в любом случае – это сложный шаг алгоритма.
Циклический тип алгоритма, как и ветвящийся имеет более сложную, относительно линейного типа, структуру, так как в теле цикла имеет линейный блок, в частности – это вспомогательный алгоритм, но в любом случае – это сложный шаг алгоритма.
Уровни вложенности структур алгоритма
Понятие уровня вложенности вводится на базовых структурах алгоритмики.
Правило уровней вложенности структур гласит:
- Для линейного типа считается, что он не имеет вложенности, то есть его вход и выход, как и сам линейный блок, находится на одном уровне вложенности.
- Для двух других типов алгоритмов можно сказать, что они располагаются на двух уровнях. На первом из них располагаются вход в структуру, выход из нее, условие (ветвления, входа в цикл или выхода из цикла), на втором, ветви ветвления или операторы тела цикла.
- Уровень вложенности считается тем выше, чем меньше его номер; например, первый уровень вложенности выше второго, а третий – выше пятого и т. д.
Пример рассмотрения уровней вложенности можно видеть в Приложении №1
Функциональные блоки
В рамках базовых структур и понятия вложенности структур можно ввести понятие функционального блока.
Под функциональным блоком будем понимать выделенную часть алгоритма, обладающую следующими свойствами:
- наличие одного входа и одного выхода,
- наличие в нем, по крайней мере, одной базовой структуры (то есть вполне законченное действие);
- базовые структуры, входящие в функциональный блок, находятся в нем полностью;
- как следствие предыдущего свойства, и вход, и выход функционального блока находящиеся на одном уровне вложенности;
- элементы функционального блока могут находиться как на уровне вложенности для входа и выхода так и на более низком уровне.
Дадим следующее определение функциональному блоку:
Опр. функциональным блоком называется выделенная часть алгоритма, выполняющая вполне законченное действие с информацией и имеющая один вход и один выход, находящиеся в данном алгоритме на одном уровне вложенности.
В схемах алгоритма с выделенными функциональными блоками межблочным разделителем используется символ "o".
Следовательно, функциональный блок, как единое целое, можно рассматривать как линейный блок, имеющий любую по сложности структуру, объединенную в один блок.
Исходя из изложенного, можно ввести понятие основных (элементарных, простейших) функциональных блоков.
Опр. функциональный блок называется ОСНОВНЫМ (ЭЛЕМЕНТАРНЫМ), если в его составе имеется либо один линейный блок, либо одно ветвление, либо один цикл.
По типу будем различать три основных (элементарных) функциональных блока:
- линейный,
- ветвящийся,
- циклический.
Дадим им определения.
Опр. ФУНКЦИОНАЛЬНЫЙ БЛОК называется ОСНОВНЫМ (ЭЛЕМЕНТАРНЫМ) ЛИНЕЙНЫМ, если он имеет только одно действие (простой шаг алгоритма).
Опр. ФУНКЦИОНАЛЬНЫЙ БЛОК называется ОСНОВНЫМ (ЭЛЕМЕНТАРНЫМ) ВЕТВЯЩИМСЯ, если он имеет только одну ветвящуюся структуру, в каждой ветви которого может располагаться не более одного элементарного линейного блока.
Опр. ФУНКЦИОНАЛЬНЫЙ БЛОК называется ОСНОВНЫМ ЦИКЛИЧЕСКИМ, если он имеет только одну циклическую структуру, в теле которого может располагаться не более одного элементарного линейного блока.
Основные функциональные блоки – это “кирпичики”, из которых строится алгоритм. Действительно, комбинация основных функциональных блоков, построенная по правилам вложенности, позволяет построить более сложный по структуре функциональный блок (с обязательным требованием одного входа и одного выхода на одном уровне вложенности).
Таким образом, алгоритм любой решаемой задачи можно рассматривать как функциональный блок со сложной структурой, который, в свою очередь, можно рассматривать как комбинацию функциональных блоков.
В Приложении №2 рассмотрена задача выделения функциональных блоков в заданном алгоритме.
Вспомогательные алгоритмы (подалгоритмы).
Строго говоря структурных элементов три: линейный, ветвящийся и циклический, - это и основные (элементарные) функциональные блоки.
В рамках понятий уровня вложенности и функционального блока можно определить построение такого элемента алгоритма, как вспомогательный алгоритм (подалгоритм).
Действительно, если выделенный фрагмент алгоритма является функциональным блоком на данном уровне вложенности, то его можно рассматривать в данном алгоритме как вспомогательный алгоритм.
Алгоритм построения подалгоритма в данном алгоритме имеет вид:
- доказать, что выделенный фрагмент является функциональным блоком;
- увеличить уровень вложенности всем элементам подалгоритма на один,
- на исходном уровне вложенности ввести сверху строку НАЧАЛА_подалгоритма, а внизу – КОНЕЦ_подалгоритма;
- для данного подалгоритма задать уникальное имя (в рамках данного алгоритма),
- определить переменные входного и выходного потоков.
Синтаксически, для представления алгоритмов, пока допускается некий произвол в оформлении подалгоритма, практика показывает, что удобно использовать следующее:
Подалгоритм <имя_подалгоритма>(<список входных переменных>;<список выходных переменных>)
Внутри списков имена входных и выходных переменных разделяются запятыми.
В данном алгоритме важно знать имя и параметры ввода/вывода вспомогательного алгоритма и совершено нет необходимости знать его структуру. Именно поэтому вспомогательный алгоритм в данном алгоритме на уровне вложенности, где он определен, рассматривается как линейный функциональный блок и именно поэтому вспомогательный алгоритм можно рассматривать как структурный элемент алгоритма.
В программном представлении заданного алгоритма подалгоритм представляется как процедура или функция, синтаксис представления которых (способ кодирования) зависит от особенностей и возможностей используемого языка программирования.
В Приложении №3 приведен пример построения вспомогательного алгоритма для заданного фрагмента алгоритма.
Заключение
К базовым структурам алгоритмики относятся основные типы алгоритма: линейный, ветвящийся, циклический. Это позволяет ввести понятия вложенности структур алгоритма и функционального блока.
Все это позволяет определить построение вспомогательного алгоритма (подалгоритм). В данном алгоритме важно знать имя и параметры ввода/вывода вспомогательного алгоритма и совершено нет необходимости знать его структуру. Именно поэтому вспомогательный алгоритм в данном алгоритме на уровне вложенности, где он определен, рассматривается как линейный функциональный блок и именно поэтому вспомогательный алгоритм можно рассматривать как структурный элемент алгоритма.
Обобщения
Изложенное позволяет утверждать:
- Структурных элементов алгоритма – четыре: три базовых структуры и вспомогательный алгоритм.
- Два из них определены как одноуровенные – это элементарный линейный блок и вспомогательный алгоритм, а два как двухуровенные – это ветвление и цикл.
- В данном алгоритме используемый подалгоритм рассматривается только как линейный блок, при этом его внутренняя структура может быть очень сложной.
- Любой подалгоритм должен быть функциональным блоком, но не любой функциональный блок обязательно должен быть подалгоритмом;
- Вспомогательный алгоритм строится как комбинация элементарных функциональных блоков, то есть комбинация базовых структур.