Графическое представление алгоритмов

Алгоритм, составленный для некоторого исполнителя, можно представить различными способами: с помощью графического или словесного описания, в виде таблицы, последовательностью формул, записанным на алгоритмическом языке (языке программирования). Остановимся на графическом описании алгоритма, называемом блок-схемой. Этот способ имеет ряд преимуществ благодаря наглядности, обеспечивающей, в частности, высокую «читаемость» алгоритма и явное отображение управления в нем.

Прежде всего определим понятие блок-схемы. Блок-схема — это ориентированный граф, указывающий порядок исполнения команд алгоритма; вершины такого графа могут быть одного из трех типов (рис. 2.2).

Рис. 2.2. Три типа вершин графа

На рис. 2.2 изображены «функциональная» (a) вершина (имеющая один вход и один выход); «предикатная» (б) вершина, имеющая один вход и два выхода (в этом случае функция Р передает управление по одной из ветвей в зависимости от значения Р (Т, т. е. true, означает «истина», F, т. е. false — «ложь»); «объединяющая» (в) вершина (вершина «слияния»), обеспечивающая передачу управления от одного из двух входов к выходу. Иногда вместо Т пишут «да» (либо знак +), вместо F- «нет» (либо знак -).

Из данных элементарных блок-схем можно построить три блок-схемы, имеющих особое значение для практики алгоритмизации.

Следование — самая важная из структур. Она означает, что действия могут быть выполнены друг за другом:

Рис. 2.3. Структура «следование»

Эти прямоугольники могут представлять как одну единственную команду, так и множество операторов, необходимых для выполнения сложной обработки данных.

Ветвление — это структура, обеспечивающая выбор между двумя альтернативами. Выполняется проверка, а затем выбирается один из путей.

Эта структура называется также «ЕСЛИ — ТО — ИНАЧЕ», или «развилка». Каждый из путей (ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение программы продолжается независимо от того, какой путь был выбран.

Рис. 2.4. Структура «ветвление»

Может оказаться, что для одного из результатов проверки ничего предпринимать не надо. В этом случае можно применять только один обрабатывающий блок:

Рис. 2.5. Структура «неполное ветвление»

Цикл (или повторение) предусматривает повторное выполнение некоторого набора команд программы. Если бы циклы не существовали, вряд ли занятие программированием было бы оправданным: циклы позволяют записать длинные последовательности операций обработки данных с помощью небольшого числа повторяющихся команд.

Цикл начинается с проверки логического выражения. Если оно истинно, то выполняется «a», затем все повторяется снова, пока логическое выражение сохраняет значение «истина». Как только оно становится ложным, выполнение операций «а» прекращается и управление передается по программе дальше.

Рис. 2.6. Структура цикла «пока»

Рис. 2.7. Структура цикла «до»

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

Еще одним важным компонентом структурного подхода к разработке алгоритмов является модульность. Модуль — это последовательность логически связанных операций, оформленных как отдельная часть программы. Использование модулей имеет следующие преимущества:

• 1) возможность создания программы несколькими программистами;
• 2) простота проектирования и последующих модификаций программы;
• 3) упрощение отладки программы — поиска и устранения в ней ошибок;
• 4) возможность использования готовых библиотек наиболее употребительных модулей.

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

На практике при составлении блок-схем оказывается удобным использовать и другие графические знаки (некоторые из них приведены на рис. 2.8).

Рис. 2.8. Некоторые дополнительные конструкции для изображения блок-схем алгоритмов