vendredi 6 mars 2015

How to add all vector elements using divide and conquer and iterators?


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;
}



Aucun commentaire:

Enregistrer un commentaire