It is one thing to be able to analyze the operation of loops like those in Programs 6.1 through 6.4 and another to design our own loops. We will attack this problem in two ways. One approach is to analyze the requirements for a new loop to determine what initialization, test, and update of the loop control variable are needed. A second approach is to develop templates for loop forms that frequently recur and to use a template as the basis for a new loop. We will discuss loop templates later in this section.
To gain some insight into the design of the loop needed for the worm and apple problem, we should study the comment in Program 6.3 that summarizes the goal of this loop:
-- Cut the distance between the worm and the apple by the worm's
-- body length until the worm is close enough to bite the apple
In
order to accomplish this goal, we must concern ourselves with loop control and
loop processing. Loop control involves making sure that loop exit occurs when
it is supposed to; loop processing involves making sure the loop body performs
the required operations.
To help us formulate the necessary loop control and loop processing steps, it
is useful to list what we know about the loop. In this example, if
Distance is the distance of the worm from the apple, we can make
the following observations:
Distance must be equal to
InitialDist.
Distance must be less than the value of
Distance during pass i - 1 by the length of the worm (for
i > 1).
Distance must be between 0 and the
worm's body length . InitialDist is the starting distance of the worm from the apple.
Statement 2 says that the distance of the worm from the apple must be cut by
the worm's body length during each iteration. Statement 3 derives from the fact
that the worm enters the apple when Distance <=
WormLength. Distance cannot be less than
WormLength after loop exit; if it were, loop exit should have occurred
at the end of an earlier pass.
Statement 1 by itself tells us what initialization must be performed.
Statement 2 tells us how to process Distance within the loop body
(i.e., reduce it by the worm's length). Finally, statement 3 tells us when to
exit the loop. Because Distance is decreasing, loop exit should
occur when Distance <= WormLength is true. These considerations
give us the outline below, which is the basis for the WHILE loop
shown in Program 6.3. The loop repetition condition, Distance >
WormLength, is the opposite of the exit condition, Distance <=
WormLength.
1. Initialize Distance to InitialDist
2. WHILE Distance > WormLength LOOP
3. Display Distance
4. Reduce Distance by WormLength
END LOOP;
Your little cousin is learning the binary number system and has asked
you to write a program that displays all powers of 2 that are less than a
certain value (say 10000). Assuming that each power of
2 is stored in the variable Power, we can make the
following observations about the loop:
1. Power during pass i is 2 times
Power during pass i - 1 (for i > 1) .
2. Power must be between 10,000 and 20,000 just after loop exit.
Statement 1 derives from the fact that the powers of a number 2
are all multiples of 2. Statement 2 derives from the fact that
only powers less than 10000 are displayed. From statement 1 we
know that Power must be multiplied by 2 in the loop
body. From statement 2 we know that the loop exit condition is Power
>= 10000, so the loop repetition condition is Power <
10000. These considerations lead us to the following outline:
1. Initialize Power to ___
2. WHILE Power < 10000 LOOP
3. Display Power
4. Multiply Power by 2
END LOOP;
One way to complete step 1 is to ask what value should be displayed during the
first loop repetition. The value of N raised to the power 0 is 1
for any number N; specifically, 20 is 1. Therefore, if
we initialize Power to 1, the value displayed during
the first loop repetition will be correct.
1. Initialize Power to 1
The body of a WHILE loop is not executed if the loop
repetition test fails (evaluates to false) when it is first reached. To verify
that you have the initialization steps correct, you should make sure that a
program still generates the correct results for zero iterations of the loop
body. If WormLength is greater than or equal to the value read
into InitialDist (say, 2.5), the loop body in Program
6.3 would not execute, and the lines below would be correctly displayed:
Enter the initial distance between worm and apple: 2.5 The final distance between the worm and the apple is 2.5 The worm bites the apple.
Very often we do not know exactly how many data items will be entered before a program begins execution. This may be because there are too many data items to count them beforehand (e.g., a stack of exam scores for a very large class) or because the number of data items provided may depend on how the computation proceeds.
There are two ways to handle this situation using a WHILE loop.
One approach is to ask whether there are any more data before each data item is
read. The user should enter Y (for yes) or N (for
no), and the program would either read the next item (Y) or
terminate data entry (N). The Y/N variable is
sometimes known as a flag. The other way is to terminate data entry when
a particular value occurs in the data. This value is often called a
sentinel: It comes at the end of the data.
Let us use this approach to design a loop that accumulates the sum
(in Sum) of a collection of exam scores. The statements below are
true assuming that MoreData always contains the value
'Y' or 'N'.
1. Sum is the sum of all scores read so far.
2. MoreData is 'N' just after loop exit.
From statement 1 we know that we must add each score to Sum in the
loop body and that Sum must initially be 0 in order for its final
value to be correct. From statement 2 we know that loop exit must occur when
MoreData is 'N' so the loop repetition condition is
MoreData = 'Y'. These considerations lead us to the loop form
below:
1. Initialize Sum to 0
2. Initialize MoreData to ___
3. WHILE MoreData = 'Y' LOOP
4. Read the next score into Score
5. Add Score to Sum
6. Read the next value of MoreData
END LOOP;
The loop repetition condition, MoreData = 'Y', derives from the
fact that MoreData is either 'Y' or 'N',
and loop exit occurs when MoreData is 'N'. To ensure
that at least one pass is performed, step 2 should be
2. Initialize MoreData to 'Y'
In the Ada loop below, the value of the type Character variable
MoreData controls loop repetition. It must be initialized to
'Y' before the loop is reached. A new character value
('Y' or 'N') is read into MoreData at
the end of each loop repetition. The loop processing consists of reading each
exam score (into Score) and adding it to Sum. Loop
exit occurs when the value read into MoreData is not equal to
'Y'.
Sum := 0;
MoreData := 'Y';
WHILE MoreData = 'Y' LOOP
Ada.Text_IO. Put (Item => "Enter the next score > ");
Ada.Integer_Text_IO.Get (Item => Score);
Ada.Text_IO.New_Line;
Sum := Sum + Score;
Ada.Text_IO.Put (Item => "Any more data? Enter Y (Yes) or N (No) > ");
Ada.Text_IO.Get (Item => MoreData);
END LOOP;
The sample dialogue below would be used to enter the scores
33, 55, and 77. The problem with this
approach is that the program user must enter an extra character value,
Y, before each actual data item is entered.
Enter the next score > 33 Any more data? Enter Y (Yes) or N (No) > Y Enter next data item > 55 Any more data? Enter Y (Yes) or N (No) > Y Enter next data item: 77 Any more data? Enter Y (Yes) or N (No) > N
The general form of the loop just seen can be used to write other loops as the need arises. This general form is
1. Initialize flag variable to its affirmative value
2. WHILE flag variable is still false LOOP
...
Read new value of flag variable
END LOOP;
A second approach to solving the problem addressed in the last section would be to instruct the user to enter a unique data value, or sentinel value, when done. The program would test each data item and terminate when this sentinel value is read. The sentinel value should be carefully chosen and must be a value that could not normally occur as data. This approach is more convenient because the program user enters only the required data.
The statements below must be true for a sentinel-controlled loop that accumulates the sum of a collection of exam scores.
1. Sum is the sum of all scores read so far.
2. Score contains the sentinel value just after loop exit.
Statement 2 derives from the fact that loop exit occurs after the sentinel
is read into Score. These statements lead to the following trial
loop form:
Incorrect sentinel-controlled loop
1. Initialize Sum to 0
2. Initialize Score to ________
3. WHILE Score is not the sentinel
LOOP
4. Read the next score into Score
5. Add Score to Sum
END LOOP;
Because Score has not been given an initial value, the
WHILE condition in step 2 cannot be evaluated when the loop is
first reached. One way around this would be to initialize Score to
any value other than the sentinel (in step 2) and then read in the first score
at step 3. A preferred solution is to read in the first score as the initial
value of Score before the loop is reached and then switch the
order of the read and add steps in the loop body. The outline for this solution
is shown below.
Correct sentinel-controlled loop
1. Initialize Sum to 0
2. Read the first score into Score
3. WHILE Score is not the sentinel LOOP
4. Add Score to Sum
5. Read the next score into Score
END LOOP;
Step 2 reads in the first score, and step 4 adds this score to 0 (initial value
of Sum). Step 5 reads all remaining scores, including the
sentinel. Step 4 adds all scores except the sentinel to Sum. The
initial read (step 2) is often called the priming read, to draw an
analogy with an old hand-operated water pump which must be primed by pouring a
cup of water into it before it can begin to pump water out of a well. The Ada
implementation shown below uses -1 (value of Sentinel) as the
sentinel because all normal exam scores will be nonnegative:
Sum := 0;
Ada.Text_IO.Put (Item => "When done, enter -1 to stop.");
Ada.Text_IO.New_Line;
Ada.Text_IO.Put (Item => "Enter the first score > ");
Ada.Integer_Text_IO.Get (Item => Score);
Ada.Text_IO.New_Line;
WHILE Score /= Sentinel LOOP
Sum := Sum + Score;
Ada.Text_IO.Put (Item => "Enter the next score > ");
Ada.Integer_Text_IO.Get (Item => Score);
Ada.Text_IO.New_Line;
END LOOP;
Although it may look strange at first to see the statement
Ada.Integer_Text_IO.Get (Item => Score);
at two different points in the program, this is a perfectly
good programming practice and causes no problems. Note that Score
must be Integer, not Natural, because the sentinel
value is negative. The following sample dialogue would be used to enter the
scores 33, 55, and 77. Compare this with
the dialogue shown in Example 6.7.
When done, enter -1 to stop. Enter the first score > 33 Enter the next score > 55 Enter the next score > 77 Enter the next score > -1 The sum of the scores is 165.
It is usually instructive (and often necessary) to question
what happens when there are no data items to process. In this case, the
sentinel value should be entered as the "first score," and loop exit would
occur right after the first (and only) test of the loop repetition condition so
the loop body would not be executed (i.e., a loop with zero iterations).
Sum would retain its initial value of 0, which would be correct.
Sentinel-controlled loops have the general form shown next.
1. Read the first value of input variable
2. WHILE input variable is not equal to the sentinel
LOOP
. . .
Read the next value of input variable
END LOOP;
The sentinel value must be a value that would not be entered as a normal data item. For program readability, we usually store the sentinel value in a constant.
In some situations it is necessary to remember the data value
processed during the previous iteration of a loop. For example, some keyboards
are "bouncy" and cause multiple occurrences of the same character to be sent
when a single key is pressed. Some faculty are forgetful and may enter the same
exam score twice in succession. An IF statement nested inside a
loop can be used to check whether or not the current data value is the same as
the last data value.
Example 6.9
Program
6.5 finds the product of a collection of data values. If there are multiple
consecutive occurrences of the same data value, only the first occurrence is
included in the product. For example, the product of the numbers 10, 5, 5, 5,
and 10 is 10 x 5 x 10, or 500. Assuming a new data value is read into
NextNum during each loop iteration, we can make the following
observations.
1. Product in pass i is the same as Product
in pass i - 1 if NextNum in pass i is
NextNum in pass i - 1; otherwise, Product
during pass i is NextNum times Product in pass
i - 1 (for i > 1).
2. NextNum is the sentinel just after loop exit.
Statement 1 requires the loop to "remember" the value read into
NextNum during the previous iteration. We will introduce a new
program variable, PreviousNum, for this purpose. The current value
of NextNum should be incorporated in the product only if it is
different from the previous value of NextNum (saved in
PreviousNum). A trial loop form follows.
Initial loop form
1. Initialize Product to ____
2. Initialize PreviousNum to ____
3. Read the first number into NextNum
4. WHILE NextNum is not the sentinel LOOP
5. IF NextNum is not equal to PreviousNum THEN
6.Multiply Product by NextNum
END IF;
7. Set PreviousNum to NextNum
8. Read the next number into NextNum
END LOOP;
For Product to be correct during the first pass, it must be
initialized to 1 (step 1). We must also initialize PreviousNum so
that the condition in step 4 can be evaluated. To ensure that the first number
read into NextNum is incorporated in the product, we must pick a
value for PreviousNum that is different from the initial data
value. The safest thing to do is to initialize PreviousNum to the
sentinel. (Why?) These considerations lead to the following revised loop form.
Revised loop form
1. Initialize Product to 1
2. Initialize PreviousNum to the sentinel
3. Read the first number into NextNum
4. WHILE NextNum is not the sentinel LOOP
5. IF NextNum is not equal to PreviousNum THEN
6. Multiply Product by NextNum
END IF;
7. Set PreviousNum to NextNum
8. Read the next number into NextNum
END LOOP;
Within the loop, steps 7 and 8 prepare for the next iteration by saving the
previous value of NextNum in PreviousNum before
reading the next data value. (What would happen if the order of these two steps
were reversed?)
Program
6.5
illustrates the proper form of a sentinel-controlled loop. The constant
Sentinel has the value 0 because it is meaningless to include 0 in
a collection of numbers being multiplied. To determine whether or not to
execute the loop, each value read into NextNum must be compared to
Sentinel. In order for this test to make sense in the beginning,
the first data value must be read before the WHILE loop is
reached. The next value must be read at the end of the loop so that it can be
tested before starting another iteration.
Program 6.5
WITH Ada.Text_IO;
WITH Ada.Integer_Text_IO;
PROCEDURE Multiply_Integers IS
------------------------------------------------------------------------
--| Finds the product of a collection of non-zero integers. If there
--| are multiple consecutive occurrences of the same value, only the
--| the first value is included in the product.
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: July 1995
------------------------------------------------------------------------
Sentinel : CONSTANT Natural := 0; -- sentinel value
NextNum : Integer; -- input - new data item
PreviousNum : Integer; -- save previous data item
Product : Integer; -- output - product of data
BEGIN -- Multiply_Integers
Product := 1;
PreviousNum := Sentinel;
Ada.Text_IO.Put (Item => "Enter 0 to stop.");
Ada.Text_IO.New_Line;
Ada.Text_IO.Put (Item => "Enter first number > ");
Ada.Integer_Text_IO.Get (Item => NextNum); -- priming read
WHILE NextNum /= Sentinel LOOP
-- invariant:
-- No prior value of NextNum is the sentinel and
-- Product in pass i is Product in pass i-1 if NextNum is
-- PreviousNum; otherwise, Product in pass i is NextNum * Product
-- in pass i-1 (for i > 1)
IF NextNum /= PreviousNum THEN
Product := Product * NextNum ; -- compute next product
END IF;
PreviousNum := NextNum; -- remember previous item
Ada.Text_IO.Put (Item => "Enter next number > ");
Ada.Integer_Text_IO.Get (Item => NextNum); -- read next item
END LOOP;
-- assert: NextNum is the sentinel and Product is the product of
-- every value of NextNum such that NextNum /= PreviousNum
Ada.Text_IO.Put (Item => "The product is "); -- display result
Ada.Integer_Text_IO.Put(Item => Product, Width => 1);
Ada.Text_IO.New_Line;
END Multiply_Integers;
Sample
RunEnter 0 to stop. Enter first number > 10 Enter next number > 5 Enter next number > 5 Enter next number > 5 Enter next number > 10 Enter next number > 0 The product is 500
Remember,
in a sentinel-controlled loop, the read operation appears twice: before the
WHILE header (the priming read) and at the end of the loop body.
PROGRAM STYLE
A Problem with Sentinel-Controlled Loops
Score to be Integer rather than Natural.
The difficulty that arises in extending the range is that an
incorrectly entered data value may not be caught by Ada. One solution is
to use an extra variable of the extended range, just to read the input data. If
a value is entered into it that is not the sentinel, that value is copied into
the other variable, whose range is that of the normally occurring data. Copying
the value will raise Constraint_Error if the value is out of range.
Ada.Text_IO.Put(Item => "Enter an integer> ");
Ada.Integer_Text_IO.Get(Item => X);
Product := X;
Count := 0;
WHILE Count < 4 LOOP
Ada.Integer_Text_IO.Put(Item => Product, Width => 1);
Product := Product * X;
Count := Count + 1;
END LOOP;
Ada.Integer_Text_IO.Put comes at the end of the loop instead of at
the beginning?
IF statement that compare this value to (N × (N +
1)) / 2 and displays a message indicating whether the values are the same or
different. What message do you think will be displayed?
Copyright © 1996 by Addison-Wesley Publishing Company, Inc.