如何使用分而治之和迭代器添加所有向量元素?

问题描述

我需要编写一个函数来汇总向量的所有元素.规范是它必须通过递归完成，唯一的参数输入将是迭代器.函数应该:将向量一分为二，在左边递归，在右边递归，返回两边的和.我写了下面的代码，但我得到了不正确的答案.

I needed to write a function that sums up all elements of a vector. Specifications are that it has to be done by recursion and the only parameters input would be iterators. The function should:Divide the vector in half, recurse on the left hand side, recurse on the right hand side, return the sum of both sides. I wrote the code below but I am getting an incorrect answer.

int sumVectorRecurse(vector<int>::iterator left, vector<int>::iterator right)
{
    if (left != right){
        int midPosition = (right - left)/2;
        vector<int>::iterator mid = left + midPosition;
        return (sumVectorRecurse(left, mid) + sumVectorRecurse(mid+1, right));
    }
    else return *left;
}

int main(){

    vector<int> v = {1,2,3,4};
    cout << endl << "THIS IS QUESTION 4:"<< endl;
    cout << sumVectorRecurse(v.begin(), v.end());

}

更新:向量的输出在 {1,2,3,4} 之前是可以的，但是一旦我添加 5 使它成为 {1,2,3,4,5} 输出为32782"

Update: the output is okay for a vector till {1,2,3,4} but once I add 5 to it making it {1,2,3,4,5} the output is "32782"

推荐答案

您正在取消引用 end 迭代器，这是未定义的行为.

You are dereferencing the end iterator, which is undefined behavior.

按照惯例，C++ 范围由一对迭代器指定，其中左迭代器指向第一项，而右迭代器指向最后一项之后.这允许一个范围为空，通过 begin == end.

C++ ranges are, by convention, specified by a pair of iterators where the left iterator points to the first item, and the right iterator points one past the last item. This allows a range to be empty, by having begin == end.

您的基本情况应该是:

if (left == right) return 0;
if (left + 1 == right) return *left;

然后，将 mid 传递给递归的两半，因为它将被包含在后半部分(它是左迭代器)中，而被排除在前半部分(它是左迭代器)中结束迭代器).

Then, pass mid to both halves of the recursion, because it will be included in the second half (where it is the left iterator), and excluded in the first half (where it is the end iterator).

int sumVectorRecurse(vector<int>::iterator left, vector<int>::iterator right)
{
    if (left == right) return 0;
    if (left + 1 == right) return *left;
    int midPosition = (right - left)/2;
    vector<int>::iterator mid = left + midPosition;
    return sumVectorRecurse(left, mid) + sumVectorRecurse(mid, right);
}

这篇关于如何使用分而治之和迭代器添加所有向量元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！