PROG
Take the minimum of a set of numbers
The last number in list is -1, the sentinel value which is not included in
count.
PED
To learn how to take the minimum of a set of numbers.
To see another example of nesting if's and whiles.
DO LOOP INVARIANT
min is the minimum of all numbers in the list, except the current number,
Click here to view Unit 4.6 Pascal program.
Taking the minimum (or maximum) of a set of numbers is a common operation in programming. Think of figuring out which student has the highest GPA in a high school to give them the Valedictorian award. Or one might want to find out the city with the highest and lowest temperature on a given day for mention in the weather report section of a news program.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 saw an example of this previously in Unit 4.2 and in Unit 4.4A.
We get the program by replacing the term "process the data item" by the code to compare the current data with minimum. If this value is less than minimum, then obviously the minimum of all the numbers so far is that number.
There is a question of initializing the value of "min" What is the "min" of a set of zero numbers? There is no real answer to this. The solution in this example, is to pick some very large number. As long as the minimum is smaller than that number, our program will work. We pick 1000 in our example. Should all the numbers in our set be greater than 1000, our program will not work--it would report 1000, not the true minimum.
Recall that our do-loop invariant is:
min is the minimum of all numbers in the list, except the current number,
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 less than the minimum, then the if statement will set the if statement equal to the current number. If the current number is greater than the minimum so far, then the current number cannot be the minimum--in this case, the if statement will not execute.
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 MIN 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 minimum of all numbers less than 5 except the -1 in variable, MIN.
Check 3: that the do loop invariant is initially true.
We are assuming that MIN is equal to 1000. We are assuming that there are no numbers in the list are bigger than 1000 in the data list.
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.