В рамках определения понятия функционального блока и правила вложенности структур [1] полная структура данного алгоритма должна содержать некоторое количество уровней вложенности. В самом верху этой конструкции, на нулевом уровне вложенности, находится один функциональный блок – формулировка исходной (формализованной) задачи, а в самом нижнем уровне вложенности находятся элементарные функциональные блоки и/или вспомогательные алгоритмы.
Структура алгоритма на данном уровне вложенности
Рассмотрим структуру алгоритма на некотором внутреннем (то есть, не нулевом, не первом и не последнем) уровне вложенности.
На данном уровне вложенности структура алгоритма должна содержать один или несколько функциональных блоков - это основное требование формирования данного уровня вложенности.
Следовательно, структура алгоритма на данном уровне вложенности может быть только линейной последовательностью функциональных блоков. Каждый из этих функциональных блоков может быть либо элементарным функциональным блоком, либо функциональным блоком со сложной структурой.
Важно отметить, что линейная последовательность функциональных блоков данного уровня вложенности может быть связанная, то есть имеем последовательность функциональных блоков. При этом последовательность выполнения этих блоков жестко определенная.
Линейная последовательность функциональных блоков связанная, если эти блоки относятся к одному и тому же функциональному блоку предыдущего уровня вложенности. В противном случае, будем иметь линейную кусочно-связанную последовательность блоков.
Поясним данную мысль примерами.
Пример №1. Задан фрагмент алгоритма решения задачи, представленный в виде сценария:
НАЧАЛО_АЛГОРИТМА
- ПОСТАНОВКА ЗАДАЧИ:
- ПОСТРОЕНИЕ АЛГОРИТМА:
- РЕАЛИЗАЦИЯ АЛОГОРИТМА:
- Составление документации.
КОНЕЦ_АЛГОРИТМА
Каждое из этих четырех предложений можно рассматривать как вспомогательный алгоритм, являющийся одноуровенным; то есть имеем линейную последовательность, состоящую из четырех линейных функциональных блока, действующих в данном алгоритме последовательно друг за другом. Схематически можно представить:
ПРИМЕР №2. Задан фрагмент алгоритма, представленный в виде псевдокодов:
{1} * Начало цикла с постусловием
{2} * * ВЫВОД (“Ввести N[целое]>а”);
{3} * * ВВОД (N);
{4} * Конец цикла ЕСЛИ Х>а
{5} * MAX:=0
{6} * НАЧАЛО цикла с параметром I=1,10,1
{7} * * ВЫВОД(‘ВВЕСТИ ЦЕЛОЕ ЧИСЛО 1<=X<=100’)
{8} * * ВВОД(X)
{9} * * НАЧАЛО если MAX>X
{10} * * * ТО МАХ:=Х
{11} * * КОНЕЦ если
{12} * КОНЕЦ цикла с параметром I
{13} * ВЫВОД (МАХ)
Здесь цифры, заключенные в фигурные скобки, – это комментарии, используемые в начале строк для обозначения их номеров.
Строки №№1-4 относятся к одному циклическому функциональному блоку более высокого уровня (начало – строка №1, а условие выхода из цикла и его конец – строка №4). Строки №№2,3 описывают линейные связанные функциональные блоки более низкого уровня вложенности.
В строке №5 описан линейный функциональный блок.
Строки №№6-12 относятся к другому циклическому функциональному блоку (цикл с параметром). Вход и выход циклического функционального блока описаны в строках №6 и №12 соответственно. Тело цикла описано в строках №№ 7-11. В данном фрагменте в теле цикла имеется вложенное ветвление, описанное в строках №№9-11, вход и выход, которого располагаются в строках №№9, 11 соответственно.
Следовательно, для второго уровня вложенности (количество звездочек определяет номер уровеня вложенности) можно построить линейную последовательность функциональных блоков:
Цикл линейный блок цикл вспомогательный алгоритм
Числа, расположенные в прямоугольниках указывают на соответствующие этим функциональным блокам номера строк.
Следовательно, для данного уровня вложенности имеем линейно связанную последовательность функциональных блоков.
Для следующего уровня вложенности имеем:
- для строк №№2,3 и №№7,8 описание вспомогательных алгоритмов по одному на каждой строке;
- для строк №№9, 11 описание входа (и условия) и выхода в/из функционального ветвящегося блока,
- в строке №10 дается описание ветви ветвления.
Следовательно, для данного уровня вложенности получаем
То есть на втором уровне вложенности имеем две линейно связанные последовательности функциональных блоков, относящихся к разным функциональным блокам первого уровня вложенности.
Таким образом, на данном уровне вложенности можно построить линейно связанную последовательность функциональных блоков, относящуюся к одному функциональному блоку более высокого уровня вложенности. А в общем виде будем иметь кусочно-связанную линейную последовательность функциональных блоков, каждая из которых относится к одному функциональному блоку более высокого уровня вложенности.
Вложенные структуры алгоритма
Очевидно, что вложенные структуры возможны лишь для двухуровенных структур, а именно, ветвления и цикла, у которых ветви ветвления и тело цикла находятся на втором, относительно входа и выхода, уровне вложенности. Действия (или шаги) ветвей ветвления как и тела цикла рассматриваются как функциональные блоки. Это позволяет построить в общем виде кусочно-связанную линейную последовательность функциональных блоков данного уровня вложенности.
В случае, если в данной последовательности данного уровня вложенности имеется ветвление и/или цикл, то можно говорить о необходимости построения третьего уровня вложенности относительно исходного.
Отметим еще раз, что, если функциональный блок – линейный, то далее ни о каких вложенных структурах для данного построения речи быть не может, так как линейный функциональный блок-одноуровенный.
К алгоритму вложенного ветвления в ветвлении приводят задачи определения значения функции по заданному значению аргумента, если на разных отрезках Х функциональные зависимости Y = f(X) различные (смотри Приложение №1).
Простейшими примерами вложенных структур в цикл можно предложить задачи с массивами:
- вложенность линейного блока в цикл – задача определения суммы или произведения значений элементов заданного массива;
- вложенность ветвления в цикл – задача определения максимального (или минимального) элемента для заданного массива;
- цикл вложенный в цикл – например, задача ввода значений элементов двумерного массива.
Продемонстрируем фрагменты соответствующих алгоритмов:
Заключение
Обобщая изложенное, можно сказать следующее:
- для данного уровня вложенности структура алгоритма может быть только линейной последовательностью функциональных блоков;
- данная последовательность будет линейно связанной или линейно - кусочно – связанной;
- следующий уровень вложенности может формироваться только и только ветвящимися и/или циклическими функциональными блоками.
Литература
- Глущенко Ю. В., Глущенко Т. В. структурные элементы алгоритма. – http://festival/1sept.ru.