Понятие алгоритма, его свойства и способы описания
Алгоритм – это точное предписание о выполнении в определенном порядке некоторой системы операций (шагов) для решения всех задач некоторого типа.
Точно указать шаги в алгоритме с помощью естественного языка, в силу его неоднозначности, достаточно сложно. Поэтому обращаются к символьным, то есть искусственным языкам. Наиболее распространенными формами искусственных языков, используемых для представления алгоритмов, являются:
- формульное описание, предназначенное для представления процесса решения несложных задач, базирующихся на локальных вычислениях;
- задание алгоритмов в виде блок-схем, широко распространенное для представления большого числа логических условий;
- словесное описание правил в виде фраз естественного языка с ограниченным синтаксисом.
Формульное описание алгоритма
Примером задания алгоритма в формульном виде может служить представление процесса начисление заработной платы сотруднику:
Задание алгоритмов с помощью блок-схем
Достаточно часто алгоритмы записываются в виде блок-схем, которые являются графическим представлением последовательности действий. В этом случае, они состоят из отдельных блоков. Их начертание определено российским стандартом ГОСТ 19.701-90 (единой системой программной документации), который разработан путем прямого применения международного стандарта ISO 5807-85.
Блоки алгоритма отражают содержание элементарного действия, а связывающие их направленные линии – последовательность выполнения. Для создания блок-схем используют стандартные графические изображения.
Рис. 6.16. Основные графические изображения, используемые при описании алгоритмов.
Блоки могут связываться в одну из следующих конструкций:
линейная (последовательная);
простой выбор;
множественный выбор;
цикл.
Рассмотрим представление некоторых основных алгоритмических конструкций с помощью блок-схем.
Линейный алгоритм
Блок схема рассмотренного ранее линейного алгоритма вычисления значения «F» в графической форме, представлена на рис.6.17)
Рис.6.17. Линейная конструкция алгоритма
Линейная структура указывает на последовательность операций, которые следует выполнить в определенной последовательности.
Простой выбор
Конструкция «простой выбор» реализует правило: если выполняется ‹условие 1›, то производится Операция 1, иначе производится Операция 2 (см. рис.6.21).
Рис.6.18. Изображение алгоритма простого выбора на блок-схеме
Рис.6.19. Пример конструкции «простой выбор»
Множественный выбор
Конструкция ”множественный выбор” используется в том случае, если имеется несколько вариантов условий, которые отражают взаимоисключающие случаи. Добавим в предыдущий пример дополнительные условия
Рис.6.20. Пример конструкции «множественный выбор»
Цикл
Циклом называется многократно повторяемый участок вычислений. Вычислительный процесс, содержащий один или несколько циклов, называется циклическим. По количеству выполнения циклы делятся на циклы с определенным (заранее заданным) числом повторений и циклы с неопределенным числом повторений. Количество повторений последних зависит от соблюдения некоторого условия, задающего необходимость выполнения цикла.
Если условие проверяется в начале цикла - тогда речь идет о цикле с предусловием (Рис.6.21).
Рис.6.21 Фрагмент алгоритма цикла с предусловием
Если условие проверяется в конце цикла, то имеем дело с циклом с постусловием (рис.6.22).
Рис.6.22 Фрагмент алгоритма цикла с постусловием
Любой алгоритм, представленный блок-схемой, это образование из связанных между собой или вложенных друг в друга четырех конструкций перечисленных ранее. Описание алгоритма в виде блок-схемы хорошо обозримо и его легко модифицировать.
Существуют различные подходы к разработке алгоритмов. Большинство из них базируются на принципе «сверху – вниз» когда на начальных этапах разработки создается общая схема, содержащая основные крупные блоки. Далее производится их последовательная детализация, то тех пор, пока не станет возможным реализация алгоритма на языках программирования.
Однако, в ряде случаев уместно использования принципа «снизу вверх». Тогда используется заранее определенный и корректный набор подалгоритмов, на их основе создаются функционально завершенные подзадачи более высокого уровня. От них происходит переход к все более общим алгоритмам, до тех пор, пока не будет достигнуто решение поставленной задачи.
Сказанное выше можно проиллюстрировать следующей схемой (рис.6.23). На ней показано, что при нисходящем проектировании алгоритма (сверху-вниз), при создании модуля более высокого уровня (Модуль 1) нижестоящие подалгоритмы (в нашем случае Модуль 2 и Модуль 3) на первом этапе не детализируются.
Рис. 6.23. Схема, поясняющая разницу между двумя подходами при создании алгоритмов
Их разработкой занимаются уже после окончания работ над алгоритмом более высокого уровня.
При проектировании с использованием восходящего проектирования алгоритмов (рис. 6.26) сначала создаются (или берутся готовыми из библиотеки алгоритмов), модули нижнего уровня (в нашем случае это Модуль В и Модуль С), а затем на из основе формируется алгоритмический модуль более высокого уровня и, возможно, даже общий алгоритм решения поставленной задачи.
Словесное описание алгоритма
Если использование формульных зависимостей при создании алгоритмов не представляется возможным, то алгоритм можно задать в виде словесного описания правил с помощью синтаксически ограниченных фраз естественного языка.
Дальнейшим развитием этого подхода, является использование псевдокода. Псевдокод - компактный (зачастую неформальный) язык описания алгоритмов, использующий ключевые слова языков программирования, но опускающий несущественные подробности и их специфический синтаксис.
Псевдокод обычно опускает детали, так как главная его цель - обеспечить понимание алгоритма человеком, сделать описание более воспринимаемым, чем исходный код на языке программирования. Псевдокод широко используется в учебниках и научно-технических публикациях, а также на начальных стадиях разработки компьютерных программ.
Например, рассмотренный ранее алгоритм оформления счета на псевдокоде имеет следующий вид:
начало алгоритм оформления счета
нц для i:=1 до количество_строк делать
сумма_по_строке[i]:=количество_предметов[i]*цена[i];
кц;
сумма_счета:=0;
нц для i:=1 до количество_строк делать
сумма_счета:= сумма_счета + сумма_по_строке[i];
кц;
сумма_скидки :=0;
нц для i:=1 до количество_строк делать
если сумма_по_строке[i]<250000 и сумма_по_строке[i]>=100000 то
скидка[i]:= сумма_по_строке[i]*0.01;
сумма_скидки := сумма_скидки+ скидка[i];
конец_если;
если сумма_по_строке[i]<1000000 и сумма_по_строке[i]>=250000 то
скидка[i]:= сумма_по_строке[i]*0.025;
сумма_скидки := сумма_скидки+ скидка[i];
конец_если;
если сумма_по_строке[i]>=1000000 то
скидка[i]:= сумма_по_строке[i]*0.05;
сумма_скидки := сумма_скидки+ скидка[i];
конец_если;
кц;
сумма_счета:= сумма_счета- сумма_скидки;
затраты_на_доставку :=0;
нц для i:=1 до количество_строк делать
если срочность_доставки = истина то
затраты_на_доставку := затраты_на_доставку + вес[i]*10000;
иначе
затраты_на_доставку := затраты_на_доставку + вес[i]*1000;
конец если;
кц;
кц алгоритм оформления счета.
В этой записи начало алгоритма обозначено «начало алгоритм оформления счета», его конец «кц алгоритм оформления счета». Используется понятие оператора - наименьшей автономной исполняемой части языка псевдокода. Как правило, оператор заканчивается знаком «;», а весь алгоритм знаком «.».
В псевдокоде широко используются выражения: “:=” - операция присваивания, “+”, ”-“, “*” и “/” - операции сложения, вычитания, умножения и деления, соответственно, а также логические функции “и”, “или”, “не” (&, |, ^, and,or, not). Кроме численных, используются логические переменные, принимающие значения истина/ложь (true/false) и знаки “>”- больше, ”<”- меньше, “=”- равно.
Номера строк счета в описании алгоритма, обозначаются в квадратных скобках, как элементы массива с номером «i». Следует отметить, что ключевые слова в псевдокоде выделяются жирным шрифтом и/или подчеркиванием.