Линейные и разветвляющиеся структуры

Базовый набор структур

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

• последовательной (линейной) структуры (рис. 2, а);

• ветвящейся структуры (рис. 2, б).

• циклической структуры (рис. 2, в).

Рис. 2. Базовый набор структур:

а — последовательная (линейная) структура;

б — ветвящаяся структура; в — циклическая структура

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

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

Предписание «Список данных» содержит сведения об именах и типах данных, обрабатываемых в этом алгоритме. Предписание «Ввод (исходные данные)» определяет, какие исходные данные и в каком порядке должны быть введены в ЭВМ. Предписание «Вывод (исходные данные)» позволяет проконтролировать правильность ввода информации. Предписания 5 и 6 позволяют получить требуемые результаты и выдать их пользователю. Рассматриваемый алгоритм относится к линейным алгоритмам.

Рис. 3. Типовой алгоритм вычислительного процесса

Линейным называется алгоритм (фрагмент алгоритма, см. рис. 8, а), в котором отдельные предписания выполняются в естественном порядке (в порядке записи) независимо от значений исходных данных и промежуточных результатов.

Линейной, например, является последовательность вычислений по какой-либо формуле с помощью карманного калькулятора. Более подробно следует рассмотреть запись математических формул в виде конструкции Х:=А; которая читается следующим образом: «Переменной X присвоить значение, равное А». В этой формуле X — переменная; А может быть любым, сколь угодно сложным математическим выражением. В процессе решения задачи на ЭВМ выражение А вычисляется, и его значение присваивается содержимому ячейки памяти, отведенной для хранения переменной X. При этом переменная X теряет свое значение и приобретает новое. Таким образом, символ «:=» употребляется при изображении алгоритмов в значении «присвоить». Как следствие этого, бессмысленное с точки зрения алгебры выражение Х:=Х+5; является широко распространенным в программировании и означает, что к текущему значению переменной X добавляется число 5, после чего X теряет свое старое значение и приобретает новое, которое на 5 больше предыдущего.

Линейные фрагменты используются на первых этапах детализации задачи. Однако только в редких случаях все предписания такого алгоритма являются элементарными. Так, например, предписание 5 на рис. 9 не является элементарным и требует дальнейшей детализации. Поэтому назначение блока 5 предусматривает сверху свободное место для записи координат блока, в котором будет раскрываться смысл детализируемого участка.

Часто для дальнейшей детализации алгоритма используются ветвящиеся структуры (рис. 4).

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

Если (условие) То операторы ветви 1; Иначе операторы ветви 2; Конец-Если;

Если (условие) То операторы ветви; Конец-Если;

Если (условие) То Иначе операторы ветви; Конец-Если;

Рис. 4. Ветвящаяся структура: а — стандартная схема; б, в — частные случаи ветвления

Каждая ветвь может быть любой степени сложности, а может вообще не содержать предписаний (как это показано на рис. 4, б, в), т.е. быть «вырожденной». Выбор той или иной ветви осуществляется в зависимости от результата проверки условия. В каждом конкретном случае алгоритм реализуется только по одной ветви, а выполнение остальных исключается. В схемах, приведенных на рис. 4, положительный исход проверки условия обозначен знаком «+» (да, true, истина, «1»), а отрицательный — знаком «–» (нет, false, ложь, «0»).

При составлении алгоритма в виде псевдокодов линии связи заменяются словами «Идти» или «Перейти» с указанием номера предписания (оператора), которое должно выполняться на следующем шаге алгоритма. Горизонтальная линия, объединяющая ветви «+» и «–», в псевдокодах имеет аналог «Конец-Если». После фразы «Конец-Если» можно указать номер псевдокода, в котором записано проверяемое условие.

Использование данной конструкции при записи алгоритма в псевдокодах позволяет легко определить место окончания разветвления (продолжения основного алгоритма).

Рис. 5. Выбор варианта: а — структура выбора варианта; б, в — условное обозначение

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

В такой структуре (см. рис. 5) сначала вычисляется значение выражения, стоящего в операторе присваивания. В зависимости от значения переменной i затем будет выбран либо 1-й, либо 2-й, либо 3-й, либо 4-й оператор. Число выбираемых операторов в такой структуре не ограничено.

Дата добавления: 2014-10-31