Основные алгоритмические конструкции

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

Линейная алгоритмическая конструкция

Линейной называют алгоритмичес­кую конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма выполняется ровно один раз, причем после каждого i-го действия (шага) выполняется (i +1)-е действие (шаг), если i -е дей­ствие - не конец алгоритма.

Пример: опишем алгоритм сложения двух чисел на псевдокоде в виде блок-схе­мы.

Псевдокод:

1. Ввод двух чисел а, b.

2. Вычисляем сумму S = а + b.

3. Вывод S.

4. Конец.

Рисунок – блок-схема к примеру

Разветвляющаяся алгоритмическая конструкция

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

Рисунок – Полное ветвление

Неполное ветв­ление предполагает наличие некоторых действий алгоритма только на одной ветви (то), вторая ветвь отсутствует, т.е. для одного из ре­зультатов проверки никаких действий выполнять не надо, управле­ние сразу переходит к точке слияния (рис).

Рисунок – неполное ветвление

Пример: вывести значение наибольшего из двух чисел.

Псевдокод:

1. Ввод двух чисел а, b.

2. ЕСЛИ а > b, ТО «выводим а»,

ИНАЧЕ «выводим b»,

3. Конец.

Рисунок – Блок-схема к примеру

В данном примере реализовано полное ветвление. ЕСЛИ значе­ния входных данных таковы, что а >b, ТО выполняется линейный алгоритм:

1. Ввод двух чисел а, b.

2. Вывод a,

ИНАЧЕ, когда а<b, выполняется линейный алгоритм:

1. Ввод двух чисел а, b.

2. Вывод b.

Вывод: алгоритм является разветвляющимся и состоит из двух ветвей.

Алгоритмическая конструкция «Цикл»

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

Рассмотрим три типа циклических алгоритмов: цикл с параметром (который называют арифметическим циклом), цикл с предусловием и цикл с постусловием (их на­зывают итерационными).

Арифметический цикл

В арифметическом цикле число его шагов (повторений) одно­значно определяется правилом изменения параметра, которое зада­ется с помощью начального (N) и конечного (К) значении параметра и шагом (h) его изменения. Т.е., на первом шаге цикла значение па­раметра равно N, на втором N+h, на третьем – N+2h и т.д. На последнем шаге цикла значение параметра не больше К, но та­кое, что дальнейшее его изменение приведет к значению, большему, чем К.

Пример: Вывести 10 раз слово «Привет!».

Параметр цикла обозначим i, он будет отвечать за количество выведенных слов. При i = 1 будет выведено первое слово, при i = 2 будет выведено второе слова и т.д. Так как требуется вывести 10 слов, то последнее значение параметра i = 10. В заданном примере требу­ется 10 раз повторить одно и то же действие: вывести слово «Привет!».

Составим алгоритм, ис­пользуя арифметический цикл, в котором правило изменения параметра i – 1, 10, 1. То есть начальное значение параметра i = 1; конечное значение i =10; шаг изменения h = 1. На рисунке представлена блок-схема алгоритма решения данной за­дачи.

Рисунок – Блок-схема к примеру

Цикл с предусловием

Количество шагов цикла заранее не определено и зависит от входных данных задачи. В данной циклической структуре сначала проверяется значение условного выражения (условие) перед выпол­нением очередного шага цикла. Если значение условного выражения истинно, исполняется тело цикла. После чего управление вновь пе­редается проверке условия и т.д. Эти действия повторяются до тех пор, пока условное выражение не примет значение ЛОЖЬ. При пер­вом же несоблюдении условия цикл завершается.

а б

Рисунок – Блок-схема цикла с предусловием

Блок-схема данной конструкции представлена на рисунке двумя способами; с помощью условного блока а и с помощью блока гра­ницы цикла б.

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

Цикл с постусловием

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

блока а и с помощью блока управления б.

а б

Рисунок – Блок-схема цикла с постусловием

Рекурсивный алгоритм

Рекурсивным называется алгоритм, организованный таким обра­зом, что в процессе выполнения команд на каком-либо шаге он пря­мо или косвенно обращается сам к себе.