Способы описания алгоритмов

Для разработки алгоритмов и программ используется алгоритмизация — процесс систематического составления алгоритмов для решения поставленных прикладных задач.

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

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

Для схематического (графического) описания алгоритма применяются блок-схемы. Другим вариантом описания алгоритма, не зависящим от языка программирования, является псевдокод.

Пример 12.1.

Опишем алгоритм вычисления факториала некоторого натурального числа N. Факториал обозначается символом АП и легко выражается посредством соотношения АЛ = 1 • 2 • 3 ••• N.

Словесное описание вычисления факториала не выглядит сложным: нужно просто перемножить друг на друга все натуральные числа от 1 до N. Человеку это описание понятно.

Заметим, однако, что если попытаться возложить решение этой задачи на компьютер, то придется ему объяснить, что означает «троеточие» и как свести решение задачи к последовательности простейших арифметических операций, операций присваивания значений переменной и сравнения чисел.

Проблема состоит в том, что мы не разбили решение задачи на шаги. Будем вычислять значение факториала постепенно.

Введем переменную F и вначале присвоим ей значение 1. Затем на каждом шаге будем умножать F на следующее по порядку (на единицу большее) натуральное число.

Для хранения значения натурального числа, на которое нужно умножать на текущем шаге, нам понадобится еще одна переменная. Назовем ее к. Результат умножения F на к снова поместим в F. Процесс вычисления остановится, когда будет выполнено умножение на F на N (т.е. при к = N). В результате в F будет храниться искомое значение N1.

Словесное описание алгоритма:

• 1) задать число AI)
• 2) положить переменную F равной единице и переменную к равной единице;

• 3) умножить F на к, результат умножения поместить в F;
• 4) сравнить числа к и ЛГ; если числа не равны, то перейти к следующему шагу алгоритма; если числа равны, то взять F в качестве ответа и остановиться;
• 5) увеличить число к на единицу и перейти к пункту 3). ?

Словесный способ описания алгоритма слишком многословен и неформален и подходит в основном для формулировки идеи алгоритма.

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

Псевдокод обычно опускает детали, несущественные для понимания алгоритма человеком. Главная цель использования псевдокода — сделать описание более понятным, чем код на языке программирования.

Псевдокод широко используется в учебниках и научно-технических публикациях, а также на начальных стадиях разработки компьютерных программ. В отличие от стандартизованного синтаксиса языков программирования на синтаксис псевдокода обычно не устанавливается стандартов.

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

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

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

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

Пример 12.2.

Запишем алгоритм нахождения факториала натурального числа N на псевдокоде, в котором, кроме обычных математических символов и служебных слов, записанных прописными буквами русского языка, присутствует символ оператора присваивания.

Мы использовали принятый во многих языках программирования символ «:=». Он означает, что объекту (в нашем случае, переменной), находящемуся слева от символа «:=», будет дано («присвоено») значение объекта (выражения), стоящего справа от него.

Алгоритм:

• 1) ВВОД N;
• 2) F - 1, к:= 1;
• 3) F:=F k;
• 4) ЕСЛИ k*N, ПЕРЕЙТИ к пункту 5), ИНАЧЕ ПЕРЕЙТИ к пункту 6);
• 5) к:= к + 1 и ПЕРЕЙТИ к пункту 3);
• 6) ПЕЧАТЬ F;
• 7) КОНЕЦ. ?

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

Для реализации повторяющегося умножения в нашем алгоритме можно ввести процедуру, которая называется «цикл со счетчиком» или «арифметический цикл».

Переменная к из примера 12.2 будет счетчиком этого цикла. Задается начальное значение счетчика (в нашем примере это 1). После каждого выполнения цикла значение параметра увеличивается на одну и ту же величину, называемую шагом цикла (в нашем примере шаг тоже равен 1).

Арифметический цикл выполняется до тех пор, пока величина параметра цикла не превышает заданного конечного значения (в нашем случае это заданное число N).

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

Пример 12.3.

Запишем алгоритм нахождения факториала натурального числа N на псевдокоде с использованием арифметического цикла.

Алгоритм:

• 1) ВВОДА/;
• 2) F:= 1, k:= 1;
• 3) ЦИКЛ по fc от 1 до N F:=Fk

КОНЕЦ ЦИКЛА;

• 4) ПЕЧАТЬ F;
• 5) КОНЕЦ. ?

Арифметические циклы широко используются при работе с массивами.

Кроме арифметических циклов существуют еще циклы «по условию». В таком цикле приписанная ему последовательность действий будет повторяться до тех пор, пока истинно некоторое утверждение (проверяемое при каждой попытке повторения цикла).

Количество повторений арифметического цикла определено заранее. Сколько раз проработает цикл «по условию», заранее неизвестно. Как только значение проверяемого утверждения станет ложным, цикл завершится.

Блок-схема описывает алгоритмы, изображая шаги алгоритма в виде блоков различной формы, соединенных между собой стрелками. Существуют документы (ГОСТы), регулирующие способы построения блоксхем и внешний вид их элементов (табл. 12.1).

Таблица 12.1

Основные элементы (блоки) блок-схемы.

Наименование.	Обозначение.	Функция.
Пуск-останов.		Элемент отображает вход из внешней среды или выход в нее (наиболее частое применение — начало и конец программы). Внутри фигуры записывается соответствующее действие.
Процесс.		Выполнение одной или нескольких операций, обработка данных любого вида (изменение значения данных, формы их представления, расположения). Внутри фигуры записывают непосредственно сами операции, например операцию присваивания
Решение.		Отображает функцию-«переключатель» с одним входом и двумя или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент обозначается линией, входящей обычно в верхнюю вершину ромба. Если выходов два или три, то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых и нижней). Если выходов больше трех, то их следует показывать одной линией, выходящей из вершины (чаще нижней) элемента, которая затем разветвляется. Соответствующие результаты вычислений могут записываться рядом с линиями, отображающими эти пути. Примеры: в общем случае — сравнение значений чисел или переменных; в программировании — условные операторы.

Окончание табл. 12.1

Наименование.	Обозначение.	Функция.
Предопределенный процесс.		Символ отображает выполнение процесса, который определен в другом месте программы (в подпрогральче, модуле). Внутри символа записываются название процесса и передаваемые в него данные. Например, в программировании — вызов процедуры или функции.
Данные. (ввод-вывод).		Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод). Данный символ не определяет носителя данных (для указания типа носителя данных используются специфические символы).
Граница цикла.		Символ состоит из двух частей — соответственно, начало и конец цикла — операции, выполняемые внутри цикла, размещаются между ними. Условия выполнения цикла записываются внутри символа его начала или конца, в зависимости от типа организации цикла. Часто для изображения цикла на блок-схеме вместо данного символа используют блок решения, указывая в нем условие, а одну из линий выхода замыкают выше в блок-схеме (перед действиями, соответствующими циклу).
Соединитель.		Символ отображает выход в часть схемы и вход из другой части этой схемы. Используется для обрыва линии и продолжения ее в другом месте (например, для разделение блок-схемы, не помещающейся на листе). Соответствующие соединительные символы должны иметь одно (при этом уникальное) обозначение.
Комментарий.		Используется для более подробного описания шага, процесса или группы процессов. Описание помещается со стороны квадратной скобки и охватывается ею по всей высоте. Пунктирная линия идет к описываемому элементу либо группе элементов (при этом группа выделяется замкнутой пунктирной линией). Также символ комментария следует использовать в тех случаях, когда объем текста в какомлибо другом символе (например, символ процесса, символ данных и др.) превышает его объем.

Рассмотренный в примере 12.3 алгоритм нахождения факториала числа N можно представить в виде следующей блок-схемы:

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