Divide et impera sum of the elements of an array 错误

Question

我编写了以下函数，使用 divide et impera 方法计算向量中所有元素的总和

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）。在这种情况下，您想要 return 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);

你会看到需要多长时间

Divide et impera sum of the elements of an array 错误

Divide et impera sum of the elements of an array bug

c++

recursion

divide-and-conquer