Задача поиска максимума.

Результаты выполнения программ.

Теоретическое введение.

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

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

Задача поиска максимума.

Рассмотрим в качестве примера задачу отыскания максимального из N элементов, сохраненных в массиве a[0],…, a[N-1]. Эту задачу легко выполнить за один проход массива:

for (t=a[0], i=1; i<N; i++)

if (a[i]>t) t=a[i];

Рекурсивное решение типа «разделяй и властвуй» (функция Maximum ), приведенное в примере 1 и использующееся в программе 1 – еще один простой

(хотя и совершенно иной) алгоритм решения той же задачи; он использовался только с целью иллюстрации концепции «разделяй и властвуй».

Пример 1:

-------------------------------------------------------------------------------------------------------

int Maximum(int a[10], int l, int r)//заголовок ф-ии

{//a-исходный массив, l-индекс 1-го эл-та, r-индекс //последнего эл-та

if (l==r) return a[l];//если массив состоит из 1-го //эл-та, то он и есть max

int m=(l+r)/2;//делим массив на 2 подмассива

int u=Maximum(a,l,m);//ищем в 1-ом максимальный эл-т

int v=Maximum(a,m+1,r);//во 2-ом также ищем //максимальный эл-т

if (u>v) return u; else return v;//сравнивая их, возвращаем максимальный

}

Эта функция делит массив a[l],…,a[r]на массивы a[l],…,a[m]и a[m+1],…,a[r], находит максимальные элементы в обоих частях (рекурсивно) и возвращает больший из них в качестве максимального элемента всего массива. Если размер массива является четным числом, обе части имеют одинаковые размеры, если же нечетным, эти размеры различаются на 1.

-------------------------------------------------------------------------------------------------------

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

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

Рисунок 1:

-------------------------------------------------------------------------------------------------------

0 1 2 3 4 5 6 7 8 9 10