С. Л. Гольдштейн А. В. Кибардин информатика для физиков часть Введение Учебное пособие

Основные типы вычислительных процессов

Общая совокупность вычислительных процессов делится на три типа:

• 
  линейные;
  
• 
  ветвящиеся;
  
• 
  циклические.
  

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



а) б) в)

Рис. 2.2

Вычислительный процесс называется ветвящимся, если в зависимости от исходных условий ил промежуточных результатов он реализуется по одному из нескольких заранее предусмотренных (возможных) направлений. Каждое отдельное направление называется ветвью вычислений. Выбор той или иной ветви вычислений осуществляется проверкой выполнения заданного условия, определяющего свойства исходных данных или промежуточных результатов. Схемы алгоритмов ветвящихся процессов задаются с помощью управляющей канонической структуры выбора (рис.2.2 б – полная, в – неполная). В случае, например. Использования полной схемы управляющей структуры выбора, последовательность операторов S1 выполняется, если соблюдается заданное условие P (иначе говоря, значение логического выражения P истинно). При ложности P выполняется другая последовательность операторов S2. После этого управление передается на выход к внешнему оператору S3.
Для составления алгоритма ветвлений по трем или более направлениям используются управляющие структуры выбора с двухуровневой вложенностью и более.
Кроме рассмотренных управляющих канонических структур выбора решения имеется еще одна дополнительная структура переключателя, которая позволяет выбирать одну ветвь из многих в зависимости от значения заданного выражения (рис.2.3). Особенность этой структуры в том, что выбор решения здесь осуществляется не в зависимости от истинности или ложности условия, а является вычисляемым.

Рис.2.3

При построении алгоритмов решения многих задач часто используется многократное повторение отдельных этапов их вычислительного процесса. Многократно повторяемые участки вычислений при соблюдении заданных условий называются циклами, а вычислительные процессы, содержащие такие многократно повторяемые участки вычислений – циклическими.
Для представления циклов в схемах алгоритмов используются канонические структуры повторения (рис.2.4 а и б).
Из схемы видно, что при соблюдении условия в блоке логики Р выполняется тело цикла и управление передается на проверку окончания цикла. Если цикл не окончен, т.е. условие Р выполняется, то повторно выполняется тело цикла S.



а) б)
Рис. 2.4
Такие повторения продолжаются до тех пор, пока заданное условие не перестает выполняться. Отличие схемы б от а в том, что каноническая структура б предполагает выполнение цикла хотя бы один раз, так как оно помещено до проверки условия работы в цикле. Структура а) называется циклической структурой с предпроверкой, структура б) циклической структурой с постпроверкой.
В зависимости от ограничения числа повторений цикла различаются два основных типа: циклы с известным (фиксированным) количеством повторений и итерационные циклы. Итерационным называется процесс, в котором для вычисления последующего значения переменной используется ее предыдущее значение по определенной реккурентной формуле до достижения заданной точности.
Исходя из структуры циклы разбиваются на простые и сложные (вложенные). Простыми называются такие циклы, которые не содержат других циклов. Сложные циклы – это циклы, содержащие один или несколько других циклов. Циклы, охватывающие другие циклы, называются внешними, циклы, входящие в другие – вложенными или внутренними.

2.