10.5. Универсальные схемы алгоритмов

Все операции, выполняемые в алгоритмах, разделяют на две группы: арифметические операции и логические операции. Арифметические операции выполняют непосредственное преобразование информации. Логические операции определяют последовательность выполнения арифметических операций.

Рассмотрим основные универсальные схемы алгоритмов. К ним относят:

• Алгоритмы Ван - Хао.

• Алгоритмы Маркова.

• Алгоритмы Ляпунова.

• Графические схемы алгоритмов (ГСА).

• Структурные схемы алгоритмов (ССА).

• Словесные схемы алгоритмов (СА).

Универсальные схемы алгоритмов Ван - Хао появились в 50-х годах прошлого столетия. Операторный алгоритм Ван-Хао задается последовательностью приказов специального вида. Каждый приказ имеет определенный номер и указание, какую операцию необходимо выполнить над заданным объектом и с каким номером следует далее выполнять действие над результатом этой операции. Например, некоторый приказ записывается следующим образом (рис. 10.3):

i:







Рис. 10.3. Пример приказа

На рис. 10.3 i — номер приказа,  — элементарная операция над заданным объектом,  и  — номера произвольных других приказов. Выполнить приказ i над объектом или числом x означает вычислить (x) и затем перейти к выполнению над (x) приказа с номером , если (x) не определяется, то перейти к выполнению над числом x приказа с номером . Заключительному состоянию в алгоритме Ван - Хао соответствует приказ, представленный на рис. 10.4:

i:

стоп

Рис. 10.4. Приказ на окончание работы алгоритма Ван-Хао

Такая запись означает, что вычисления следует прекратить.

В настоящее время схемы алгоритмов Ван-Хао не имеют широкого практического применения, а используются для теоретического представления алгоритмов.

Интерес в практической деятельности представляют нормальные алгоритмы Маркова (НАМ). Они основаны на использовании абстрактных алфавитов и марковских подстановок. В качестве исходных данных и конечных результатов нормальные алгоритмы Маркова (НАМ) используют строки символов, т.е. слова абстрактных алфавитов.

Марковской подстановкой называют операцию над словами, задаваемую парой слов <P ,Q>, где P и Q —слова в абстрактном алфавите. Суть подстановки заключается в следующем. В исходном слове С определяется первое вхождение слова Р. Если оно есть, то производится замена этого вхождения словом Q без изменения остальных частей слова С. При этом слова P и Q должны иметь одинаковую размерность.

Пример 10.1. Пусть задано слово С = 832547, и задана пара <P, Q> = <32, 00>. Тогда результатом работы нормального алгоритма Маркова будет слово C’ = 800547.

Пример 10.2. Пусть задано слово С = 832547, и задана пара <P, Q> = <9, 4>). Отметим, что такая марковская подстановка к слову C не применима, так как в нем отсутствует цифра 9.

Нормальные алгоритмы Маркова применяют для анализа и преобразования формульных записей. Тогда НАМ работает следующим образом. Двигаясь по столбцу формул, определяют первую формулу, левая часть которой входит в преобразуемое слово; если такой формулы нет, то процесс окончен. При ее наличии выполняется марковская подстановка, изменяющая преобразуемое слово. После этого проверяется, заключительная ли это подстановка или нет. Если да, то процесс окончен, если нет, то весь процесс повторяется с самого начала.

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

1234567;

9713256;

0001111;

2224444.

И задана пара <P, Q> = <2, B>.

Тогда результат работы НАМ запишется следующим образом:

1В34567;

9713В56;

ВВВ4444.

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

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

Приведем пример записи ЛСА:

А₀ ¹ A₁ q ¹ ² A₂ p ² A_k.

Согласно этому выражению работа алгоритма начинается с выполнения левого оператора. Обычно это оператор А₀, представляющий собой начало алгоритма. Затем выполняется следующий справа оператор A₁. Следующий за оператором A₁ оператор q является логическим условием. Поэтому в зависимости от результатов проверки истинности этого условия будут выполняться либо оператор A₂ - если условие q - истинно, либо оператор A₁(по нисходящей стрелке). Аналогичные действия выполняются и для другого логического условия p. Последним в алгоритме является крайний правый оператор, обозначаемый обычно A_k. Он называется оператором окончания алгоритма.

В общем случае ЛСА Ляпунова должны удовлетворять следующим условиям:

1. Содержать один начальный и один конечный оператор, соответственно А₀ и A_k.

2. Каждому логическому условию должна соответствовать одна стрелка, направленная вверх.

3. Каждому логическому условию всегда соответствует, одна стрелка, направленная вниз.

4. Каждой восходящей (нисходящей) стрелке обязательно соответствует одна нисходящая(восходящая)стрелка.

Пример 10.3. Пусть задана последовательность из n натуральных целых чисел. Составить логическую схему алгоритма нахождения среднего арифметического этих чисел. Тогда данный алгоритм можем записать в виде логической схемы следующего вида:

А₀ ¹ A₁ q ¹ A₂ A₃ ² A₄ A₅ p ² A₆ A₇ A_k,

А₀ – начало алгоритма;

А₁ – ввод исходной последовательности чисел;

q – проверка логического условия: все ли числа введены;

А₂ – задание начального значения для подсчета суммы чисел: S = 0;

А₃ – ввод начального значения переменной цикла: i = 1;

А₄ – суммирование значений чисел последовательности: S = S + x_i;

А₅ – увеличение переменной цикла: i = i + 1;

p – проверка логического условия выхода из цикла: i > n;

А₆ – нахождение среднего арифметического последовательности чисел:  = S / n;

А₇ – вывод найденного значения;

А_k – конец работы алгоритма.

Рассмотрим графические схемы алгоритмов (ГСА). Они представляют собой графическую интерпретацию алгоритмов Ляпунова. Приведем основные правила представления графических схем алгоритмов:

• наличие конечного числа вершин;

• наличие одной начальной и одной конечной вершин;

• входы и выходы вершин соединяются между собой с помощью стрелок, направленных от входа к выходу;

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

• логическое условие имеет некоторое множество входов, но только два выхода («да», «нет»).

Следовательно, оператор начала А₀ может иметь только выходящие стрелки (рис. 10.5).

Рис. 10.5. Оператор начала ГСА

Оператор преобразования может иметь входящие и выходящие стрелки (рис. 10.6).

Рис. 10.6. Оператор преобразования ГСА

Логическое условие может иметь много входящих стрелок, выходящих стрелок может быть только две (рис. 10.7)

Рис. 10.7. Оператор логического условия

Оператор конца алгоритма имеет только входящие стрелки (рис. 10.8).

Рис. 10.8. Оператор окончания ГСА

Пример 10.4. Пусть задана логическая схема алгоритма следующего вида: А₀¹А₁р₁¹А₂р₂²А₃²А₄А₅А_k. На основе приведенных правил построим эту схему в виде ГСА (рис. 10.9).

Рис. 10.9. Графическая схема алгоритма (ГСА)

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

Правила выполнения структурных схем алгоритмов определены ГОСТом 19.701-90 (ИСО 5807-85) “Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения”. Фрагмент текста ГОСТа приведен в приложении. Руководствуясь требованиями данного ГОСТа, можно построить структурную схему алгоритма для решения конкретной задачи.

Пример 10.5. Пусть необходимо построить ССА нахождения минимального числа в заданном множестве чисел.

А = {a₁, a₂, a₃, a₄}; |A| = 4 = n, a₁ = 2, a₂ = 1, a₃ = 8, a₄ = 5.

Перед разработкой ССА производится распределение памяти, причем это распределение условное.

Блок «Начало» соответствует началу работы алгоритма.

Блок 1 ввод исходных данных.

Блок 2 задает начальное значение переменной i.

Блок 3 присваивает переменной x значение a_i, причем на первом шаге значение a_i равно a₁.

Блок 4 сравнивает значение переменной i с n. Это необходимо для определения момента окончания алгоритма.

Блок 5 увеличивает значение переменной i на единицу.

Блок 6 сравнивает предыдущее число a_i с последующим a_i+1.

Блок 7 печатает значение найденного минимального элемента a₂ = 1.

Блок «Конец» соответствует окончанию работы алгоритма.

На рис. 10.10 приведена структурная схема алгоритма.

Рис. 10.10. Пример структурной схемы алгоритма

Пример 10.6. Составить алгоритм определения среднего роста студента учебной группы.

Решение:

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

2. Математическая модель задачи может быть выражена соотношением

,

где l_i - рост i-го студента, n - число студентов в учебной группе.

6.3. Составляем структурную схему алгоритма. Вариант структурной схемы алгоритма для решения этой задачи показан на рис. 10.11.

Рис. 10.11. Вариант структурной схемы алгоритма к примеру 6

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

• следование - последовательное размещение блоков или их групп.

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

а) присваивание, где происходит задание начальных значений параметров вычисляемой величины;

б) тело цикла, представляющего собой последовательность многократно выполняемых действий;

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

Различают два типа циклических структур - цикл "с предусловием" (цикл «до») и цикл "с постусловием" (цикл «пока»). Цикл "до" (рис. 10.12, а) позволяет выполнять заданные действия (тело цикла) несколько раз, до тех пор, пока выполняется некоторое условие. Особенность преобразования информации здесь состоит в том, что цикл «до» выполняется всегда (по крайней мере, один раз), т.к. проверка условия выхода из цикла осуществляется только после выполнения действий. Цикл "пока" (рис. 10.12, б) позволяет выполнить заданные действия только после проверки условия. В этом случае цикл "пока", в отличие от цикла "до", может быть не выполнен ни разу;

• разветвление (рис. 10.13) позволяет выполнять, в зависимости от условия, то или иное действие (или группу действий).

• обход (рис. 10.14) представляет собой частный случай разветвления, когда при выполнении (или, наоборот, невыполнении) условия никаких действий не выполняется.

а) цикл «до»; б) цикл «пока»

Рис. 10.12. Типы циклических структур

Рис. 10.13. Структура разветвления

Рис. 10.14. Структура обхода

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

АЛГОРИТМ = {<элементарные алгоритмы>}.

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

Рассмотрим распространенный способ записи алгоритмов – словесное описание. В этом случае алгоритм задается через описание и перечисление операторов, аналогичных блокам, используемым структурной схемой алгоритма. Таким образом, словесная запись алгоритма представляет собой перечень операторов, пронумерованный в порядке их исполнения алгоритмом. При записи условных операторов помимо указания условия, истинность которого необходимо проверить, указываются также номера операторов, которым будет передаваться управление в зависимости от результатов проверки.

Пример 10.7. Приведем словесное описание структурной схемы алгоритма из примера 5.

1. Присвоить переменной i значение, равное 1.

2. Присвоить х значение, равное a_i (x — произвольная ячейка памяти).

3. Проверяем, i меньше n или нет. Если меньше, то переходим к п.4, иначе переходим к п.6.

4. Переменной i присвоить значение, равное i + 1.

5. Проверка логического условия a_i < x. Если условие выполняется, то переходим к п.2, если нет, то переходим к п.3.

6. Печать минимального числа из множества А.

7. Конец работы алгоритма.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Пример 10.1. Построить логическую схему алгоритма (ЛСА) подсчета арифметического выражения:

.

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

A₀ - начало программы;

А₁ - ввод объема выборки n;

А₂ - задание начальных значений переменной цикла i = 0 и промежуточной переменной С = 0;

А₃ - оператор увеличения переменной цикла: i = i + 1;

А₄ - вычисление значения индекса переменной b: j = n - i + 1;

А₅ - вычисление значения произведения: p = a_i  b_j;

A₆ - суммирование промежуточных значений p: С = С + p;

q - логический оператор проверки условия: i = n;

А₇ - вычисление значения исходного выражения: у = С  n;

А_k - конец программы.

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

А₀ А₁ А₂ ¹ А₃ А₄ А₅ А₆ q ¹ А₇ А_k.

Пример 10.2. Построить граф-схему алгоритма (ГСА) подсчета среднего арифметического значения ряда целых четных чисел длины n.

Решение. Графическая схема алгоритма (ГСА) показана на рис. 10.15.

Рис. 10.15. Граф-схема алгоритма

Для построения граф-схемы данного алгоритма используются следующие операторы:

A₀ - начало программы;

А₁ - оператор ввода размера интервала n;

А₂ - оператор ввода начального значения шага: i = 0;

А₃ - наращивание значения шага: i = i + 1;

А₄ - оператор выбора начального числа из заданного интервала а_i;

А₅ - вычисление значения: b = а_i  2;

А₆ - вычисление значения: b = b  2;

p - логический оператор проверки условия: a_i = b;

A₇ - промежуточное суммирование: S = S + a_i;

q - логический оператор проверки условия: i = n;

А₈ - подсчет среднего арифметического: Y = S  2;

А_k - конец программы.

Пример 10.3. Составить структурную схему алгоритма вычисления 50 значений функции:

Y_i = sin(x_i) x_i ,

где x_i - это одномерный массив натуральных чисел; i - индекс переменной в массиве: i = 1, 2, ..., 50;  - константа.

Решение. Для построения структурной схемы данного алгоритма используем следующие блоки (согласно ГОСТ 19.701-90):

Блок - “НАЧАЛО” - “Терминатор” - неисполняемый блок, символизирующий начало работы алгоритма, всегда располагается перед остальными блоками структурной схемы.

Блок 1 - “Ввод исходных данных” - “Процесс” - в данном блоке осуществляется ввод массива значений переменной x_i и значение константы .

Блок 2 - “i = 1“ - “Процесс” - задает начальное значение индекса переменной.

Блок 3 - “Y_i = sin(x_i ) x_i“- “Процесс” - производится подсчет значения функции Y_i при данном значении переменной x_{i .}

Блок 4 - “Печать значений Y_i и x_i“- “Процесс” - данный блок задает процедуру вывода на печать значений переменных Y_i и x_{i .}

Блок 5 - “i = i +1“- “Процесс” - увеличивает значение индекса i переменной х на единицу после каждого шага выполнения алгоритма.

Блок 6 - “i > 50“ - “Решение” - блок, осуществляющий управление циклом. В случае, если индекс i переменной x меньше или равен 50, т.е. алгоритм подсчитал меньше 50 значений функции Y_i, блок 6 передаст управление блоку 3, таким образом цикл будет повторяться до тех пор, пока не будет произведено 50 вычислений. После этого блок 6 передаст управление следующему по порядку блоку.

Блок - “КОНЕЦ” - “Терминатор” - неисполняемый блок, символизирующий окончание работы алгоритма, всегда располагается после остальных блоков структурной схемы.

Структурная схема алгоритма приведена на рис. 10.16.

Рис. 10.16. Структурная схема алгоритма

Нумерация блоков ведется сверху вниз. В данном примере используется следующий порядок описания блоков: номер блока, затем его название в данной структурной схеме, затем название блока в соответствии с ГОСТом и, наконец, небольшой комментарий к содержанию блока. Стрелки на концах некоторых соединительных линий необходимы, т.к. в соответствии с ГОСТ 19.701 - 90 стандартным считается “направление потока слева направо и сверху вниз”, а в рассматриваемой структурной схеме есть несколько потоков, имеющих нестандартную направленность (например, снизу вверх).

Пример 10.4. Записать словесный алгоритм вычисления выражения, заданного в примере 10.3.

Ответ. Словесная запись алгоритма вычисления исходного выражения будет выглядеть следующим образом:

1. Начало работы алгоритма.

2. Ввод исходных данных.

3. Присвоить i значение 1.

4. Вычислить значение переменной: Y_i = sin(x_i) / x_i.

5. Вывести на печать значения переменных х_i, Y_i.

6. Присвоить i значение: i + 1.

7. Проверка условия i > 50. Если условие истинно, то перейти к пункту 8 настоящего алгоритма, если условие ложно, то перейти к пункту 4.

8. Конец работы алгоритма.

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

Решение: Подробное описание всех блоков структурной схемы алгоритма не приводится, поскольку блоки структурной схемы будут аналогичны операторам граф - схемы алгоритма из примера 10.2. Приведем содержание основных 1-го и 3-го блоков.

Блок 1 - Ввод размера интервала n и начального значения шага i = 0;

Блок 3 - Выбор начального числа из интервала a;

Ответ. Структурная схема алгоритма показана на рис. 10.17.

Рис. 10.17. Пример структурной схемы алгоритма