Лекция 12. базовые алгоритмические структуры
1. Линейная базовая структура
2. Разветвленная базовая структура
3. Циклическая базовая структура
ЛИТЕРАТУРА:
[1], стр. 187 – 212.
В общем случае блок-схема алгоритма имеет сложную структуру и, следовательно, может быть выражена композицией элементарных блок-схем, которые принято называть базовыми.
Логическая структура любого алгоритма может быть представлена комбинацией трех базовых алгоритмических структур:
· алгоритмов линейной структуры, которые иногда называют следованием (последовательностью),
· алгоритмов разветвляющейся структуры, называемых ветвлением,
· алгоритмов циклической структуры, называемых циклами.
Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.
ЛИНЕЙНАЯ БАЗОВАЯ СТРУКТУРА
Алгоритм линейной структура (serial algorithm) — это алгоритм, в котором все действия выполняются последовательно друг за другом, в порядке, заданном схемой. Такой порядок выполнения называется естественным.
Данный алгоритм не содержит ветвей и циклов, блок-схема представима в виде одного или нескольких следующих друг за другом символов «Процесс».
Рис. 12.1. Алгоритм линейной структуры
Пример. Вычислить высоты треугольника со сторонами а, b, с, используя формулы:
где .
Решение: При решении данной задачи для исключения повторений следует вычислять высоты не по приведенным выше формулам непосредственно, а используя промежуточную переменную
,
тогда ha=t/a, hb=t/b, hc=t/c.
При этом схема алгоритма решения имеет вид, представленный на рис. 12. 2.
Рис.12.2.
2. РАЗВЕТВЛЕННАЯ БАЗОВАЯ СТРУКТУРА
На практике редко удается представить решение задачи в виде алгоритма линейной структуры. Часто в зависимости от каких-либо промежуточных результатов вычисления осуществляются либо по одним, либо по другим формулам, т.е. в зависимости от выполнения некоторого логического условия вычислительный процесс осуществляется по одной или другой ветви. Алгоритм такого вычислительного процесса называется алгоритмом разветвляющейся структуры.
Алгоритм разветвляющейся структуры – алгоритм, который в зависимости от результата проверки условия (ИСТИННО или ЛОЖНО) обеспечивает выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.
Ветвление алгоритма – предусмотренная в алгоритме возможность выполнения тех или иных действий в зависимости от результатов проверки некоторого условия. На блок-схеме изображается при помощи символа «Решение».
Ветвь алгоритма – одна из альтернативных последовательностей действий алгоритма, выбор которой зависит от некоторых условий. На блок-схеме – один из альтернативных путей, исходящих из точки ветвления.
Различают линейную и блоковую формы алгоритмов разветвляющейся структуры, блок-схемы которых представлены на рис. 12.3 и 12.5.
Рис.12.3. Алгоритм разветвленной структуры (линейная форма)
Пример. Вычислить значение функции
ax+bx2-c, если x<0,
F(x)=
(a+bx)/(x-1), если x≥0,
где a=1.8; b=-0.5; c=3.5.
Схема алгоритма решения имеет вид, представленный на
рис. 12. 4.
Рис. 12.4.
Рис.12.5. Алгоритм разветвленной структуры (блоковая форма)
Пример. Вычислить значение функции
ax+2bx-c, если x<=0,
(a+bx)/(x-1), если 0<x<=2,
F(x)=
(x+1)/2, 2<x<10,
4ax-3b+c, x>=10,
где a=1.8; b=-0.5; c=3.5.
Схема алгоритма решения имеет вид, представленный на
рис. 12. 6.
Рис. 12.6.