对整数数组之和进行划分和征服算法

Question

我在分治算法方面遇到了一些麻烦，并且正在寻求一些帮助。我正在尝试编写一个名为sumArray的函数来计算整数数组的总和。

此函数必须通过将数组分成两半并在每一半上执行递归调用来完成。我尝试使用类似的概念来编写递归求和算法时使用的概念，以及用于识别数组中最大元素的分而治之算法，但我正在努力将这两个想法结合起来。

下面是我为sumArray编写的代码，它编译但不返回正确的结果。

int sumArray(int anArray[], int size)
{
    int total = 0;
    //base case
    if (size == 0)
    {
        return 0;
    }
    else if (size == 1)
    {
        return anArray[0];
    }

    //divide and conquer
    int mid = size / 2;
    int lsum = anArray [mid] + sumArray(anArray, --mid);
    int rsize = size - mid;
    int rsum = anArray[size - mid] + sumArray(anArray + mid, --rsize);
    return lsum + rsum;
}

我已经将问题确定为函数在计算rsum时包含lsum的值。我知道问题在于我使用rsize对sumArray的递归调用（一个等于原始数组大小的变量，减去中点）。但是，出于某种原因，我似乎无法确定修复方法。

我觉得很傻，因为我知道答案是正确地盯着我，但是我如何修复我的功能以便它返回准确的结果呢？

更新：感谢所有有用的响应，我已修复我的代码，以便它编译和运行良好。我会留下我原来的代码，以防其他人在分裂和征服中挣扎，并可能犯同样的错误。有关正确解决问题的函数，请参阅@Laura M的答案。 @haris的回复也很好地解释了我的代码出现错误的地方。

Answer 1

int sumArray(int anArray[], int size)
{
    //base case
    if (size == 0)
    {
        return 0;
    }
    else if (size == 1)
    {
        return anArray[0];
    }

    //divide and conquer
    int mid = size / 2;
    int rsize = size - mid;
    int lsum = sumArray(anArray, mid);
    int rsum = sumArray(anArray + mid, rsize);
    return lsum + rsum;
}

Answer 2

在你的代码中：

int mid = size / 2;
int lsum = anArray [mid] + sumArray(anArray, --mid);
int rsize = size - mid;
int rsum = anArray[size - mid] + sumArray(anArray + mid, --rsize);

我们可以用一个例子来说明错误，其中数组是{ 2, 3, 4, 5, 6, 9}和size = 6。

现在当你做mid = size / 2，然后：

int lsum = anArray [mid] + sumArray(anArray, --mid);
int rsize = size - mid;
int rsum = anArray[size - mid] + sumArray(anArray + mid, --rsize);

5加上两次（一次在lsum然后在rsum）加上mid == (size - mid)。

此外，sumArray()中对rsum的调用应该有参数sumArray(anArray + (mid + 1), --rsize)，因为元素mid已经添加到lsum

另一方面，您可以使用更简单的递归代码，例如..

int add(int low,int high,int *a)
{
    int mid;
    if(high==low)
        return a[low];
    mid=(low+high)/2;
    return add(low,mid,a)+add(mid+1,high,a);
}

Answer 3

int sumArray(int anArray[],int start,int end){
     if(start==end)
        return anArray[start];
     if(start<end){
         int mid=(start+end)/2;
         int lsum=sumArray(anArray,start,mid-1);
         int rsum=sumArray(anArray,mid+1,end);
         return lsum+rsum+anArray[mid];

     }
     return 0;

}

Answer 4

正如哈里斯所说，在你的代码中你将相同的数字添加到正和和左和;但是，您的代码存在更大的问题。

您总是将相同的数组传递给lsum和rsum的递归调用。起初我认为这只是您实现的一部分，并且它将由size参数处理。但是，size参数似乎不起作用，因为您可能希望它起作用。您的所有算法都会减小size参数，直到达到1.然后，触发基本情况，结果始终返回原始数组中的第一个项目。为什么？您永远不会在代码中拆分数组，因此在每次递归调用中都会保留相同的数组（即使在基本情况下也是如此）。

要解决这个问题，所有sumarray（）应该做的是根据mid计算将数组拆分为左半部分和右半部分，并递归传递这个新数组，直到数组的大小为1（基本情况）并返回数组中的项目。这有效地将数组分解为其各个元素，此时所有函数必须将lsum和rsum相加。

伪代码：

sumArray(array[]){
    if size(array) is 1
          return array[0]

    mid = size(array) / 2 
    leftArray = splitArrayUpto(mid, array)
    rightArray = splitArrayAfter(mid+1, array)

    leftArraySum = sumArray(leftArray)
    rightArraySum = sumArray(rightArray)

    return leftArraySum + rightArraySum
 }   

Answer 5

#include<iostream>
using namespace std;
int sum(int a[], int l, int r)
{
    if(l==r) return a[l];
    int mid = (l+r)/2;
    int lsum = sum(a,l,mid);
    int rsum = sum(a,mid+1,r);
    return lsum+rsum;
}

int main() {
    int b[] = {9,7,2,6,5,3};
    int fsum = sum(b,0,5);
    cout<<fsum;
    return 0;
}