Формы представления алгоритмов
Алгоритм, составленный для некоторого исполнителя, можно представить различными способами. Основными среди них являются:
- словесное описание алгоритма на естественном языке (вербальная форма);
- построчная запись алгоритма;
- блок-схема;
- указание формулы.
Рассмотрим особенности каждой из названных форм.
1) Словесное описание имеет минимум ограничений и является наименее формализованным. Однако при этом алгоритм получается и наименее строгим, допускающим появление неопределенностей. Алгоритм в вербальной форме может оказаться очень объемным и трудным для восприятия человеком.
Пример. Если числа равны, НОД равен одному из них. В противном случае надо из большего числа вычесть меньшее, полученную разность запомнить вместо значения большего числа и повторить все сначала.
2) В виде таблицы данных. Например y = x2
x |
1 |
2 |
3 |
y |
1 |
4 |
9 |
3) Аналитический. Указание формулы или последовательности формул, расчеты по которым нужно выполнить для получения результатов.
Пример. Вычислить объем круглого конуса. Для вычисления следует воспользоваться формулой V=1/3πr2h. При заданных размерах (r-радиус основания, h-высота конуса) эта формула дает предписание исполнителю, как действовать.
4) Построчная запись алгоритма. Это запись на естественном языке, но с соблюдением некоторых дополнительных правил:
шаги (предписания) алгоритма нумеруются;
исполнение алгоритма происходит в порядке возрастания номеров шагов, начиная с первого (если не встречается никаких специальных указаний);
Типичными шагами алгоритма являются:
1- чтение (ввод) данных, которое записывается в виде: чтение A,B,…,
где A,B,…-обозначение исходных данных;
2- обработка данных (вычисления) по формулам, записанная в виде V=…, где V-переменная, значение которой определяется как результат, полученный после выполнения операций, указанных в правой части. По-существу знак “=” обозначает специальную операцию, которая называется присвоением;
3- сообщение (вывод) результата, который имеет вид:
запись X,Y,…,
где X,Y,…-обозначение переменных, значение которых необходимо узнать;
4- проверка условия, которое записывается в виде:
Если … идти к N,
где вместо многоточия записывается условие, при выполнении которого осуществляется переход к шагу с номером N (если условие не выполняется, то производится переход к следующему по порядку шагу);
5- переход к шагу с номером N: идти к N;
6- конец вычислений: конец.
Пример. 1. чтение A,B;
2. Если A=B, идти к 7;
3. Если A>B, идти к 6;
4. B=B-A;
5. Идти к 2;
6. A=A-B;
7. НОД=А;
8. Запись НОД;
9. КОНЕЦ.
Построчная запись алгоритма позволяет избежать неопределенностей в алгоритме, не требует, по-существу, никаких специальных знаний (все, что написано, понятно) и в то же время обеспечивает отработку навыков логически строгого изложения хода решения задачи (последовательности вычислений, возможных вариантов перехода к различным шагам алгоритма и так далее) и облегчает последующее изучение алгоритмических языков.
Однако построчная запись алгоритма воспринимается человеком тяжело и требует большого внимания при изучении (или записи) алгоритмов в этой форме представления.
5) Изображение алгоритма в виде блок-схемы (графическое представление).
Графическое изображение алгоритма в виде блок-схемы отличается высокой степенью наглядности. Введем понятие блок-схемы.
Блок-схема – это ориентированный граф, указывающий порядок исполнения команд алгоритма. Другими словами, блок-схема состоит из соединенных между собой стрелками (линиями потока) блоков различного вида и необходимого количества комментариев.
Выполнение алгоритма всегда начинается с блока начало и оканчивается при попадании на блок конца. Порядок вычислений определяется стрелками.
Вершины
графа могут быть одного из трех типов:
1) “функциональная” вершина (имеет один вход и один выход);
2
)
“предикатная” вершина (один вход, два
выхода; в этом случае функция Р передает
управление по одной из ветвей в зависимости
от значения Р)
3) “объединяющая” (вершина “слияния”), обеспечивает передачу управления от одного из двух входов к выходу.
Структурная
блок-схема алгоритма представляет
блок-схему, которая может быть выражена
как композиция из четырех элементарных
блок-схем:
а
)
композиция (следование). Такая
структура предполагает однократное
выполнение одной и той же последовательности
шагов при любых наборах исходных данных.
б) развилка (альтернатива).
Д
ля
разветвляющейся структуры также
характерно однократное выполнение
последовательности шагов, однако состав
этой последовательности определяется
результатами проверки некоторого
условия, то есть зависит от обрабатываемой
информации.
Блок-схема может иметь и сокращенную форму, в которой отсутствует ветвь S1 или иметь расширенную форму, когда количество выборов больше двух.
б/) неполная развилка
б//) выбор
в, г) итерация (повторение, цикл)
Циклическая структура обеспечивает многократное выполнение одной и той же последовательности шагов тела цикла с модифицируемой (изменяемой) информацией.
В общем случае S1 и S2 представляют собой серии команд для соответствующего исполнителя; B – это условие, в зависимости от истинности (+,T) или ложности (-, F) которого управление передается по одной из ветвей.
Важной особенностью приведенных структур является то, что они имеют один вход и один выход.
Для удобства изображения алгоритмов при составлении блок-схем используются следующие графические знаки (блоки).
Мы будем писать для краткости
|
начало (конец) алгоритма
|
|
ввод – вывод данных
|
|
Соединитель
|
|
проверка условия
|
|
выполнение операций или группы операций (обработка данных) |
|
указывают направление
|
Структурное изображение блок-схемы помогают “видеть” алгоритм.
Вопрос: какой алгоритм изображен на этих двух блок-схемах?
Ответ: на первый взгляд трудно понять, что на этих двух блок-схемах изображен один и тот же алгоритм. Из схемы а) четко видна его структура: цикл - пока с вложенным ветвлением. В схеме б) довольно сложно усмотреть эту же структуру.
Пример. Запишем блок-схему алгоритма Евклида.
При большой насыщенности блок-схемы блоками допускается прерывать стрелки, а затем продолжать их в нужном месте (то есть, как бы удаляешь часть стрелки, пересекающую блок-схему). В этом случае начало и конец удаленных участков обозначаются соединителями, внутри которых записываются (для каждой стрелки) одни и те же обозначения: буква, буква и цифра или цифра.