Пусть одномерный массив задан вектором v = (v₀, v₁, ... , v_n-1). Часто возникает задача поиска максимального (минимального) элемента v. Вне зависимости от того, идет ли речь о нахождении максимального по значению элемента или его позиции в v, поиск можно реализовать за один просмотр массива. Правда, в последнем случае решение может оказаться неоднозначным и постановка задачи требует уточнения. Например, отыскивается позиция максимального элемента с наименьшим индексом. В любом случае сравнение характеристик различных алгоритмов поиска проводят по количеству тех или иных выполняемых ими операций. Чаще всего это операции сравнения.

Рекурсивная функция maxv(v) находит максимальный элемент v ровно за n-1 операцию сравнения. Декомпозиция реализуется по длине вектора и опирается на такое утверждение. Решить исходную задачу для v - это то же самое, что решить её для подвектора, получаемого из v удалением его первого компонента, сравнить полученное значение с удаленным элементом и, наконец, выбрать не меньшее из них:

Контрольный пример:

v := (7    5    -3    9    11    3    -17    2    8)^T,      maxv(v) = 11.

Замечание. При подсчете количества операций сравнения элементов массива не учитываются сравнения с управляющими переменными рекурсии или цикла. Это же самое касается и других программ, приведенных ниже.

Аналогично строится и функция minv(v) - нахождения за n-1 операцию сравнения минимального по значению элемента массива. Нетрудно написать рекурсивную функцию одновременного поиска минимального и максимального значений v за 2×n-2 операции сравнения. Выглядеть она может, например, так:

Контрольный пример:

v := (7    5    -3    9    11    3    -17    2    8)^T,      minmaxv(v)^Т = [-17    11].

Однако одновременное нахождение максимального и минимального значений v может быть реализовано гораздо эффективней. Соответствующий результат зафиксирован в следующей задаче.

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

Решение. Если длина вектора v равна единице, то решением задачи можно считать вектор [v₀   v₀]^T. При длине вектора v, равной двум, решение находится за одно сравнение. Пусть длина вектора больше двух. Тогда из двух первых компонентов непосредственно найдем наибольшее и наименьшее значение (одно сравнение), решим исходную задачу для подвектора, получающегося из v удалением этих компонентов, и, наконец, осуществим правку полученного решения для подвектора за счет первых двух компонентов (два сравнения). Именно эти идеи и реализуются рекурсивной функцией minmax():

Контрольный пример:

v := (6    2    9    11    7    5    3)^T,      minmax(v)^T = [2    11].

Подсчитаем теперь S - общее количество сравнений:

Тем самым решение задачи завершено полностью.

В следующем варианте minmax() - функции minmax1() используются три вспомогательных параметра: a, b, i. Первые два из них служат для фиксации текущих значений минимального и максимального элементов массива, а последний - для нумерации рекурсивных обращений. Как и в предыдущем случае, каждый рекурсивный вызов уменьшает обрабатываемый массив на два элемента. Но здесь, в отличие от minmax(), они удаляются с разных его концов. Использование вспомогательной функции mima(v) избавляет нас от сложного обращения к minmax1().

Контрольный пример:

v := (6    2    9    11    7    5    3)^T,      mima(v)^T = [2    11].

адача 35. Написать рекурсивную программу-функцию, находящую одновременно позиции максимального и минимального элементов массива v за операций сравнения.

Решение. Для решения данной задачи можно использовать тот же самый алгоритм, который реализуется функцией minmax1(), подвергая запоминанию не текущие значения минимального и максимального элементов массива, а их индексы. Соответствующие функции posmima() и pmima() можно записать так:

Контрольный пример:

v := (6    2    9    11    7    5    3)^T,      pmima(v)^T = [1    3].

Замечание. Рекурсивная функция posmima() позволяет реализовать сортировку массива v по такому алгоритму:

Контрольные примеры:

v := (95    20    35    29    9    70)^T,      sorti(v)^T = (9    20    29    35    70    95);

v := (96    87    40    65    94    0)^T,      sorti(v)^T = (0    40    65    87    94    96).