logo标签列表

整数数组求和的分治算法

c++arraysalgorithmrecursiondivide-and-conquer
5

我在分治算法方面遇到了一些困难，需要一些帮助。我试图编写一个名为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的回答也很好地解释了我的代码出现错误的原因。
3
你是否尝试用一小组样本（比如4个项目）来测试你的程序？这是你最终应该弄清楚问题的方法（同时使用调试器逐步执行代码）。 - PaulMcKenzie
1
int lsum = anArray [mid] + sumArray(anArray, --mid); 这段代码存在未定义行为的味道。在同一序列中更改了 mid 并将其用作数组下标。 - PaulMcKenzie
@ldgorman 谢谢你提醒我！我太专注于解决问题的其他部分，以至于忘记回来接受一个答案了。 - Nea
6个回答
11
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;
}
是的，int anArray[] = { 0, 1, 2, 3, 4, 5}; //15 int size = 6; 的结果是19。 - ldgorman
我只是编辑它以在所有编译器中产生相同的输出。一开始我只在VS2012中进行了测试。 - Laura Maftei
2
这是一个非常简单明了的解决方案，解决了我遇到的问题。感谢您的答案！ - Nea
不客气，我很高兴这是你需要的解决方案。 - Laura Maftei
@LauraMaftei 是否可以创建一个递归函数，只有数组作为参数而不是数组的大小？这与我正在处理的任务非常相似。 - Alex Tănăsescu
这个解决方案的时间复杂度是多少？ - Boobalan
4
在你的代码中：
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)。

此外，在调用 rsum 中的 sumArray() 时，应该将参数设置为 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);
}
谢谢你的回答，解释非常有帮助，让我知道了我的错误所在。 - Nea
0
#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;
}
0
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;

}
1
你因为在其他人之前提供了解决方案而被投票否决，但是请注意我没有投票否决你。 - ldgorman
谢谢你的回答。我之前确实发现了解决问题的方法，但不幸的是，我后来被告知只能使用int anArray[]和int size作为参数。 - Nea
0
如haris所说，在您的代码中，您将相同的数字添加到右侧总和和左侧总和中; 但是，您的代码存在更大的问题。
您始终将相同的数组传递给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
 }
它通过此操作对数组进行拆分：anArray + mid。 - Laura Maftei
mid 不是整数吗？将整数添加到整数数组中如何分割整数数组？ - Wenqin Ye
变量anArray指向数组的第一个元素，anArray + mid将指向中间元素。 - Laura Maftei
0
int a[mx], tree[mx*3];

void sum(int node, int s, int e){
  if(s == e)
  {
     tree[node] = a[s];
     return;
  }

  int left = node*2;
  int right = node*2 + 1;
  int mid = (s+e)/2;

  sum(left, s, mid);
  sum(right, mid+1, e);

  tree[node] = tree[left] + tree[right];
}

cin >> n;
for(int i=1;i<=n;i++)
    cin >> a[i];

sum(1, 1, n);

完整代码在此处

请在您的回答中提供更多细节。目前的写法让人难以理解您的解决方案。 - Community
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接