6.2. Основные типы алгоритмов

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

6.2.1. Линейные алгоритмы

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

Задача 1.

Дан треугольник со сторонами a,b,c. Найти площадь треугольника по формуле Герона, гдеp– полупериметр треугольника. Составить блок-схему.

Решение:

Нача

6.2.2. Алгоритмы разветвляющейся структуры

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

Задача 2.

Составить алгоритм вычисления функции

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

да

нет

да

нет

6.2.3. Алгоритмы циклической структуры

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

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

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

Задача 3.

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

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

да

нет

Итерационные циклы

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

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

,

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

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

Вычисление суммы членов бесконечного ряда возможно лишь в том случае, если получаемая в результате циклического процесса последовательность s(1),s(2), …,s(i), … сходится к своему предельному значениюS, т.е. существует предел. Здесьs(i) – суммаiчленов бесконечного ряда.

Процесс вычисления суммы членов равномерно сходящегося ряда организуется в виде циклического алгоритма, когда при каждом прохождении цикла номер слагаемого iувеличивается на единицу, а сумма изменяется на величинуi-го слагаемого, т.е., гдеи- суммыiиi-1 слагаемых. Приведенное выше соотношение в алгоритме вычисления записывается следующим образом:S=S+f(i), что означает добавление слагаемого с номеромiк значению суммы, вычисленному на предыдущем шаге алгоритма, и присвоение вычисленного значения S+f(i) той же переменнойS. Начальное значениеSдолжно быть равно нулю, в этом случае после первого выполнения цикла значениеSбудет равно значению первого слагаемого. Суммирование считается законченным при выполнении условия, т.е. если значение очередного вычисленного члена ряда меньше величины погрешности.

Задача 4.