Поиск наибольшего значения в массиве с помощью рекурсии

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

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

Что в основном начинается с первого элемента до последнего элемента массива, и алгоритм сравнивает каждое значение друг с другом, а самый большой элемент массива стоит отдельно в массиве (который вызывает базовый случай)

int largestValue(int anArray[], int first , int last){
int value;

// base case
if(first == last){
    value = anArray[first];
}
else if(anArray[first]>anArray[first+1]){
    anArray[first + 1] = anArray[first];
    value = largestValue(anArray, first + 1, last);
}else{ // anArray[first] < anArray[first + 1]
    value = largestValue(anArray, first + 1, last);
}
return value;

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

И я не мог понять алгоритм с точки зрения «многопутевой рекурсии».


c++ arrays recursion algorithm multipath
person Rutkay Karabulak    schedule 26.07.2020    source источник
comment
Разделите массив посередине, затем вызовите largestValue для каждой половины.   -  person Evg    schedule 26.07.2020
comment
@Evg, так что эта точка зрения основана на совместном использовании двух функций рекурсии?   -  person Rutkay Karabulak    schedule 26.07.2020
comment
Не пишите [SOLVED] в заголовке. Выберите ответ и примите его, пожалуйста.   -  person Waqar    schedule 26.07.2020

Ответы (3)


arrow_upward
2
arrow_downward

Я бы порекомендовал вам использовать вспомогательную функцию, которая вызывает вашу функцию с наибольшим значением следующим образом:

int largestValue(int arr[], int size){
    int middle = (size - 1)/2;
    int first_max = largestValue(arr, 0, middle);
    int second_max = largestValue(arr, middle + 1, largest - 1);
    if(first_max < second_max){
       return second_max;
    }
    return first_max;
}
person Yunfei Chen    schedule 26.07.2020

arrow_upward
5
arrow_downward

Разделите массив посередине, затем вызовите функцию для каждой половины:

template<class Random_it>
// typename std::iterator_traits<Random_it>::value_type
auto recursive_max(Random_it first, Random_it last) {
    assert(first != last);
    if (last - first == 1)
        return *first;
    const auto mid = first + (last - first) / 2;
    const auto l_max = recursive_max(first, mid);
    const auto r_max = recursive_max(mid,   last);
    return (r_max > l_max) ? r_max : l_max;
}

Пример использования:

std::vector<int> vec{/* init values */};
const auto max = recursive_max(vec.begin(), vec.end());

Демо

Обратите внимание, что здесь first и last представляют половину открытый интервал [first, last) в соответствии с соглашением, которое широко используется в стандартной библиотеке C++.

person Evg    schedule 26.07.2020

arrow_upward
1
arrow_downward

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

Простым решением будет следующее:

int largestValue(int anArray[], int first, int last) {
    if (first == last) {
        return anArray[first];
    }
    int middle = (first+last)/2;
    int left = largestValue(anArray, first, middle);
    int right = largestValue(anArray, middle+1, last);
    int max;
    if (left > right) {
        max = left;
    } else {
        max = right;
    }
    return max;
}
person phuppert    schedule 26.07.2020