Алгоритмизация ветвящихся процессов

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

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

Ветвящиеся алгоритмы изобра- жаются на схеме с помощью управ- ляющей структуры «Развилка» (рис. 9), где ЛВ – логическое выражение, за- дающее проверяемое условие. С1 и С2 –

последовательность любых блоков, кроме блоков «Начало» и «Конец». Логиче- ские выражения строятся с помощью операндов и знаков сравнения (>, <, =,<>) и логических операций (И-AND, ИЛИ-OR, НЕ-NOT). Если логическое выражение записывается с помощью логических операций, то оно называется сложным. Лю- бое сложное логическое условие может быть представлено в виде простых.

В управляющей структуре «Развилка», в условном блоке записывается логическое выражение. Если оно принимает значение «ИСТИНА» (условие вы- полняется), то вычисления идут по ветке «ДА», т. е. выполняется блок С1, блок C2 игнорируется. Если логическое выражение принимает значение «ЛОЖЬ» (условие не выполняется), то вычисления идут по ветке «НЕТ», т. е. выполняет- ся блок С2, а блок С1 игнорируется.

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

В некоторых алгоритмах могут использоваться варианты «развилки» – неполная развилка (рис. 10) и вложенная развилка (рис. 11). Вложенная развил- ка используется для организации сложных ветвлений.

 

Задача 5.

Определить, в каком из супермаркетов «Слата», «Бонус» или «Удача»

цена за 1 кг яблок ниже.

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

Формализованная постановка задачи записывается следующим образом:

Исходные данные:   A, B, C – заданные числа.

Выходные данные:  MIN – максимальное число,

MAR – название супермаркета Рабочие переменные: MIN – текущее значение максимума. Формулы, рассчитывающие результаты:

МIN = min(a,b); MIN = min (min(a,b),c)).

Для решения этой задачи предлагается следующий алгоритм. Сначала сравниваются первые два числа, из них выбирается минимальное. Затем вы- бранное число сравнивается с третьим, меньшее из них и будет искомым мини- мальным числом. На блок-схеме 4 изображен этот алгоритм решения задачи, а программа Min1 реализует его.

В предложенном алгоритме используются две следующих друг за другом управляющих структуры «развилка» и «неполная развилка», а переменная MIN выступает в двух ролях: в качестве рабочей переменной для промежуточных расчетов и в качестве выходного значения. После первого сравнения двух чисел (значения переменных А и В) в переменную МIN заносится большее значение. Для следующего сравнения используются переменные МIN и C.

 

 

НАЧАЛО

ВЕЩЕСТВЕННОЕ A, B, C, MIN

 

ВВОДA, B, C

 

 

ЕСЛИ A < B ТО

MIN:=A

MAR:= “Слата”

ИНАЧЕ

MIN:=B

MAR:= “Бонус”

 

КОНЕЦ развилки;

 

 

ЕСЛИ C < MIN ТО

MIN:= C

MAR:= “Удача”

 

КОНЕЦ развилки;

 

 

ВЫВОД MIN

 

 

 

Блок-схема 4

КОНЕЦ.

 

 

Программа Max1

Задача 6.

Вычислить значение Y по следующему правилу:

 

Постановка задачи: требуется вычислить значение переменной Y, при за- данных значениях a, b, c и x в зависимости от выполнения следующих условий:

- если модуль числа x больше 1, то Y вычисляется как разность Макси- мального значения среди b и а и минимума между b и c;

- если модуль числа x равен 1, то Y вычисляется как разность между a и минимумом между b и c;

- если модуль числа x меньше 1, то Y вычисляется как разность между максимумом а и b и числа с.

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

Исходные данные: A,B,C,X

Выходные данные: Y

Рабочие переменные: MAX = max (A,B); MIN = min (B,C), MOD = |X|.

Изучив постановку задачи, понимаем, что алгоритм ее решения представ- ляет собой ветвящийся процесс с проверкой значения модуля числа х и вычис- лениями значений минимума и максимума из двух чисел a и b. При реализации алгоритма следует организовать вложенную развилку для проверки заданных условий, при этом следует помнить, что при конкретных значениях исходных данных вычисления идут только по одной из возможных ветвей алгоритма. Ал- горитм решения задачи изображен на блок-схеме 5.

Комментарии к алгоритму. Предложенный алгоритм решения постав- ленной задачи начинается с проверки основного условия, для которого необхо- димо предварительно вычислить модуль числа х (переменная MOD). На ветви

«mod>1» сначала вычисляем максимальное значение между a и b, и минималь- ное между b и c, затем вычисляем значение Y, используя вычисленные значе- ния рабочих переменных. На ветви «mod<1» сначала вычисляем максимальное значение между a и b, затем вычисляем значение Y. На ветви «mod=1» сначала вычисляем минимальное значение между b и c, затем вычисляем значение Y. После закрытия внутренней и внешней развилки с помощью блока вывода вы- водим значение переменной Y и обозначаем конец алгоритма.

Блок-схема 5

 

Критически рассмотрев предложенный алгоритм, можно заметить, что в нем дублируется запись вычислений значений минимума и максимума. В дан- ном алгоритме это необходимо, так как при конкретных значениях исходных данных вычисления идут только по одной из возможных ветвей алгоритма. Дублируется именно запись вычислений, при выполнении алгоритма повтор- ных вычислений не будет. Можно избежать названного дублирования. Для это- го вычисления значений рабочих переменных MAX и MIN оформим до провер- ки условия с модулем. Тогда блок-схема будет выглядеть более компактно (блок-схему 6).

 

 

 

 

Блок-схема 6

 

В этом алгоритме вычисление значений минимума и максимума осущест- вляется до проверки основного условия. На ветвях вложенной развилки оста- ются только операции вычисления Y с использованием проведенных ранее промежуточных расчетов.

Задача 7.

Поступивший на торговое предприятие товар характеризуется тремя ви- дами цен: цена поступления, минимальная розничная цена, максималь- ная розничная цена. Требуется установить цену «прайс», по которой данный товар будет продаваться в розничных магазинах, в соответствии со следующими правилами. Если цена поступления ниже 60 р., то уста- новить торговую наценку 22 %, если цена поступления находится в диа- пазоне от 60 до 100 р., то установить торговую наценку 16 %, если цена товара больше 100 р., то установить торговую наценку 12 %. При этом расчетную цену округлить до 50 коп. Если расчетная цена оказалась меньше минимальной розничной цены, то цену «прайс» установить рав- ной минимальной розничной цене, если расчетная цена оказалась боль- ше максимальной розничной цены, то цену «прайс» установить равной максимальной розничной цене, в противном случае цену «прайс» уста- новить равной расчетной цене.

Опишем формализованную постановку задачи.

Исходные данные: ЦП – цена поступления;

МахЦ – максимальная розничная цена; МинЦ – минимальная розничная цена.

Выходные данные: Прайс – цена, для реализации в розничных магазинах.

Рабочие переменные: РЦ1 – расчетная цена с учетом торговой наценки; РЦ – расчетная цена с учетом округления до 50 коп.

Формула для округления цены до 50 коп. выглядит следующим образом:

Новая цена = [цена ∗ 2 + 0,5]

2

Расчетные формулы:

ЦП ∗ 1.22, если ЦП < 60

РЦ1 =     ЦП ∗ 1.12, если ЦП > 100

ЦП ∗ 1.16, если 60 $: ЦП $: 100

 

РЦ = [цена ∗ 2 + 0,5]

2

МинЦ, если РЦ < МинЦ

Прайс = МахЦ, если РЦ > МахЦ

РЦ, в противном случае

 

Алгоритм решения задачи представлен на блок-схеме 7.

 

Блок-схема 7