Unit 5.3 - Determining which row has the largest sum

PROG

read in a 2-D array "by row"

PED

To learn how to read in a 2-D array
"by row"
"by column"

To see stepwise refinement for a common problem in two-dimensional
arrays

CONCEPTS

to read in data "by row"

for i:=1 to norows do begin
for j:=1 to nocols do begin
read(a[i,j]);
end;
end;

to read in data "by column"

for i:=1 to nocols do begin -- i is now a column subscript
for j:=1 to norows do begin -- j is now a row subscript
read(a[j,i]);
end;
end;

STEPWISE REFINEMENT TO FIND THE ROW WITH THE LARGEST SUM

use max/min template of a set

maximum:=very small number
for each row
compute its sum
if sum>max then
max:=sum
{update position if desired}
end;
end;

Here is another example of two-dimensional arrays. It illustrates a style of code, which is explained in general in Template Six. We find the row with the largest sum.

By finding the row with the largest sum, I mean we must examine each row, compute its sum, and then by appropriate comparisons determine which row has the largest sum.

WE have seen how to sum various things in Unit Four. We will be using the template to process a row of an array as part of our code.

We also saw how to take the maximum of various things in Unit Four. And of course, our Unit 4.10 found which list had the largest sum. We will see many similarities between this program and that program.

Thus, there is much used here that should be familiar to you.

There is one thing that we will show you in this example and tempalte six, that is using the upper left-hand part of an array. Very often, we may wish to write a program where we don't know precisely how many rows or columns we will need in a given case. For example, we may wish to write a general purpose program to handle budgeting by department that can work for many different companies. The rows would represent the departments and the columns might represent the categories of expenditure, e.g., personnel, supplies, travel, etc.

Different companies would have different sets of categories and of course different departemnts. The first step would be to read in the number of rows (departments) and the number of columns (categories). The program would dimension the array or arrays with a very large number of rows and a very large number of columns. However, the calculations and input of data would only be done with the number of rows and number of columns that the user indicated he needed.

In our example, we read in the variables "norows" and "nocols" to contain the number of rows and columns actually used. We assume that the user of the program will never need more than ten rows or more than ten columns. Thus the array is dimensioned 1..10 and 1..10 of lines 3. But the number 10 is NOT used in the loops--the variables norows and nocols are used.

But before we do this, we must learn two ways to read in two-dimensional
arrays. They are "by row" and "by column" Again, these are similar to stuff we saw before. They are similar to template C and template D in the Unit 5.2.

We "process" each element of the array, we read in the number to row.

When we read in by row, that means that the input data will be arranged in such manner that the data for first row appears first in the input file. Then the second row will appear in the input data. And so on until the last row.

When the data is to be read in by column, that means that the data will be arranged such that the first column of data appears first in the data file. Then the numbers to go in the next column to the right will appear. And so on, until the rightmost column appears.

Remember, either way, the first two numbers in the input data will be the number of rows adn the number of columns.

Example, let's say we wanted to read in the array

1 2 3 4 5
7 8 9 10 11
7 2 3 4 1

This is a 3 row by 5 columns. Thus the first two numbers on the data card would be 3 and 5.

By row, the data file would be:

3 5
1 2 3 4 5
7 8 9 10 11
7 2 3 4 1

By column, the data file would be:

3 5
1 7 7
2 8 2
3 9 3
4 10 4
5 11 1

Note, that the carriage returns are optional and arbitrary. The program wouldn't care if we put all 17 numbers on a single line or we had 17 lines or anything in between.

To read in data "by row", we need the program

for i:=1 to norows do begin
for j:=1 to nocols do begin
read(a[i,j]);
end;
end;

For columns, we reverse the roles of the inner and outer loop as we saw in the previous example. The outer loop varies the subscript of the column, or the second item.

to read in data "by column"

for j:=1 to nocols do begin -- i is now a column subscript
for i:=1 to norows do begin -- j is now a row subscript
read(a[i,j]);
end;
end;

In our example program, we read in the data "by row" WE see the code to do this on lines 9 to 13 of our example program.

Now, we get to discuss the main point of this program. Once we have the data read into the 2-D array, we are supposed to determine which row has the largest sum.

We look at the logic to take the maximum of a set of numbers:

Set max to extremely small number
for each item in set
compute or obtain the next number in the set
if number>max then begin
max:=number
endif
end

If we also need the position of the number that is the maximum, then the refinement is slightly different--whenever we find a new value for the maximum, larger than the others encountered so far, we also drop the position into a separate variable. I call this maxpos. :

Set max to extremely small number
for i:=1 to NumberofItemsinSet
compute or obtain the next number in the set
if number>max then begin
max:=number
maxpos:=i
end;
end;

Let's look at our problem--we want to determine which row has the largest sum.

We substitute "compute or obtain the next number in the set" with the code to "compute the sum of the ith row" getting the pseudocode: We also replace "number" by "sum"

Set max to extremely small number
for i:=1 to NumberofItemsinSet
compute the sum of the ith row
if sum>max then begin
max:=sum
maxpos:=i
end;
end;

"compute the sum of the ith row" can be done by simply using tempalte A from Unit 5.2, substituting i for row-number.

Lines 6 to 13 read in the array by row. The main code is from line 14 to 26.

This corresponds to the above pseudocode. We use the variable "largestsum" isntead of "max" and "largestrow" instead of "maxpos" so the names are more relevant to the functions of the main code.

The expansion of the pseudocde "compute the sum of the ith row" in the above pseudocode is shown in lines 17 to 20.

And lastly, the values for largest row and largest sum are printed out after the double-nested loop on lines 27 and 28.