Не знаю как сделать поиск максимального элемента массива с помощью рекурсии. Есть идеи?
#include
using namespace std;
const int n = 5;
float a[n + 1];
int fmax(float a[], int nach, int kon);
int main() {
int i, k; for(i = 1; i <= n; i++) {
cout << "\n введи a[" << i << "] ";
cin >> a[i];
} for(i = 1; i <= n; i++) {
cout << " a[" << i << "]=" << a[i];
}
cout << "\n";
cout << fmax(a[5], 0, 4); return(0);
}
int fmax(float a[], int nach, int kon)
{
int k, kmax;
float max;
kmax = nach;
max = a[nach];
for(k = nach; k <= kon; k++)
{
if(a[k] > max)
{
max = a[k]; kmax = k;
}
}
return kmax;
}
Ответы
Ответ 1
Как и для других рекурсивных функций, достаточно реализовать простейший случай и
вызвать эту же функцию с меньшей задачей:
template
ForwardIt max_element(ForwardIt first, ForwardIt last, ForwardIt largest)
{
if (first == last) // no more elements to compare
return largest;
if (*largest < *first) // compare with the first element
largest = first;
++first;
return max_element(first, last, largest); // compare the rest
}
если слово template не ясно, то чтобы не отвлекаться (это не важно для понимания
рекурсии), можно просто заменить ForwardIt на float*.
Простейшим случаем здесь является пустой массив (first == last), в этом случае функция
просто возвращает largest аргумент.
Чтобы уменьшить размер задачи, можно отбросить первый элемент first—обновив largest,
если необходимо—и вызвать функцию рекурсивно c остатками ввода, чтобы завершить решение
задачи.
Для удобства использования, можно определить функцию с двумя параметрами, передавfirst
в качестве начального значения для largest—это работает и для пустых массивов, в этом
случае возвращается значение равное last:
template
ForwardIt max_element(ForwardIt first, ForwardIt last)
{
return max_element(first, last, first);
}
Пример использования:
#include
int main()
{
float a[] = {1, -2, 3, 0.5};
std::cout << *max_element(a, a + sizeof(a) / sizeof(*a)) << '\n';
}
Чтобы запустить:
$ g++ max_recursive.cc && ./a.out
3
В данном случае max_element() является так называемой tail-recursive функцией—рекурсивный
вызов является хвостовым (последним) в функции и может не потреблять стек. Некоторые
компиляторы умеют автоматически преобразовывать подобный код в циклы, например, gcc
-O2 для ForwardIt=int* может сгенерировать вот такой ассемблер:
# first : %rdi
# last : %rsi
# largest: %rdx
# result : %rax
max_element(int*, int*, int*):
cmpq %rsi, %rdi # x = cmp(first, last)
movq %rdx, %rax # result = largest
je .L2 # if(first == last) return result // if(!x)
.L4: # do {
movl (%rdi), %ecx # y = *first
cmpl %ecx, (%rax) # z = cmp(*result, y)
cmovl %rdi, %rax # if (*result < y) result = first //if(z<0)
addq $4, %rdi # ++first
cmpq %rdi, %rsi # x = cmp(last, first)
jne .L4 # } while (last != first) // while(x)
.L2:
rep ret # return result // rep is amd
// brancher bug workaround
Абсолютно такой же код получается из итеративной версии:
int* max_element(int* first, int* last, int* largest)
{
for ( ; first != last; ++first)
if (*largest < *first)
largest = first;
return largest;
}
Ответ 2
Можно, например, вот так:
#include
#include
#include
int max(const std::vector::const_iterator& begin, std::vector::const_iterator&
end, int curentMax)
{
if(begin == end)
return curentMax;
if(*begin > curentMax)
return max(begin + 1, end, *begin);
return max(begin + 1, end, curentMax);
}
int main()
{
std::vector array{1, 55, 17, 77, 88, 13, 45, 72, 11};
std::cout << max(array.сbegin(), array.сend(), std::numeric_limits::min())
<< "\n";
}
Есть массив,— вектор, в котором находится некоторый набор данных. Я в функцию max
передаю итераторы(можно считать указатели) на начало и конец(на одну позицию за концом)
массива. Базовым случаем рекурсии будет случай, когда элементы массива кончились, т.е.
начало и конец, переданные в аргументах, совпадают. В рекурсивном шаге мы проверяем,
является ли элемент, который находится в начала переданного промежутка большим, по
отношению к уже найденному максимальному, если да, то используем его, если нет, то
используем ранее найденный max.
Ответ 3
Вот еще вариант для массива (не вектора), с делением такового пополам (быстрее от
этого, конечно, он не работает :))
// Максимальный элемент в массиве array с индексами [start,stop)
int maxel(int * array, int start, int stop)
{
if (start == stop-1) return array[start];
int mid = (start + stop)/2;
int m1 = maxel(array,start,mid), m2 = maxel(array,mid,stop);
return (m1 > m2) ? m1 : m2;
}
int main(int argc, const char * argv[])
{
int x[] = { 1,2,15,2,41,18,-4,2 };
cout << maxel(x,0,sizeof(x)/sizeof(x[0]));
}
Ответ 4
Как рекурсию всегда можно представить итерацией, так и наоборот.
В своем примере поиска максимума Вы используя итерацию перебираете все элементы массива,
соответственно простейшим будет вот такой естественный "однострочник" с рекурсией,
возвращающий максимум:
float rfmax (float *a, int n, float cmax) {
return n > 0 ? rfmax(a + 1, --n, cmax > *a ? cmax : *a) : cmax;
}
который на каждом следующем шаге рекурсии сдвигает начало массива на следующий элемент
и уменьшает количество элементов в нем на один.
Вызывать можно вот так:
int n = ...
float a[n];
...
printf("max: %f\n", rfmax(a + 1, n - 1, a[0]));
Однако, в Вашем примере несколько другая процедура, которая перебирает элементы
некоторого диапазона массива и возвращает индекс максимального в нем. Здесь по всем
шагам рекурсии нам надо вместе с текущим максимумом тащить еще и его индекс, который
в конце-концов и возвращается как результат.
Пожалуй, однострочник для нее выглядит несколько вычурно, соответственно, рекурсивный
вариант, максимально похожий на Ваш пример, можно написать так:
int ixfmax (float a[], int start, int end, float cmax, int icmax) {
if (start > end)
return icmax;
if (cmax < a[start])
cmax = a[icmax = start];
return ixfmax(a, start + 1, end, cmax, icmax);
}
и вот так использовать его для поиска максимального элемента во всем массиве
int imax = ixfmax(a, 1, n - 1, a[0], 0);
printf("max: a[%d] = %f\n", imax, a[imax]);
Довольно естественно, что если при поиске мы сначала полагаем, что начальный элемент
это максимум, то поиск проводим со следующего элемента. В самом деле,
зачем его сравнивать с самим собой?
