Базовые структуры алгоритмов

 Базовые структуры алгоритмов

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

·      последовательного алгоритма – алгоритма линейной структуры;

·      ветвящегося алгоритма – алгоритма разветвляющейся структуры;

·      циклического алгоритма – алгоритма циклической структуры.

Алгоритм линейной структуры – это объединение всех действий в единую цепь, в которой каждое последующее действие строго и одно- значно следует за предыдущим действием (рис.7). На языке псевдокода соответствующая последовательность команд запишется в виде:

команда 1; команда 2; . . . ; команда N

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

Ветвление «если-то-иначе» (рис. 8) встречается на практике наибо- лее часто. В нем присутствует проверка одного условия, по результатам которой происходит выбор между двумя возможными цепочками даль- нейших действий.

. . .

. . .

Рис. 7. Алгоритм линейной структуры

. . .

. . .                                                   . . .

Рис. 8. Алгоритм разветвляющейся структуры (вариант «если-то-иначе»)

На языке псевдокода соответствующая последовательность ко- манд запишется в виде:

если Условие

то команда 1; . . . ; команда M

иначе команда 2; . . . ; команда N

все

Ветвление «если-то» (рис. 9) позволяет при соблюдении проверяе- мого в нем условия выполнить заданную цепочку действий: команды

1…N. При несоблюдении указанного условия команды 1…N пропускаются и сразу начинает выполняться следующая за ветвлением команда N+1.

На языке псевдокода вариант «если-то» запишется в виде:

если Условие

то команда 1; . . . ; команда N

все;

команда N+1;

. . .

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

(вариант «если-то»)

Рис. 10. Алгоритм разветвляющейся структуры (вариант «выбор»)

Ветвление «выбор» (рис. 10) позволяет выбрать одну из N имею- щихся альтернатив – цепочек команд. Для каждой альтернативы снача- ла проверяется соответствующее ей условие, срабатывает та первая альтернатива, у которой оно выполнится. Если не выполнится ни одно из условий выбора – ни одна из N цепочек команд не сработает, а управление перейдет к следующей после ветвления команде.

На языке псевдокода вариант «выбор» запишется в виде:

выбор

при условие 1: команды 1

при условие 2: команды 2

. . . . . . . . . . . .

при условие N: команды N

все

Ветвление «выбор-иначе» (рис. 11) предусматривает проверку ус- ловий только у первых N-1 альтернатив, а у последней N-й цепочки ко- манд условие отсутствует. Если не сработает ни одна из первых N-1 альтернатив, то тогда автоматически выполнится N-я цепочка команд. Таким образом, в отличие от ветвления «выбор», здесь обязательно произойдет срабатывание одной из имеющихся N цепочек команд.

. . .

. . .

Рис. 11. Алгоритм разветвляющейся структуры (вариант «выбор-иначе»)

На языке псевдокода вариант «выбор-иначе» запишется в виде:

выбор

при условие 1: команды 1

при условие 2: команды 2

. . . . . . . . . . . .

при условие N-1: команды N-1

иначе команды N

все

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

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

На рис. 12 представлены цикл с предусловием (а) и цикл с посту- словием (б). Повторяющееся тело цикла составляют команды 1…N, ко- манда N+1 в цикл не входит. В цикле с предусловием тело цикла не вы- полнится ни разу, если первая проверка условия цикла покажет его не- соблюдение. В цикле с постусловием тело цикла обязательно выпол- нится хотя бы один раз.

. . .                                                                                                   . . .

(а)                                                          (б)

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

На языке псевдокода циклы с предусловием или с постусловием отображаются соответственно следующими вариантами команды пока:

(а)

нц пока Условие

команда 1; команда 2; . . . ; команда N

кц;

команда N+1;

(б)

нц команда 1; команда 2; . . . ; команда N

пока Условие

кц;

команда N+1;

. . .

. . .

Рис. 13. Цикл с параметром

В тех случаях, когда число повторов выполнения тела цикла зара- нее известно, для отображении цикла удобно использовать блок моди- фикатор (табл. 4), в котором размещается заголовок цикла (рис. 13).

На языке псевдокода цикл с параметром отображается с помощью команды для:

нц

для К от k1 до k2 шаг k3

команда 1; команда 2; . . . ; команда N

кц;

команда N+1

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