Управляющие структуры и основные конструкции алгоритмов

Независимо от формы описания, для алгоритмов важно различать следующие аспекты:

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

- специфичный способ, каким решается задача, при этом для алгоритма различают:

o элементарные шаги обработки, которые имеются в распоряжении;

o описание отдельных подлежащих выполнению шагов.

Для алгоритмически разрешимой постановки задачи всегда имеется много различных способов её решения, т.е. различных алгоритмов.

В алгоритмах некоторые шаги выполняются всегда, некоторые лишь при определённом условии, а выполнение некоторых шагов производится неоднократно. В этих случаях говорят о безусловном выполнении шагов, условном выполнении и циклическом выполнении шагов. Таким образом, классические элементы, которые встречаются в описаниях алгоритмов, это:

- выполнение элементарных шагов;

- разветвления по условиям;

- циклы.

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

- состоянием некоторых ячеек памяти, понимаемых нами как переменные;

- активной точкой программы, то есть той командой программы, которая выполняется данный момент.

Следовательно, можно выделить и два основных класса действий, которые может выполнять вычислительная система:

- действия, выделяющие область памяти под переменные программы (описания).

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

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

В теории программирования доказано, что программу для решения задачи любой сложности можно составить их трех структур, называемых следованием (цепочкой), ветвлением и циклом. Любую программа можно преобразовать в эквивалентную, состоящую только из этих структур и их комбинаций Этот результат известен как теорема Бена-Якопини (1966). Каждая из этих управляющих структур реализована в языке программирования набором соответствующих конструкций.

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

{

оператор 1;

оператор 2;

….

оператор n;

}

На блок-схеме блоки, отображающие эти операции, располагаются в линейной последовательности.

Структура ветвления реализует ветвящийся вычислительный процесс, то есть процесс, для реализации которого предусмотрено несколько направлений (ветвей). Ветвление в программе – это выбор одной из нескольких последовательностей операторов при выполнении программы. Выбор направления зависит от заранее определенного признака, который может относиться к исходным данным, к промежуточным данным или конечным результатам. Хотя на схеме алгоритма должны быть показаны все возможные направления вычислений в зависимости от выполнения определенного условия (или условий), при однократном прохождении программы процесс реализуется только по одной ветви, а остальные исключаются. Любая ветвь, по которой осуществляется вычисления, должна приводить к завершению вычислительного процесса.

В языках программирования структура ветвления реализуется условными и селективными конструкциями. Условные конструкции в общем случае имеют форму

если выражение то действие1 иначе действие2;

и следующей смысл: если выражение верно то выполняется действие1, иначе выполняется действие2.

Кроме того, используется и усеченная форма условной структуры

если выражение то действие1;

На блок-схеме ветвление и усеченное ветвление изображаются следующим образом:

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

- подготовка (инициализация параметров цикла);

- выполнение вычислений цикла (тело цикла);

- модификация параметров (которая фактически является частью тела цикла);

- проверка условия окончания (или условия продолжения) цикла.

Порядок выполнения этих этапов может и меняться. Если условие проверяется до выполнения тела циклf, то говорят о цикле с предусловием. Если – после, то о цикле с постусловием. Главное отличие- цикл с постусловием обязательно выполнится хотя бы один раз.

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

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

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: