Словесная запись алгоритма

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

Пример словесной формы записи алгоритма классический алгоритм Евклида для нахождения наибольшего общего делителя двух натуральных чисел:

1. Если числа равны, то взять первое число в качестве ответа и закончить исполнение алгоритма, иначе перейти к п. 2.

2. Определить большее из двух чисел.

3. Заменить большее число на разность большего и меньшего чисел.

4. Перейти к п. 1.

Команды такого алгоритма выполняются в естественной последовательности. Так, после второй команды будет выполняться третья, после третьей – четвертая, а вот после четвертой команды необходимо вернуться снова к выполнению первой команды, так как это явно оговорено в четвертой команде. Команды такого типа (команды перехода) нарушают естественный порядок выполнения команд алгоритма.

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

Псевдокоды

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

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

В качестве примера приведем запись на одном из псевдокодов алгоритма:

алгоритм алгоритм Евклида;

начало

пока первое число не равно второму

повторять

начало

если числа равны

то стоп все;

иначе определить большее из двух чсел;

заменить большее число на разность большего и меньшего чсел

конец;

взять первое число в качестве ответа

конец

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

Структурные схемы алгоритмов

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

• действия ввода – вывода данных помещают в блоках, имеющих вид параллелограмма,

• действия обработки информации помещают в блоках, имеющих вид прямоугольников,

• команды проверки условий — в блоках, имеющих вид ромбов,

• начало и конец алгоритма обозначают овалом.

Структуры алгоритмов

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

Структура, состоящая из последовательности шагов (действий) называется линейной (см. рисунок 7.1). Каждый функциональный блок этой структуры имеет один вход и один выход.

Рис. 7.1. Линейная структура алгоритма

Структура, обеспечивающая выбор между двумя альтернативами в зависимости от исходных данных, называется разветвляющейся или условной. Различают полное (см. рисунок 7.2) и неполное (см. рисунок 7.3) ветвления. В этой структуре присутствует блок условия, который имеет один вход и два выхода (истина и ложь). После проверки условия на каждой ветви располагается линейная структура.

Рис. 7.2. Полная форма ветвления Рис. 7.3. Неполная форма ветвления

Структура, обеспечивающая повторение линейных и условных структур в зависимости от входных данных и условия задачи, называется циклической (или циклом). Различают циклы с предусловием (проверка условия стоит перед началом действий рисунок 7.4) и циклы с постусловием (проверка условия стоит после выполнения действий рисунок 7.5).

Рис. 7.4. Цикл с предусловием Рис. 7.5. Цикл с постусловием

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

Рис. 7.6. Пример структурной схемы алгоритма Евклида

Для записи внутри блоков действий используется естественный язык с элементами математической символики. В результате проверки условия возникают два возможных пути для продолжения алгоритма. Эти пути изображаются стрелками со знаками «+» и «-» (иногда пишут также «Да» и «Нет»).

Переход по стрелке со знаком «+» происходит, если условие истинно, а переход по стрелке «-», если условие ложно.

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

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

Задания:

Используя рассмотренные ранее структуры, создать следующие алгоритмы:

• Нахождение суммы последовательности чисел.

• Нахождение произведения последовательности чисел.

• Нахождение среднего значения последовательности чисел.

• Нахождение факториалов: n!, 2n!!, (2n+1)!! (раздельные алгоритмы и один – общий)

• Нахождение суммы всех положительных (отрицательных) чисел

• Нахождение максимального (минимального) значения последовательности чисел.

• Нахождение корней квадратного уравнения.