Примеры алгоритмов, линейных и с разветвлением

Разветвления в алгоритмах

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

Линейным называется алгоритм, в схеме которого блоки (вершины) связаны в одну линию.

Пример 1.1. Составить СА для вычисления следующей функции:

y = sin(a)cos(b) + e ^-x cos(a) (1.1)

при заданных значениях a, b, x.

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

1) А₁ = sin(a); 2) A₂ = cos(b); 3) A₃ = exp(- х); 4) A₄ = cos(a);

5) B₁ = A₁ A₂; 6) B₂ = A₃ A₄; 7) у = B₁ + B₂.

СА, представляющая данный вычислительный процесс с учётом ввода исходных данных и вывода вычисленного значения y, является линейной (рис. 1.1; начальный и конечный блоки не нумеруются). Её особенность – то, что операторные блоки 2-5 можно располагать в произвольном порядке; то же относится и к блокам 6 и 7.

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

Рис. 1.1. Пример линейной СА (последовательная реализация)

Для вычисления функций SIN, COS и EXP используются стандартные подпрограммы (СП), основанные, как правило, на представлении этих функций в виде полиномов (например, разложение в ряд Тейлора [4]). Однако эти СП реализуют нелинейные СА, содержащие циклы – см. п. 1.2.

Рис. 1.2. Параллельная реализация СА для примера 1.1

Таким образом, линейность СА - понятие относительное; при более подробном рассмотрении СА может оказаться нелинейной. В сколько-нибудь сложной СА линейными могут быть только её отдельные фрагменты.

Рассмотрим далее схемы алгоритмов с разветвлением.

Разветвлением будем называть фрагмент СА, содержащий блок выбора альтернативного направления с одним входом и с двумя или более выходами; по этим выходам организуются связи с другими фрагментами СА. Выбор альтернатив осуществляется по определённому условию, возможно, сложному, реализуемому совокупностью условных операторов.

Пример 1.2. Составить СА нахождения корней квадратного уравнения

au² + bu + c = 0. (1.2)

Предварительно запишем приведённое квадратное уравнение с целью уменьшения числа параметров, определяющих решения исходного уравнения:

u² + pu + q = 0; (1.3)

здесь

p = b / a, q = c / a (a ¹ 0!). (1.4)

Корни приведённого квадратного уравнения определяются по формуле

u_1,2 = - p /2 ± Ö d, (1.5)

где

d = p ²/4 – q. (1.6)

В зависимости от значений d возможны 3 случая:

· d>0. Решение содержит два вещественных корня

u₁ = - p /2 + Ö d, u₂ = - p /2 - Ö d; (1.7)

· d<0. Решение содержит два мнимых корня (u = x + iy, i = Ö-1)

u₁ = - p /2 + i Öï d ï, u₂ = - p /2 - i Öï d ï; (1.8)

· d=0. Решение содержит два слившихся вещественных корня

u₁ = u₂ = - p /2. (1.9)

Проанализируем поведение корней при изменении величины и знака дискриминанта d (рис.1.3):

1 ) d< 0 - корни перемещаются симмет-рично по вертикали (мнимая ось);

2) d >0 - корни перемещаются симметрично по горизонтали (реальная ось);

3) d =0 - граничная точка x = - p /2 при переходе с вертикали на горизонталь.

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

Составляем СА (рис. 1.4), исходя из такой последовательности шагов: вводим исходные данные и вычисляем параметры приведённого квадратного уравнения; вычисляем значения корней в соответствии с тремя возможными альтернативами, определяемыми условными блоками; выводим результаты на экран (принтер).

На рис. 1.4,а пунктиром выделен блок выбора трёх альтернативных направлений в зависимости от значения дискриминанта d; он легко преоб-разуется в эквивалентный ему блок выбора (рис. 1.4,б). Анализ этого блока показывает, что проверку условия d =0 можно исключить из алгоритма, так как в случае d =0 равные значения корней получаются автоматически.

Дата добавления: 2014-01-14