Составление разветвляющихся алгоритмов

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

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

Задача 1.1. Вычислить значение Y по одной из формул:

Y = { X + aесли X < 10(1)
X — b1если 10 <= X <= 20(2)
c + b2если 20 < X < 30(3)
c — b3если 30 <= X(4)

где X = 3√a + b1.

Здесь b1, b2, b3 будем рассматривать как элементы массива В(1:3).

Условие задачи означает, что У зависит от X, а X может принимать любое значение из интервала (-∞, +∞). Этот интервал разбит на четыре области и в пределах каждой области У вычисляется по одной из формул. Значение х = 10 является границей для первой и второй областей; х = 20 — для второй и третьей, а х = 30 — для третьей и четвертой областей.

Решение.

1. Исходные данные: с, а, B(1:3). Результаты: X, У.

2. Метод решения задачи (в общем виде):

— ввод с, а, B(1:3);

— вычисление X;

— вычисление Y;

— вывод X, У.

3. Укрупненная схема алгоритма (фрагмент схемы) показана ниже.

Рассмотрим подробно блок 2 этой схемы.

Метод решения задачи: он должен обеспечить выявление области, которой принадлежит значение X, для чего достаточно проверить заданные условия по порядку, например, сверху вниз:

Проверяем Х < 10,если условие истинно (Да), вычисляем У = Х + а;
если условие ложно (Нет), проверяем:
10 <= X <= 20,если Да, вычисляем У = Х — b1;
если Нет, проверяем:
20 < Х < 30,если Да, вычисляем Y = c + b2;
если Нет, вычисляем У = с — b3

Процесс решения задачи распадается на этапы (операции):

— «проверка истинности условия»,

— «вычисление по формуле».

Согласно Основным принципам алгоритмизации, заменяем каждую такую операцию соответствующим блоком — ромбом, прямоугольником и соединяем согласно порядку их выполнения линиями. В итоге получаем схему блока 2. Объединив ее с блоками 1 и 3, получим схему алгоритма всей задачи.

Изображая в схеме логический блок, следует выяснить и указать в явном виде, какому условию отвечает проверяемая переменная (в нашем случае — X) на выходе Нет этого блока. Полученную информацию следует использовать при реализации последующих условий. Так, для проверки условия (2) нашей задачи (10 <= X <= 20) достаточно проверить отношение Х <= 20, поскольку на входе второго логического блока отношение 10 <= Х всегда истинно. Аналогично для проверки условия (3) достаточно проверить одно отношение: Х < 30; информация на выходе Нет третьего логического блока (условие 30 <= Х - истинно) позволяет исключить отдельный блок для проверки условия (4).

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

Задача 2.1. Определить Y = max { X,Z }.

Решение.

1. Исходные данные: X, Z. Результат: Y.

2. Метод решения задачи очевиден и предполагает выполнение трех основных операций. Применяя основные принципы алгоритмизации, получим схему алгоритма. Фрагмент ее приведен на рисунке ниже.

Задача 2.2. Определить значение наибольшего элемента главной диагонали матрицы А(1:3, 1:3).

Решение.

1. Исходные данные:

2. Результат: Y, т. е. Y = max {a11, a22, a33}.

Рассмотрим два варианта решения задачи.

Первый вариант.

Метод решения задачи:

проверяем a11 > a22

если Да, проверяем а11 > а33

Если Да — Y = a11

Если Нет — Y = a33

если Нет, проверяем а22 > а33

Если Да — Y = a22

Если Нет — Y = a33

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

Второй вариант.

Метод решения задачи:

— ввод А(1:3, 1:3);

— определение Z = max{a11, a22};

— определение Y = max{Z, a33};

— вывод Y.

Укрупненная схема алгоритма, отражающая этот процесс (точнее, ее фрагмент), приведена на рисунке ниже.

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

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

III. Часто встречаются задачи, в которых используются не только простые условия, но и составные, (использование условий с операциями и, или, не).

Например, контролер ОТК завода решает задачу — отобрать из числа изготовленных болты длиной Z, допустим 18 мм, и диаметром d не менее 7 мм и не более 8 мм.

Другой пример: школьник выяснил, что сможет попасть в кино при условии, если в кассе есть билеты по цене 40 или 50 руб.

В первом примере мы имеем дело с тремя отношениями, связанными между собой союзом «и» и частицей «не», во втором — с двумя отношениями, связанными союзом «или».

Условия наших примеров в алгоритме могут выглядеть в виде составных условий таким образом:

первое — (l = 18) и (не (d <= 7)) и (не (d > 8)) или, что то же: (l = 18 и d >= 7 и d <= 8);

второе — С = 40 или С = 50.

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

1. Составное условие рассматривается как «единое и неделимое» и в схеме изображается одним логическим блоком. Такой подход допустим, если в языке программирования, на который мы ориентируемся, составные условия разрешены.

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

Подобная схема имеет два выхода (Да и Нет) и обеспечивает «передачу управления» (так принято говорить) на один выход, если составное условие выполняется, и на другой — если оно не выполняется.

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

Задача 3.1. Вычислить значение Y по одной из формул:

Y = { X + Zесли Х < 10 и Z > 5
X * Zв остальных случаях

Решение.

Составим схему алгоритма задачи, используя второй подход. Метод решения задачи вытекает из определения составного условия «А и В»:

проверяем Х < 10

если Да, проверяем Z > 5

если Да — Y = X + Z

если Нет — Y = X * Z

если Нет — Y = X * Z

Руководствуясь основными принципами алгоритмизации, составляем схему алгоритма задачи:

Здесь блоки 1 и 2 образуют схему, реализующую составное условие «А и В». Точки D и N — выходы Да и Нет соответственно схемы, реализующей указанное условие. Отметим, что при использовании первого подхода алгоритм решения задачи описывается простейшей схемой.