Виды алгоритмов

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

Линейные обычно состоят из блоков «ввод/вывод» и «процесс». Пример. Вычислить функцию F=x² при любом х. В данном примере буквы Х, F обозначают переменные. Более подробно это понятие рассматривается далее. Переменная обозначает величину, которая может изменяться в течение работы алгоритма.

Рис.3. Линейный алгоритм

Такой способ записи, как F=х·х называется присвоением. Сначала вычисляется результат х·х, который записывается в переменную с именем F.

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

Ветвящиеся алгоритмы в зависимости от выполнения или невыполнения в них некоторых условий осуществляют ту или иную последовательность вычислений. При разветвлении происходит однократный проход по одной из ветвей решения задачи. Классический пример ветвящегося алгоритма – это алгоритм решения квадратного уравнения ах²+вх+с=0 при любых а, в, с. В добавление к предыдущим блокам ветвящиеся алгоритмы содержат блок «решение» (условие). В этом примере A,B,C,D, x, x₁, x₂ – переменные.

Рис. 4. Алгоритм ветвления

Сначала проверяют возможность А=0, тогда уравнение ах²+вх+с=0 приводится к виду вх+с=0, откуда

. Затем вычисляют дискриминант D, если он отрицателен, уравнение корней не имеет, если положительный, будут два корня, если равен 0, оба корня будут одинаковы. Алгоритм представлен на рис.4.

Ветвления могут быть полные и неполные:

Циклические алгоритмы имеют часть вычислений, которые выполняются неоднократно (рис. 5). В общем виде циклы содержат три вида действий:

1) подготовительные к циклу;

2) действия, которые будут повторяться (их называют тело цикла);

3) условия выхода из цикла.


Рис. 5. Циклические алгоритмы

Циклические алгоритмы бывают нескольких видов:

- циклы со счетчиком применяются, когда заранее известно, сколько раз будет повторяться последовательность действий;

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

В циклических алгоритмах часто вычисляют последующий член последовательности через предыдущий. Например, для всех i от 1 до N, причем а₀ задается заранее. Говорят, что в этих случаях единая формула вычислений называется рекуррентной, т.е. выражает рекуррентное соотношение между последующим и предыдущим шагами вычислений.

Пример. Найти сумму N слагаемых, т.е. вычислить

. Решение: Ведем S=Ø, тогда S₁=S+a₁; S₂=S₁+a₂; · ·S_i=S_i_–1+a_i;···S_n=S_n_-1+a_n , значению суммы на i-м шаге присваивается значение суммы на предыдущем шаге плюс слагаемое очередного шага а_i: На рис. 6а пример цикла со счетчиком. Здесь заранее известно количество повторений N раз. Блоки 5–8 можно было бы оформить как изображено на рис.6б:

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

Рис. 6а

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