Sum of consecutive elements in an array, C++

问题:

Suppose that I have an array consisting of n elements.

1 2 3 4 5 6 ... n

I need to find a way to extract the sums of consecutive elements in this array using C++. Like this:

1, 2, 3,...n, 1+2, 2+3, 3+4,...(n-1)+n, 1+2+3, 2+3+4,...(n-2)+(n-1)+n,...1+2+3...n

So far I figured out I need to iterate through this array by summing certain number of elements on each run. I am not sure if it is possible to implement the algorithm I explained above. There might be a better solution but this is the best I could come up with.

回答1:

Let's inspect case with 4 elements:

{1,3,4,5, // from original array
 4,7,9, // sum of 2 consecutive elements
 8,12, // sum of 3
 13} // sum of 4

As you can see every part for N sum array is of size lower from original array by (N-1). So you need target array of size: N + (N-1) + (N-2) + ... 1 - which is N*(1+N)/2

int* createSumArray(int* arr, int size)
{
   int ti = 0; // target index
   int* ta = new int[size*(size+1)/2];
   for (int s = 1; s <= size; ++s) // how many elements to sum
   {
      for (int si = 0; si < size + 1 - s; ++si)
      {
          ta[ti] = 0;
          for (int i = si; i < si + s; ++i)
            ta[ti] += arr[i];
          ++ti;
      } 
   }
   return ta;
}

See test on ideone

回答2:

You can use std::transform to do this:

std::transform(
    v.begin(), v.end()-1,
    v.begin()+1,
    std::ostream_iterator<int>(std::cout, "\n"),
    std::plus<int>()
);

Of course you don't have to use an ostream_iterator as it's output, you can also use another containers iterator, or a std::back_inserter for a container or any other OutputIterator

references

http://en.cppreference.com/w/cpp/algorithm/transform

http://en.cppreference.com/w/cpp/utility/functional/plus

http://en.cppreference.com/w/cpp/container/vector

EDIT:

std::vector<int> v(100), t;
//this just populates v with 1,2,3...100
std::iota(v.begin(), v.end(), 1);

std::transform(
    v.begin(), v.end()-1, v.begin()+1,
    std::back_inserter(t),
    std::plus<int>()
);

std::transform(
    t.begin(), t.end()-1, v.begin()+2,                
    std::ostream_iterator<int>(std::cout, "\n"),
    std::plus<int>()
);

回答3:

How this. Given an array of 5 integers : 5, 7, 3, 9, 4

    void DoMaths (void)
    {
         int       iArray [] = { 5, 7, 3, 9, 4 } ;
         int       iSize = 5 ;

         int       iGroup ;
         int       iIndex ;
         int       iPass ;
         int       iResults ;
         int       iStart ;
         int       iSum ;

    // Init
         iGroup   = 1 ;
         iResults = iSize ;
    // Repeat for each pass
         for (iPass = 0 ; iPass < iSize ; iPass ++)
         {
              printf ("\n") ;
              printf ("Pass %d : Group %d :\n", iPass, iGroup) ;
         // Repeat for each group of integers in a pass
              for (iStart = 0 ; iStart < iResults ; iStart ++)
              {
                   iSum = 0 ;
                   printf ("  %d [ ", iStart) ;
                   for (iIndex = iStart ; iIndex < (iStart + iGroup) ; iIndex ++)
                   {
                        printf ("%d ", iIndex) ;
                        iSum += iArray [iIndex] ;
                   }
                   printf ("] sum = %d \n", iSum) ;
              }
              iGroup ++ ;
              iResults -- ;
         }
         return ;
    }

This produces the following results...

    Pass 0 : Group 1 :
      0 [ 0 ] sum = 5
      1 [ 1 ] sum = 7
      2 [ 2 ] sum = 3
      3 [ 3 ] sum = 9
      4 [ 4 ] sum = 4

    Pass 1 : Group 2 :
      0 [ 0 1 ] sum = 12
      1 [ 1 2 ] sum = 10
      2 [ 2 3 ] sum = 12
      3 [ 3 4 ] sum = 13

    Pass 2 : Group 3 :
      0 [ 0 1 2 ] sum = 15
      1 [ 1 2 3 ] sum = 19
      2 [ 2 3 4 ] sum = 16

    Pass 3 : Group 4 :
      0 [ 0 1 2 3 ] sum = 24
      1 [ 1 2 3 4 ] sum = 23

    Pass 4 : Group 5 :
      0 [ 0 1 2 3 4 ] sum = 28

I hope this helps...

回答4:

I think this code should do what you are asking for:

int main()
{
    int ptr=0,i,j,k;
    int Ar[]={1,2,3,4,5,6,7,8,9,10,11,12,13};
    int n=13;
    int *Res;
    Res=(int*)calloc(n*(n+1)/2,sizeof(int));
    for(i=1;i<=n;i++) //tells about how many element's sum we need
    for(j=i;j<=n;j++)
    {
        for(k=0;k<i;k++)
        {      
               Res[ptr]+=Ar[j-i+k];
        }
        ptr++;
    }
    for(int x=0;x<ptr;x++)
    cout<<Res[x]<<"\t";
    return 0;
}

回答5:

Let's call the original array A.

Let's call the array of sums of k consecutive elements B.

Let's call the array of sums of k+1 consecutive elements C.

Each of the array is of size n.

First k-2 cells of C are irrelevant.

for(int i = k-1; i < n; i++)
    C[i] = A[i-1] + B[i];

Iterate the above code for each k up to n and after each pass concatenate the resulting array to the result from previous iteration. (Make sure to check the corner cases well)

回答6:

See it working at ideone.com:

std::vector<std::vector<int> > sums(int array[], int size)
{
        std::vector<std::vector<int> > result(size - 1);
        //build the two element sums
        for(int *p = array; p - array < size - 1; ++p)
                result[0].push_back(std::accumulate(p, p + 2, 0));
        //build the rest of the sums
        for(int i = 1; i < size - 1; ++i)
                for(int j = 0; j < size - (i + 1); ++j)
                        result[i].push_back(result[i - 1][j] + array[i + j + 1]);
        return result;
}

This should use the previously calculated sums too.