Divide et impera sum of the elements of an array bug

Question

我编写了以下函数来使用除法计算向量中所有元素的总和

int Sum(std::vector<int> v, int left, int right)
{
int mid = (left + right) / 2;
if (left >= right)
return v[mid];
else
return Sum(v, left, mid - 1) + Sum(v, mid + 1, right);
}
//in main:
vector <int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
cout << Sum(v, 0, v.size() - 1);

但是，在给定的示例中，它输出 37 而不是 55。我用调试器完成了它，它似乎跳过了某些数字。我尝试将left >= right更改为left > right，它仍然给了我一个错误的答案(56(，尽管我认为从逻辑上讲应该是left => right。

代码中有什么问题？

Answer 1

主要问题：递归将mid排除在两个子和之外。

次要问题：可能会发生left>right(尽管有合理的初始输入，最坏的情况是left == right + 1(。在这种情况下，您要返回0.

所以也许

if ( left > right ) 
return 0;
else
return Sum(v, left, mid-1) + v[mid] + Sum(v, mid+1, right);

Answer 2

错误在这里，

return Sum(v, left, mid - 1) + Sum(v, mid + 1, right);

您缺少添加v[mid]。所以，改变它，

if (left >= right)
return v[left]; // v[mid] also helps.
return Sum(v, left, mid) + Sum(v, mid + 1, right);

Answer 3

Sum应该是这样的：

int Sum(const std::vector<int>& v, int left, int right)  // pass vector by const reference
{
int mid = (left + right) / 2;
if (left == right)  // there's no need to check whether left > right
// if you call function with left <= right
return v[mid];
else
return Sum(v, left, mid) + Sum(v, mid + 1, right);  // you have missed mid
}

在你的版本中，你也在递归期间复制向量，尝试像这样调用你的函数：

std::vector<int> v(100'000, 1);  // digit separator comes since C++14
Sum(v, 0, v.size() - 1); 

你会看到需要多长时间