1

我最近一直在研究“数据抽象和用 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;

但是，在我阅读了问题的描述之后，有人说“你必须用多路径递归来解决这个问题。” 为了更好地理解我把问题的截图： 在此处输入图像描述

而且我想不出具有“多路径递归”视角的算法。

4

3 回答 3

4

在中间拆分数组，然后为每一半调用函数：

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++ 标准库中广泛使用的约定一致。

于 2020-07-26T20:18:53.870 回答
2

我建议你使用一个辅助函数来调用你的最大值函数，如下所示：

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;
}
于 2020-07-26T20:19:18.420 回答
1

递归算法只是将数组一分为二并递归地找到最大值，然后将两者进行比较并返回最大值。您需要做的是使用边界 first 和 last 来告诉您要计算数组的哪个部分的最大值。

一个简单的解决方案如下：

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;
}
于 2020-07-26T20:27:02.580 回答