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

⇐ ПредыдущаяСтр 2 из 2

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

Вычисление функций с условием.

Задача вычисления функции с условием в общем виде может быть сформулирована в следующем виде (слайд 26): вычислить

g₁(x), если c₁;

g₂(x), если c₂;

f(x) = ………………...

g_n(x), если c_n.

Очевидно, что для решения данной задачи необходимо использовать разветвляющуюся алгоритмическую структуру: при n = 2 – стандартное разветвление, при n = 3 – вложенное разветвление.

Рассмотрим пример алгоритма вычисления условной функции для случая n = 3. Пусть необходимо вычислить

e^x, если x <= -1;

y = ln x, если x > 1;

2, если –1 <х ≤1.

На слайде 27 приведен возможный алгоритм решения задачи и его реализация в виде функции Comp l 3.

double Compl3( double x) { double y ; if (x <= - 1) y = exp(x); else if (x > 1) y = log(x); else y = 2; return y; }

Выбор наибольшего (наименьшего) из нескольких значений.

Выбор наибольшего (наименьшего) из нескольких значений производится путем последовательного сравнения этих значений между собой. Количество требуемых сравнений всегда на единицу меньше количества значений: 1 сравнение для выбора из 2 значений, 2 сравнения для выбора из 3 значений и т.д.

Различные алгоритмы выбора отличаются порядком выполнения сравнений и способом формирования результирующего значения. При этом выбор наименьшего значения отличается от выбора наибольшего только знаком операций сравнения: меньше (<) или больше (>).

Рассмотрим сначала задачу выбора наибольшего из 2 значений:

f = max {x , y }.

На слайде 28 изображены варианты алгоритмов решения задачи и их программные реализации в виде функций Max 21 и Max22: со стандартным разветвлением и с усеченным разветвлением.

double Max21( double x, double y) { double f; if (x > y) f = x; else f = y; return f; }

double Max22( double x, double y) { double f=x; if (y>f) f = y; return f; }

Если выбирать между этими двумя алгоритмами, то предпочтение следует отдать первому варианту со стандартным разветвлением: он более компактен при программировании и более эффективен. Что означает большая эффективность? Представим себе, что задача выбора решается многократно, и каждый раз равновероятно выполнение условий x > y и x < y. Тогда в первом алгоритме всегда выполняется 1 сравнение и 1 присваивание. Во втором алгоритме тоже всегда выполняется 1 сравнение, но либо 1, либо 2 присваивания, то есть в среднем 1,5 присваивания.

Рассмотрим теперь задачу выбор наименьшего из 3 значений:

f = m in{x , y , z }.

Если мы попытаемся пойти по первому пути, то в ветвях первой проверки окажутся 2 стандартных разветвления. Такая структура очень громоздка и неудобна для программирования. Эти недостатки усугубляются при выборе наибольшего (наименьшего) из 4 и более значений. Поэтому пренебрежем меньшей эффективностью и решим поставленную задачу вторым способом: с использованием усеченных разветвлений.

На слайде 29 изображена схема алгоритма решения задачи и его программная реализация в виде функции Min 3.

double Min3( double x, double y, double z) { double f=x; if (y<f) f = y; if (z<f) f = z; return f; }

Как видно из схемы, сначала результирующей переменной f присваивается значение первой из трех входных переменных x. Затем производится сравнение y с f, и если y меньше f, то f присваивается меньшее значение y. Если же y не меньше f, то в f остается прежнее значение переменной x. Таким образом, после выполнения первого усеченного разветвления в f оказывается наименьшее из 2 значений: x или y. Аналогично, после выполнения второго усеченного разветвления f будет содержать наименьшее из 3 значений x, y или z.

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

Тернарная условная операция

По смыслу тернарная условная операция (?:) идентична конструкции if … else, но выглядит компактнее. Она тернарная, так как имеет три операнда. Ее формат:

операнд_1 ? операнд_2 : операнд_3;

Первый операнд - это, как правило, логическое выражение (арифметическое выражение, значение которого оценивается с точки зрения эквивалентности нулю; операнд, равный нулю, рассматривается как false, не равный нулю – как true). Сначала вычисляется значение операнда_1, и если оно равно true, то вычисляется операнд_2 , иначе вычисляется операнд_3. Операция возвращает результат вычисления.

Уже рассмотренную задачу выбора наибольшего из 2 значений

f = max {x , y } ,

решенную с помощью оператора:

if (x > y) f = x; else f = y;

можно так переписать с помощью тернарной операции:

f = (x>y)? x : y;

Заключать условие x>y в скобки необязательно, но читается так лучше.

Дата добавления: 2020-11-27; просмотров: 148; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 12

Мы поможем в написании ваших работ!