Clever Geek Handbook

Split algorithm and conquer the sum of an integer array

I'm having problems with splitting and conquering algorithms and was looking for some help. I am trying to write a sumArray function that calculates the sum of an array of integers.

This function should be done by dividing the array in half and making recursive calls for each half. I tried to use similar concepts to the ones I used when writing recursive sum algorithms and a division and conquest algorithm to determine the maximum element in an array, but I am struggling to combine the two ideas.

Below is the code I wrote for sumArray that compiles but does not return the correct result.

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

I identified the problem as a function that includes the lsum value when calculating the rsum. I know the problem is my recursive call to sumArray using rsize (a variable that is equal to the size of the original array minus the midpoint). For some reason, however, I cannot find a definition.

It seems to me that I am stupidly asking, since I know that the answer is looking right in my face, but how do I restore my function so that it returns the exact result?

UPDATE: Thanks to all the helpful answers, I've corrected my code so that it compiles and works nicely. I'll leave my original code here in case others struggle with division and win and might make similar mistakes. For a function that correctly solves the problem, see @Laura M. @haris's answer also provides a good explanation of where my code was getting bugs.

+3


source to share


5 answers 


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


+8


source


In your code

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

allows you to show an example where this makes a mistake.

Let's assume the array is equal { 2, 3, 4, 5, 6, 9}

, sosize = 6

now that yo do mid = size / 2

and then



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

and the mid == (size - mid)

number is 5

added twice (once a lsum

and then a rsum

).

Further, the call sumArray()

to rsum

must have parameters sumArray(anArray + (mid + 1), --rsize)

, since the element mid

has already been added tolsum

In another post, you can find much simpler code for recursion, something like ..

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);
}
+2


source 


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;

}
0


source


As Haris said, in your code, you add the same number to both the correct amount and the left amount; however, there is a much bigger problem with your code.

You always pass the same array to your recursive calls for lsum and rsum. At first I thought this was just part of your implementation and the size parameter would take care of it. However, the size parameter doesn't work as you may have intended it to work. Your whole algorithm shrinks the size parameter until it reaches 1. Then the base case runs, and as a result, the first element in the original array is returned. What for? You never split an array in your code, and therefore the same array is preserved across all recursive calls (even in the base case).

To fix this problem, all sumarray () should be done is to split the array into left half and right half based on the average calculation and recursively pass this new array until the size of the array is 1 (base case) and you return an element in an array. This effectively splits the array into its individual elements, and all functions should be doing at this point is adding lsum and rsum.

pseudocode:

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


source 


#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


source






More articles:


All Articles