Unit 4.11 Flag Variables

PROG

Read in a list of numbers beginning with -1.
Sum all those numbers between the first two and the first five after that.
Do not include either the "two" or the "five" in the sum.

PED

To learn about state variables.

CONCEPT

state table
2 5
0 --------> 1 --------> 2

if (state = m1) and (input = n1) then
end
else
if (state=m2) and (input = n2) then
.
OR
if (state = m) then

m -- represents the number in the state variable
n -- represents possible value of the input

DO LOOP INVARIANT

state=0 -> first one is not found yet
state=1 -> first one is found but first five is not 

         sum is the sum of all numbers after first one up to but not
         including the first one.
state=2 -> first five after the first one is found

Unit 4.11 Flag and List Variables

Click here to view Unit 4.11 Pascal program.

Our sample problem is to go through a list of numbers. We want a sum. But we want a sum of the subset of numbers defined as follows. We want to start summing with the first number we encounter after the first one. We should keep on summing until the first five is encountered.

When we encounter an arbitrary number in the list, we need to know where we are in the list. We need to know Did we encounter the first two yet? If so, we add the number to the sum, except that we need to check Did we encounter the five after the two yet? If we did, then we don't add to the sum variable.

The way we answer that question is by keeping flag variables. A common way to think about this sort of problem is as a state table. We saw a diagram of one on the transparency. We have three states corresponding to: 

0:    waiting for the first two
1:    summing away until the five is found
2:    end of data to sum for
The arrows represent transitions from one state to another. If we are in a state zero to state one, when a two is encountered. If we are in state one, there are two possibilities. In line 13, we check that we are in state one and we have an ordinary number. We just add that. On line 17, we have the transition to state two. We go through the numbers as long as we are in state two until the -1 sentinel is encountered. (Actually, given the definition of the problem, we could simply stop the loop when state two is reached, but I want to show a more general solution.)

The basic idea is to identify each combination of a state and an input and perform whatever actions are required, e.g., adding a number to sum, as well whatever state transitions are implied by the arrows.