Построение алгоритмов с разветвляющейся структурой.

1. Сущность разветвлений.

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

Пример 1. Если заданы величины p , q , r , s и нужно подсчитать количество М тех из них, которые превышают заданную величину a , то в ЭВМ это нельзя сделать иначе, как последовательной проверкой значений величин и увеличением на 1 значения М всякий раз, когда обнаруживается величина большая, чем a. Исходным значением М должен быть 0. Cледовательно, ЭВМ должна производить выбор очередного действия после рассмотрения каждой из величин p , q , r , s . Блок - схема соответствующего алгоритма показана на рисунке 2.1.

Данный алгоритм показывает характер проведения процесса при различных исходных данных. Например, величины p , q , r , s могут оказаться меньше a (все) и тогда блоки 4, 6, 8, 10 не выполняются, т.е. значение М останется равным 0.

КОНТРОЛЬНЫЕ ЗАДАНИЯ

I.I. Указать на рис. 2.1 номера блоков, исполняемых в случае, если величины g и r оказались больше a , а величины p и s – меньше a.

I.II. Укажите тип (целый, вещественный), который должна иметь переменная М, обоснуйте.

I.III. Построить иной алгоритм для решения данной задачи, в котором:

а) для представления исходных данных используется переменная a и переменная Х, принимающая поочередно значения проверяемых величин;

б

) имеется цикл, телом которого являются инструкции ВВОД Х, проверка условия Х > a (изображается в виде ромба с двумя выходами), М = М + 1; данный цикл заменяет блоки 3 - 10 (рис.2.1);

Рис. 2.1.

в) до цикла выполняются действия ВВОД a и М = 0.

Ответ к заданию I.III дан в конце описания лабораторной работы.

2. Элементы разветвлений

Пример 2. Заданы длины l₁ , l₂ , l₃ сторон треугольника, являющиеся значениями целого типа, причем такими, что сумма двух любых из них больше третьего. Необходимо, чтобы ЭВМ отпечатала сообщение: “ПРЯМОУГОЛЕН” в случае прямоугольности треугольника, либо сообщения “НЕПРЯМОУГОЛЕН“ - в противном случае.

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

у

казанная проверка заменена проверкой равенства, равносильного выше указанному: 2М?= В алгоритме имеется четыре разветвления. Рассмотрим часть, образованную блоками 2 … 8. Входящие в нее части, состоящие из блоков 3 … 5 и блоков 6 … 8, являются конкурирующими: если выбраны для исполнения блоки одной из них, то исполнение блоков другой части исключается. Такие взаимоисключающие части блок-схемы именуют

Рис. 2.2.

ветвями. Ветви 1 и 2 (см. рис.2.2) и сами по себе являются разветвленными, ибо каждая из них образована блоком проверки условия и двумя элементарными ветвями- инструкциями присваивания.

Особенностью разветвлений в примере 1 (рис.2.1) являются пустые ветви, изображаемые линиями потока между 3,5,7 и 9 блоками. Нередко ветви, относящиеся к разным разветвлениям, или их части могут быть совмещены, как, например, блоки 4 и 7 (см. рис.2.2).

Разветвленные участки могут входить в состав циклов, а циклы, в свою очередь, могут быть элементами разветвлений. Например, если бы потребовалось за одно исполнение алгоритма рассмотреть серию треугольников с заданными сторонами, то блоки 1 …11 (рис.2.2) составили бы разветвленное тело цикла, а за ним следовали бы изменение параметра цикла (номера треугольника) и управление циклом.