ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ АЛГОРИТМОВ
Алгоритм, составленный для некоторого исполнителя, можно представить различными способами: с помощью графического или словесного описания, в виде таблицы, последовательностью формул, записанным на алгоритмическом языке (языке программирования). Остановимся на графическом описании алгоритма, называемом блок-схемой. Этот способ имеет ряд преимуществ благодаря наглядности, обеспечивающей, в частности, высокую «читаемость» алгоритма и явное отображение управления в нем.
Прежде всего определим понятие блок-схемы. Блок-схема - это ориентированный граф, указывающий порядок исполнения команд алгоритма; вершины такого графа могут быть одного из трех типов (рис. 1.12).
Рис. 1.12. Три типа вершин графа
На рис. 1.12 изображены «функциональная» (a) вершина (имеющая один вход и один выход); «предикатная» (б) вершина, имеющая один вход и два выхода (в этом случае функция Р передает управление по одной из ветвей в зависимости от значения Р (Т,
т.е. true, означает «истина», F, т.е. false - «ложь»); «объединяющая» (в) вершина (вершина «слияния»), обеспечивающая передачу управления от одного из двух входов к выходу. Иногда вместо Т пишут «да» (либо знак +), вместо F- «нет» (либо знак -).
Из данных элементарных блок-схем можно построить четыре блок-схемы (рис. 1.13), имеющих особое значение для практики алгоритмизации.
Рис. 1.13. Основные алгоритмические структуры
На рис. 1.13 изображены следующие блок-схемы: а -
композиция, или следование; б - альтернатива, или развилка, в
и г -
блок-схемы, каждую из которых называют
итерацией, или циклом
(с предусловием (в), с постусловием (г)). S1 и S2 представляют собой в общем случае некоторые серии команд для соответствующего исполнителя, В - это условие, в зависимости от истинности (Т) или ложности (F) которого управление передаётся по одной из двух ветвей. Можно доказать, что для составления любого алгоритма достаточно представленных выше четырех блок-схем, если пользоваться их последовательностями и/или суперпозициями.
Блок-схема «альтернатива» может иметь и сокращенную форму, в которой отсутствует ветвь S2 (рис. 1.14, а). Развитием блок-схемы типа альтернатива является блок-схема «выбор» (рис. 1.14, б).
Рис. 1.14. Развитие структуры типа «альтернатива»;
о) - неполная развилка; б) -
структура «выбор»
На практике при составлении блок-схем оказывается удобным использовать и другие графические знаки (некоторые из них приведены на рис. 1.15).
Рис. 1.15. Некоторые дополнительные конструкции для изображения блок-схем алгоритмов
