PROG

Read in a list of lists.
Determine the sum of each of the lists, and print out the largest sum.
Each list ends with -1
After the -1 of last list, a -2 will appear to signal the end of all
the lists.

PED

To learn more about nesting do loops.
To see another example of stepwise refinement.

DO LOOP INVARIANT

Outer do loop
number contains the first number of the next list to be processed
(or the -2)
maxsum is the maximum of all the sums except the list about to be read

Inner do loop
sum is the sum of all numbers in the current list before the one in the
number

Click here to view Unit 4.10 Pascal program.

We have a series of lists, each list following the previous list. Each list ends in a -1 which signals that this list is ended and that probably a new list will follow. In the case of the last list, a -2 will follow which will indicate that there are no more lists. Thus, we have two types of sentinels, the -1, which signals the end of a single list and a -2 which signals the end of multiple lists. An example of the input data is:

2 3 -1
1 1 1 1 1 1 -1
2 2 1 -1
-2

The three lists are (2,3) (1,1,1,1,1,1) and (2,2,1). Their sums are 5,6, and 5. The largest sum would be 3.

We are going to use two plans. The outer do loop will follow the plan from Unit 4.5 which is taking the minimum of a set of numbers. When it is time to compute a new number, we execute a do loop to read in the next list computing the sum as we go along.

Thus, our stepwise refinement looks as follows:

while (we haven't processed thelast list)
compute the sum of the current list
if that sum is greater than the maximum sum so far
set "maximum sum so far" to that sum
endif
end

LInes 14 to 17 "compute the sum of the current list" This code should be very familiar to you--it is practically a copy of Unit 4.2's program. You will recall that we must insrue that "sum is the sum of all mnumbers in the current current list before the one in number." Thus we must insure that number contains the first number of the list being processed. Note that this is in the do loop invariant of the outer do loop, so we know that we msut insure that this always true at the w in the while on line 12.

Let's look at the do loop invariant for the outer loop since that is new. We must:

number contains the first number of the next list to be processed
(or the -2)
maxsum is the maximum of all the sums except the list about to be read

Check 1: that the do loop invariant and the condition being true implies that executing the statements leaves the do loop invariant true

The loop from lines 14 to 17 will leave number containing the value of -1 at the end of the loop. It also leaves sum containing the sum of the current list. Liens 18 to 20 will make maxsum reflect the maximum of this list. Then when we do the read at line 21, we make sure that number contains the first number after the -1 in the last loop.

Check 2: that the do loop invariant and the condition not being true implies the POSTCONDITION for the loop

When number is equal to -2, that means we have computed the maximum of all the sums before this -2 which by definition of the input format is all the sums.

Check 3: that the do loop invariant is initially true.

WE did the fudge on line 11 to set maxsum to a sufficiently small number that at least one list will have a larger sum. In addition, we read the first number in.

Check 4: that executing the statements once makes progress towards the goal. Since each read statement removes a number from the file and advances us toward the end of what must be a finite set, then the statement makes progress.

Each time through the loop, reads some numbers off the input, specifically one
list worth.

Some questions for thought:

See for yourself by executing the program by hand what happens when the there are several empty lists, i.e., you have several -1's in succession?

See for yourself what happens when there are no lists at all, i.e., the input consists of a single -2?

What would the program do if we deleted line 21 by mistake?

How would we change the program if we wanted to comptue the list with the largest average.

How would we change the program if we decided to end the last list with a single -2. INother words, what would happen if we changed the input format so that the last number was a -2 instead of the last two numbers being -1 which would be followed by a -2?