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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1.2. Общие вопросы организации разветвлений в алгоритмах

Рассмотрим вопрос организации выбора направления в СА подробнее.

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

На СА выбор реализуется двоичным деревом, полным либо неполным, в каждом узле (условном блоке) которого простейший выбор кодируется логическим 0, если условие не выполняется ( false ), и логической 1, если условие выполняется ( true ).

Если составить позиционный код на выходе из блока выбора по каждому направлению в соответствии с кодами на выходах условных блоков СА при последовательном прохождении через них сверху вниз, то получим двоичный код десятичного номера альтернативы, уменьшенного на 1. Проранжируем сверху вниз условные блоки (ранг СА выбора – это глубина узла дерева выбора, увеличенная на 1); тогда количество альтернатив m, предоставляемых полным двоичным деревом, определяется его рангом r, m=2^r.

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

Рассмотрим построение СА выбора для полного дерева выбора.

Пример 1.3. Пусть необходимо организовать выбор из четырёх альтернатив, используя полное дерево и таблицу альтернатив.

В этом случае достаточно двух условий В1 и B2, где В1 и В2 — булевы переменные, причём на втором ранге условия одинаковы; каждой паре из значений 0 ( false ) и 1 ( true ) этих условий можно сопоставить свою альтернативу Ni - см. табл. 1.1, колонка А. Этой таблице соответствует фрагмент СА, показанный на рис.1.5; здесь рядом с номерами альтернатив указаны их коды (двоичные представления).

В1	В2	А
		N1
		N2
		N3
		N4

Таблица 1.1

N1 (00) N2 (01) N3 (10) N4 (11)

Рис. 1.5. СА выбора из четырёх альтернатив

Рассмотрим построение СА выбора при неполном дереве выбора.

Пример 1.4. Пусть задана логическая функция выбора вида С=В1Å В2, где В1 и В2 - логические условия (В1, В2 - булевы переменные) и Å -операция логического сложения по mod2. Заполним таблицу истинности для функции С (табл. 1.2); здесь в колонке для С проставлены её логические значения F ( false ) и Т ( true ), определяющие выбор из двух путей (альтернатив), по которым разветвляется СА для заданной функции. Таким образом, табл. 1.2 представляет собой таблицу альтернатив. На рис. 1.6 приведён фрагмент схемы алгоритма, построенный в соответствии с табл. 1.2, причём все пути, имеющие одинаковое логическое значение, объединены.

В1

В2

		F
		Т
		Т
		F

Таблица 1.2

r=1

r=2

F(00 V 11) T(01 V 10)

Рис. 1.6. СА выбора с объединением путей

Аналогично заполняется таблица истинности (если она не задана) и по ней строится схема алгоритма выбора, если задан составной оператор как логическая функция n аргументов; на каждом ранге, начиная со второго, проводится объединение путей, выбор которых имеет одинаковые логические значения.

Рис: 1.7. Частный случай выбора: а - исходный фрагмент ВБ б - упрощение фрагмента

Если в построенной схеме имеется изображённый на рис. 1.7, а фрагмент, то булева переменная Bi в нём склеивается, т. е. BiVù Bi=1; это означает, что условный блок на участке a-b не нужен, и его можно заменить отрезком прямой (рис 1.7, 6).

Пример 1.5. Пусть выбор из трёх альтернатив N1, N2, N3 определяется тремя простыми условиями (булевыми переменными) В1, В2, ВЗ в соответствии с табл. 1.3. Требуется синтезировать СА для блока выбора.

Перестроим табл. 1.3, введя для каждой альтернативы свою колонку, в которой для выбранного набора ù В1ù В2ù ВЗ отмечается единицей тот факт, что альтернатива реализуется, а прочерком - что не реализуется (табл. 1.4).

В1	В2	В3	С
			N1
			N2
			N1
			N3
			N3
			N3
			N3
			N3

Таблица 1.3 Таблица 1.4

В1	В2	ВЗ	N1	N2	N3
				–	–
			–		–
				–	–
			–	–
			–	–
			–	–
			–	–
			–	–

На рис. 1.8, а приведена начальная схема алгоритма выбора, а на рис. 1.8, б показана минимизированная СА выбора; рядом с каждым альтернативным выходом в скобках записаны соответствующие им коды (значения двоичных наборов ù В1ù В2ù ВЗ; X - безразличное значение).

В данном примере упрощения фрагментов СА выбора могут быть получены чисто схемным путём. Действительно, участок а-b может быть заменен прямой (см. рис. 1.7), а участки c-d, с-е, с-в можно преобразовать с учётом законов дистрибутивности и коммутативности как для переменных, так и для соответствующих им условных блоков. Имеем

участок c-d - ù В2 & ù B3 V B2 & ù B3 = ù ВЗ & (ù B2 V B2) = ù B3;

участок с-е - ù В2 & В3 = ВЗ & ù В2;

участок с-в - В2& ВЗ = ВЗ& В2.

N1(000 V 010) N2(001) N3 (011 V 100 V 101 V 110 V 111)

Рассмотрим общие вопросы организации разветвлений в СА. Под термином " организация разветвлений" понимается такое построение схемы (блока) выбора альтернатив, которое адекватно отображает исходное задание, и при этом имеет минимальное булево выражение в смысле цены по Квайну. Исходная информация о сложном выборе в некоторой задаче должна быть представлена таблицей альтернатив (ТА).

В общем случае построения СА выбора заданы m альтернатив N1...Nm и n булевых переменных В1...Вn. Каждому набору ù B1...ù Вn соответствует своя альтернатива, что может быть представлено в виде ТА. Перестроим ТА таким образом, чтобы каждой альтернативе соответствовала своя колонка, в которой для выбранного набора ù B1...ù Вn отмечается " 1" - альтернатива реализуется, а прочерком - не реализуется. Тогда Ni (i=) можно считать выходными переменными схемы выбора, а саму таблицу можно рассматривать как таблицу истинности для системы m функций от n булевых переменных; минимизировав такую систему [5], можно построить СА выбора.

В ТА в столбце альтернатив могут быть одинаковые альтернативы (одна и та же альтернатива реализуется при нескольких наборах ù В1...ù Bn) или прочерки (не все альтернативы используются). В первом случае можно объединить конечные узлы дерева. Второй случай соответствует неполному дереву выбора (m< 2^r); ТА в этом случае может быть доопределена исходя из дополнительных соображений. В обоих случаях надо минимизировать логические выражения и реализующие их схемы алгоритмов.

Рис. 1.9. Фрагменты СА для условных операторов типа:

а, б – if; c – case..of

На рис. 1.9 приведены фрагменты СА для условных операторов вида

а) if < условие> then S (на схеме условие сокращённо обозначено I),

б) if < условие> then S1 else S2 (на схеме - I);

в) case N of 1: S1; 2: S2; .. k: Sk end (на схеме - С ).

Здесь Si - произвольный оператор; он может быть пустым либо составным, т. е. включать в себя последовательность операторов, в том числе условный оператор.

Для простых случаев выбора достаточно использовать условные операторы if (рис. 1.9, а и б). В более сложных случаях Pascal предоставляет мощное средство – оператор-переключатель case.. of (рис. 1.9, в); аналогичное средство ( switch ) имеется и в языке С.

В заключение запишем фрагмент программы для минимизированной СА выбора (пример 1.5) Переход от схемы выбора (рис. 1.8, б) к условному оператору case N of несложен; каждой альтернативе ставится в соответствие свой десятичный номер (слева направо в СА выбора), затем по кодам альтернатив записываются логические формулы, которые вписываются в качестве условий в условные операторы, и формируются операторы присваивания параметру N соответствующего десятичного номера; далее следует (возможно, после операторов общего вида) оператор case N of.

Таким образом, фрагмент программы для примера 1.5 имеет вид

Begin

if (NOT B1) AND (NOT B3) then N: =1 else

if (NOT B1) AND (NOT B2) AND B3 then N: =2 else N: =3;

case N of

1: S1;

2: S2;

3: S3;

end;

End.

Важно отметить, что к моменту вычисления N должны быть определены значения В1, В2, ВЗ.

В качестве еще одного примера использования ветвлений рассмотрим составление алгоритма для вычисления функции f в зависимости от конкретных значений х, а, b:

Первое приближение алгоритма будет иметь вид, показанный на рис. 12.

Рис. 12. Первый этап составления алгоритма

Анализ этого алгоритма показывает, что все его блоки, кроме блока 5, являются элементарными. Возможный вариант дальнейшей детализации блока 5 представлен на рис. 13. Все блоки второго этапа детализации являются элементарными, поэтому составление алгоритма практически закончено.

Рис. 13. Второй этап составления алгоритма

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

Предыдущая 1 2 345 6 7 8 Следующая