Thread: Output matrix containing sum of elements above and to the left of an input matrix

I have the following question that I'm having trouble with. I need write a code that defines some 2D array NxN that gets a number n (n can't be larger than N) which then defines a matrix nxn (starting from the 0,0 element to n,n) that I provide its elements. Then, the following calculation is done on the (i,j) cell and is placed in the (i,j) cell of another 2D array (which includes the output) of size nxn as well: For every (i,j) in the input sub-matrix (nxn), I need write the average of all the cells above and to the left of the current cell including it and place it in (i,j) of the output matrix. For example, if n=3 and the input sub-matrix is 15 13 0 14 2 9 -3 12 -16 The output is 15.00 14.00 9.33 14.50 11.00 8.83 8.67 8.83 5.11 I was successful with the (0,j) (i,0) cells of the output matrix but in the rest (when both i and j arent 0) I'm always missing the cells that are diagonal to the one I'm looking at or more. This is a part of the code I've written that includes the calculations and the output matrix: Code: for(i=0;i<n;i++) { for(j=0;j<n;j++) { sum=a[0][0]; cells=1; if( i==0&& j>0) { for(k=1;k<=j;k++) { sum+=a[i][k]; cells++; } } if( i>0&& j==0) { for(k=1;k<=i;k++) { sum+=a[k][j]; cells++; } } if( i>0&& j>0) { } b[i][j]=sum/cells; } } printf("Result matrix:\n"); for(i =0; i < n; i++){ for(j =0; j < n; j++){ printf("%d ", b[i][j]); } printf("\n"); } I left the last if condition empty on purpose as my attempts failed. I apologize in advance if something isn't clear. I will make sure to explain better if someone got lost in my explanation. Any help would be much appreciated. Thank you.

You shouldn't be dividing your logic into cases like that. It's unnecessary.

Inside your first double loop you need another double loop that only goes up to (and including) the current element. Sum those elements up and divide by the number of elements (which don't need to be counted since the number can be calculated).

That's not the most efficient algorithm since it repeats work, but it will do the job.

First off thanks for the reply.
So you're saying that something like

Code:

for(i=0;i<n;i++)
{
    for(j=0;j<n;j++)
        {
            for(k=0;k<=i;k++)
            {
                for(q=0;q<=j;q++)
                {
                    sum+=a[k][q];
                }
            }
            cells=(i+1)*(j+1);
            }
            b[i][j]=sum/cells;
}

Would work?

Looks pretty good. Give it a go. Remember that you need to zero sum before the inner double loop.

Originally Posted by algorism

Looks pretty good. Give it a go. Remember that you need to zero sum before the inner double loop.

I will try this in a second and come back with an answer. Thank you algorism!

You should be more specific instead of just saying that it doesn't work. You should also post a complete program. The way it is, I can't tell what sum or a or b are. I assumed they were doubles (or at least floats). Obviously b must be a double or float since the output you show has a fractional part. Since b must be double or float, you can't print it with "%d", which is for ints. Instead, you must use "%f".

Also, why are the cells calculation and b[i][j] calculation in completely different positions relative to the loops? They should both be where the cells calculation is.

I've just noticed your reply, it didn't show at first. I used int on purpose since when I first tried it with double it gave me extremely large numbers for some reason so I kept working with int remembering that it gives only the integer part of the number. Now, I've received the correct integer part and I'm switching it to double.

I feel I should reiterate that the simple algorithm I described (and you implemented) is of complexity order n to the fourth power. But it is possible to write one that is more like n squared. I wrote this up and for a 100x100 array it was about 300 times faster on my system. For a 300x300 array, it was about 3000 times faster. So if you're looking for efficiency, the simple algorithm is not the way to go.

That is not of concern here as N is very small compared to the examples you nxn you just presented. We're talking here about a single digit N.

Are there any active mods on this forum?