Unit 4.5 Learn how to Nest If's Statements and Whiles

PROG

Count the numbers in a list that are less than five.
The last number in list is -1, the sentinel value which is not included in count.

PED

To learn how to count numbers that meet a given condition.
To learn how to nest if's and whiles.

DO LOOP INVARIANT

count is the count of all the numbers in the list, except the current number, that meet the condition:
being less than five


Unit 4.5 Counting Numbers which meet a given condition

Click here to view Unit 4.5 Pascal program.

In our previous examples, we just had read, write and assignment statements as the statements between the "while do" and the "end;" of the while-end pair. This example will show a case where we nest an if statement in the while-end pair. (We will later see while loops nested in the while-end pair, i.e., nested loops.)

Our example program reads a list of numbers in a file and counts the numbers that are less than five. We frequently encounter similar problems in the real world--read in the database of all admittees to the University and count the number who have made an appointment for orientation. This is something done every Summer in order to get a feel on how many of those accepted might actually show up here.

You will recall from Unit 4.2 that the pseudocode or plan to process a set of numbers is:

get first data item into variable
while( data item not the sentinel) do begin
process the data item
get next data item into variable
end;

We get the program by replacing the term "process the data item" by an if statement that will increment count, when the data item is a number below 5: This if statement can be found in lines 19 through 21 of the program.

Recall that our do-loop invariant is:

count is the count of all the numbers in the list, except the current number, that meet the condition:
being less than five

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

If the current number is one that is less than five, count is incremented and after we read the next number, the statement is included in the next count.

Check 2: that the do loop invariant and the condition not being true implies the POSTCONDITION for the loop does what its supposed to

This part is very similar to the same reasoning in Unit 4.2.

In this case, we have from the do loop invariant that COUNT is the count of all values except the current one. If NUMBER<>-1 is not true, that means NUMBER is equal to -1. That means that we have the count of all numbers less than 5 except the -1 in variable, SUM.

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

COUNT is initially zero. NUMBER contains the first number. The set of numbers we are concerned with is all the numbers before the first number, or an empty set. The COUNT of an empty set is zero.

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.

Again, we read in a number each time through the loop. Since there are a finite numbers in the file, we will eventually read them all in.