Структурный подход при разработке алгоритмов

Процесс разработки алгоритмов и программ достаточно сложен и содержит некоторые элементы творчества. Для одной и той же задачи возможно множество алгоритмов ее решения, различающихся сложностью и эффективностью, и как правило, программы, реализующие различные алгоритмы отличаются сложностью, эффективностью и количеством допущенных логических ошибок. На выявление логических ошибок, а также на модификацию разрабатываемых участков программы уходит значительная часть времени программистов. Поэтому разрабатываемые алгоритмы должны быть простыми и понятными, легко проверяемы и допускать возможность ее модификации без существенной перестройки всей конструкции.

Для достижения указанных свойств при разработке алгоритмов придерживаются особой методики, называемой структурным подходом. Суть этого подхода - применение некоторых базовых структур алгоритмов. Применение их снижает вероятность появления ошибок при разработке алгоритмов, повышает надежность, упрощает понимание и модификацию алгоритмов. При структурном подходе к конструированию алгоритмов алгоритмы как бы составляются из следующих базовых структур: следование, развилка, выбор, цикл, каждая из которых имеет один вход и один выход.

Алгоритм решения любой логической задачи можно составить только из них. При описании структур употребляются специальные обозначения для действий обработки информации, проверки условия, выбора действия и слияния соединительных линий (Рис.3.14).

Функциональный узел включает действие, которое необходимо выполнить. Решение по условию определяет порядок выхода (выбирается один из выходов, но не оба сразу) в соответствии с тем, какое значение принимает результат проверки условия: " истина" или " ложь". Решение по коду определяет порядок выхода (выбирается один из выходов) в соответствии с тем, какое значение принимает код.

№ п.	Название	Обозначение	Примечание
1.	Узел обработки или функциональный узел
2.	Решение по условию		Р – некоторое логическое условие
3.	Решение по коду		К – значение кода
4.	Узел слияния

Рис.3.14 Обозначения, принятые при описании структур алгоритмов

Узел слияния изменений данных не предусматривает. Это просто соединение с двумя входами и одним выходом. Если требуется соединение произвольного без преобразования сигналов количества входов, то такую конструкцию можно представить в виде последовательности узлов слияния (рис.3.15).

Ниже приведены изображения базовых структур.

Следование. Эта базовая структура состоит из двух функциональных блоков, размещенных и выполняемых последовательно друг за другом (Рис. 3.16).

Любое обозначение обработки можно заменить следованием, но, повторяя эту замену, можно изобразить последовательное исполнение любого количества функций. Следование - это такая структура, в которой ряд операции выполняется в линейном порядке.

Развилка - состоит из логического элемента и одного или двух функциональных узлов. Эта структура обеспечивает выбор между двумя ветвями. Развилка может быть двух видов: полная условная конструкция, когда в каждой ветви присутствует функциональный узел и неполная условная конструкция, когда функциональный узел присутствует только в одной из ветвей. Каждая из ветвей ведет к общей точке слияния. Выбираемые пути могут обозначаться метками: истина/ложь (T/F), да/нет, +/- и т.п. Полная условная конструкция схематически может быть представлена рисунком 3.17. Неполная условная конструкция имеет место тогда, когда одному из результатов проверки не требуется выполнение функционального блока (рис.3.18).

Выбор - состоит из логического узла проверки состояния кода и множества функциональных узлов. Эта структура обеспечивает выбор из множества n ветвей, каждая из которых может содержать функциональный узел, либо быть пустой. Все ветви сливаются в одной точке. Схематически базовая структура выбор изображено на рис.3.19.

В зависимости от состояния кода выбирается та или иная ветвь.

Базовая структура цикл может быть двух видов: цикл - пока и цикл - до. Базовая структура цикл - пока имеет вид рис.3.20. Вначале проверяется условие Р. Если Р истинно, то многократно выполняется действие S. Если условие становится ложным, то цикл завершается. Действие S циклически выполняется при последовательных значениях по крайней мере одного параметра. Так как условие проверяется до действия S, то оно может ни разу не выполниться. При выполнении действия S параметры условия Р должны изменяться, иначе программа зациклится.

Базовая структура цикл - до имеет вид на рис.3.21.

цикл - до обеспечивает многократное выполнение действия S также, как и цикл - пока, за исключением двух моментов.

1. Проверка условия производится после выполнения действия S, поэтому действие S выполняется хотя бы один раз.

2. цикл - до завершается, когда Р истинно, а цикл - пока тогда, когда Р ложно.

Любой алгоритм может быть разработан с использованием только базовых структур. Функциональные узлы S1, S2 и S, в свою очередь, могут представлять собой любую базовую структуру. Конструируемые таким образом алгоритмы имеют четкую и ясную структуру, легко поддаются проверке.

Пример: Алгоритм поиска большего из трех чисел (А, В, С). Алгоритм представляет собой следование двух развилок (рис.3.22). В первой (полная конструкция) отыскивается большее из двух чисел А и В. Большее из них становится значением переменной Y. Во второй (неполная конструкция) значение Y сравнивается с третьм числом, и если Y < С, то Y заменяется значением С.

Рассмотренные структуры: Следование, Развилка, Цикл, Выбор - могут сочетаться в любой последовательности, составлять несколько уровней вложенности одна в другую. Например, в схеме рис.3.23 функциональные узлы S₁ и S₂ представляют собой структуры Следование рис.3.24, а, б. В свою очередь узлы S₁₂ и S₂₂ представляют собой соответственно структуры Цикл-пока (структура типа whiledo) и Цикл-до (структура типа dountil) рис.3.25. В результате развернутая схема будет иметь вид рис.3.26. Следовательно, любой функциональный узел может быть заменен любой базовой структурой.