Лекция 5 Рекурсивные алгоритмы

Для характеристики относительного изменения полного напора по длине потока вводят понятие гидравлического уклона.

Средний гидравлический уклон на участке между сечениями 1–1 и 2–2 (рис. 4.6) определяется как отношение потери напора к длине участка:

,

где l_1-2 - расстояние (по пути движения) между сечениями 1–1 и 2–2.

Гидравлический уклон - безразмерная положительная величина.

Гидравлический уклон в сечении потока определяется выражением

.

Знак «-» указывает на убывание полного напора по течению.

Понятие об уклоне можно ввести и для пьезометрической линии.

Средний пьезометрический уклон

.

Пьезометрический уклон для некоторого сечения потока

.

Пьезометрический уклон может быть положительным, равным нулю и отрицательным.

Литература по содержанию лекции:

1. Чугаев Р. Р. Гидравлика (Техническая механика жидкости). - Л.: Энергоиздат, 1982. - 672 с.

2. Штеренлихт Д. В. Гидравлика. - М.: Энергоатомиздат, 1985. - 640 с.

Лекция 5 Рекурсивные алгоритмы

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

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

Неразрывно с понятием рекурсивного алгоритма связано понятие рекурсивной функции. Существует два определения этого понятия.

Первое определение рекурсивной функцииотносится ктеории вычислимостии являетсясинонимом понятия вычислимой функции, т. е. функции,для вычислениязначения которой можно указать алгоритм.

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

Рекурсивная функция – это функция, которая вызывает саму себя.

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

1. Примеры простейших рекурсивных функций

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

Рис. 2. Нерекурсивная функциявычисления факториала числа

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

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

Рис. 3. Пример рекурсивной функции, использующей два рекурсивных вызова