3.3. Графическая форма записи
Наиболее удобным способом записи несложных (небольших) алгоритмов на первых этапах его разработки является графическая форма записи. Другое распространенное название данной формы – блок-схема алгоритма. Блок-схемой алгоритма называется такое графическое изображение алгоритма, в котором этапы решения задачи изображаются в виде различных геометрических фигур. Внутри этих фигур указывается содержание данного этапа вычисления, причем, если описание является громоздким, внутри блока ставится номер этапа вычисления, а описание дается в приложении к блок-схеме.
Геометрические фигуры (блоки) соединяются стрелками, показывающими направление развития вычислительного процесса. Иногда возле стрелок делают надписи, показывающие, при каких условиях происходит выбор данного направления. В данной форме для представления отдельных блоков алгоритма используются обусловленный набор геометрических фигур. Приняты следующие основные (базовые) обозначения:
Графическая форма предназначена, безусловно, только для исполнителя «человек» – в этом ее основной недостаток. Главное достоинство такой формы представления – наглядность. Блок-схема позволяет охватить весь алгоритм сразу, отследить различные варианты его выполнения. На стадии разработки в блоках можно делать записи как на естественном, так и на формальном языке. Именно по этой причине блок-схема считается весьма полезной формой при обучении алгоритмизации, а также при разработке сложных алгоритмов. Однако в блок-схеме, как правило, отсутствует подробное описание конкретных действий – их существование лишь обозначено.
По блок-схеме гораздо проще осуществляется запись алгоритма на каком-либо формальном языке. Правда, следует заметить, что синтаксическое богатство языков программирования выше языка блок-схем – по этой причине не все языковые конструкции имеют простое графическое представление – примером может служить конструкция цикла с параметром FOR … DO (или FOR … NEXT), не имеющая собственного представления в базовом языке блок-схем.
3.4. Управляющие структуры
После того, как были рассмотрены возможные способы записи алгоритмов, вполне закономерным представляется вопрос о технологии их разработки. До середины 60-х годов теории разработки алгоритмов не существовало – процесс разработки целиком определялся опытом и искусством программиста. Однако по мере роста сложности программ возникла необходимость создания методологии разработки программ, и она появилась в виде структурного программирования. Идеи структурного программирования были высказаны в 1965 г. Э. Дейкстрой, но сведены в некую законченную систему правил они не были. В том же году итальянские математики К. Бом и Д. Джакопини сформулировали теорему о структурности. Прежде, чем рассмотреть ее суть, необходимо ввести некоторые понятия.
Поскольку алгоритм определяет порядок обработки информации, он должен содержать, с одной стороны, действия по обработке, а с другой стороны, порядок их следования, называемым потоком управления.
Рассмотренные выше блоки, связанные с обработкой данных, делятся на простые и условные. Особенность простого действия в том, что оно имеет один вход и один выход, в отличии от условного, обладающим двумя выходами в зависимости от того, истинным ли окажется условие. Простое действие не означает, что оно единственное – это может быть некоторая последовательность действий.
Часть алгоритма, организованная как простое действие, т.е. имеющая один вход (выполнение начинается всегда с одного и того же действия) и один выход (т.е. после завершения данного блока всегда начинает выполняться одно и то же действие), называется функциональным блоком.
Из этого определения, в частности, следует, что каждое простое действие является функциональным блоком, а условное – нет.
Согласно положениям структурного программирования можно выделить всего три различных варианта организации потока управления действиями алгоритма. Поток управления может обладать следующими свойствами:
каждый блок выполняется не более одного раза;
выполняется каждый блок.
Поток управления, в котором выполняются оба эти свойства, называется линейным – в нем несколько функциональных блоков выполняются последовательно. Линейному потоку на языке блок-схем соответствует структура:
Очевидно несколько блоков, связанных линейным потоком управления, могут быть объединены в один функциональный блок:
Второй тип потока управления называется ветвлением – он организует выполнение одного из двух функциональных блоков в зависимости от значения проверяемого логического условия. Блок-схема структуры:
В этом типе выполняется свойство (1), свойство (2) – нет. Если структура содержит два функциональных блока (S1 и S2), ветвление называется полным; возможно существование неполного ветвления – при этом один из блоков пуст (обычно S2).
Третий тип потока управления называется циклическим – он организует многократное повторение функционального блока, пока логическое условие его выполнение является истинным. Для циклического потока выполняется свойство (2), но не выполняется (1). Его блок-схема показана на рисунке.
Поскольку ветвление и циклический типы управления имеют один вход и один выход, они в целом также подходят под определение функционального блока. Введем рекурсивным образом понятие стандартного функционального блока:
каждое простое действие есть стандартный функциональный блок;
каждая из описанных трех управляющих структур является стандартным функциональным блоком, если все входящие в них блоки являются стандартными функциональными;
других стандартных функциональных блоков не существует.
Определим еще одно понятие:
Алгоритм называется структурным, если он может быть представлен стандартным функциональным блоком.
Другими словами, структурный алгоритм представляет собой комбинацию трех рассмотренных выше структур (иногда они называются базовыми алгоритмическими структурами). Безусловно, не все алгоритмы являются структурными. Однако именно структурные алгоритмы обладают рядом замечательных преимуществ по сравнению с неструктурными алгоритмами:
понятность и простота восприятия алгоритма (поскольку невелико число исходных структур, которыми он образован);
проверяемость (для проверки любой из основных структур достаточно убедиться в правильности входящих в нее функциональных блоков);
модифицируемость (она состоит в простоте изменения структуры алгоритма, поскольку составляющие блоки относительно независимы).
После введенных определений можно сформулировать структурную теорему Бома-Джакопини:
любой алгоритм может быть сведен к структурному.
Или по-другому:
любому неструктурному алгоритму может быть построен эквивалентный ему структурный алгоритм.
Значение структурной теоремы для практики программирования состоит в том, что на ее основе разработан и широко используется структурный метод программирования. Основой метода является использование принципа модульности построения сложных программ. При этом каждый программный модуль организуется в виде стандартного функционального блока (т.е. строится только из трех базовых структур) и выполняет лишь одну функцию по обработке данных. В идеале каждый такой модуль должен иметь один вход и один выход. Модули обладают определенной автономностью, что позволяет их отладку (т.е. поиск и устранение ошибок) вести независимо от остальной программы, а также обеспечивает относительно простую модифицируемость как отдельного модуля, так и программы в целом. Эффективность метода структурного программирования особенно заметна при создании сложных программ. Модульный принцип позволяет разбить общую задачу на составные и относительно автономные части, каждая из которых может создаваться и отлаживаться независимо (и даже разными разработчиками); безусловно, такое разбиение требует согласования входных и выходных параметров модулей.