Courses/CS 2114/Lab Manual/Repetition2

From A-State Computer Science Wiki
Jump to: navigation, search

Repetition Continued

Introduction

This lab will continue to illustrate looping with the use of the C++ do-while control structures.

Topics Covered in this Lab:
  • count-controlled looping
  • event-controlled looping
  • do-while control structure
Questions Answered in this Lab:
  • How does the do-while differ from the while loop?
Demonstrable Skills Acquired in this Lab:
  • understand stopping conditions for both count- and event-controlled loops
  • ability to construct do-while loops
  • understanding of when to use do-while loops


Three Types of Program Control

There are three programming constructs sufficient for the solution of any programming problem: sequence, selection, and repetition. The “hello, world” type of program illustrates the sequence construct; one statement executes after another in the order written. The previous lab examined selections with the if and if-else control structures. This lab introduces repetition, which is what allows the speed of a computer to be exploited by performing the same task many times.


Two Types of Repetition

From a logical standpoint, there are two types of repetition: event-controlled and count-controlled. Event-controlled repetition continues until some specific event occurs. When a telephone number is looked up in a directory, the search stops when the corresponding name is either found or determined not to be in the directory; the specific quantity of names and numbers to be examined will not be known beforehand. A program may be designed to execute until the user indicates “finished” with a ‘y’ (yes) or ‘n’ (no). (Incidentally, the indication in this case is a sentinel value and this type of event-controlled loop is often referred to as a sentinel-controlled loop.) Count-controlled loops execute a specific number of times which is known in advance of the loop's start. Many mathematical formulae involve summations or products of a known number of values; for example, Horner's method for evaluating a polynomial of degree n requires one multiplication and one addition for each of the n degrees. Other more mundane count-controlled loops may be based on seven days in a week, twelve items in a dozen, or a known number of students enrolled in a course.


Three Syntax Structures for Looping in C++

With respect to C++ syntax, there are three looping structures: while, for, and do-while. Each of these looping structures has a purpose depending on the context where repetition occurs in a program; each of these structures can be used for either event- or count-controlled repetition.

The three C++ loops are categorized as pre-test and post-test based on whether they perform their test before or after the body of the loop. The while control structure is a pre-test loop and the do-while control structure is a post-test loop; these two structures are typically associated with event-controlled iteration. The for control structure is another pre-test loop, but it is typically used for count-controlled iteration. In this lab the while and for control structures will be reviewed and the do-while control structure will be examined.

The while Control Structure

The basic syntax of the while control structure is as follows:

Information Icon.pngSyntax
   while (CONDITION) 
      STATEMENT;  // body

The condition given by CONDITION may utilize any combination of relational, logical, arithmetic, and/or other operators in C++. The while control structure will repeat the “body” of the loop (the STATEMENT) as long as the condition is true (non-zero). If the condition ever becomes false (zero), the repetition ends and execution continues at the statement following the while loop. In the example above, the loop body is only one statement. Generally, it is desired to repeat more than one statement; to do so, use a compound statement, or block of code, for the loop body. Recall that a compound statement uses the curly braces { and } to enclose any number of statements.

The extended syntax for the while control structure shown below incorporates the three parts of the count-controlled loop.

Information Icon.pngSyntax
   INITIALIZE;
   while (CONDITION)
   { 
      BODY;
      UPDATE;
   }


As a specific example, the following syntax is of a sentinel-controlled loop.

Information Icon.pngSyntax
INITIALIZE;                                    PROMPT AND READ FIRST DATA VALUE;
while (CONDITION)                     ==>      while (DATA != SENTINEL VALUE)
{                                              {
   BODY;                                          BODY;
   UPDATE;                                        PROMPT AND READ NEXT DATA VALUE;
}                                              }

The initialization step for a sentinel-controlled loop is to prompt the user for data and get the keyboard input. (If the input was from a file, the prompt would not be needed, only the read.) The CONDITION is the verification that the data read was not the sentinel value. The UPDATE becomes the prompt and subsequent read of the next data value.

Note that a value is read prior to the initial test of the while loop; subsequent values are read at the bottom of the loop, immediately prior to the return to the top of the loop and another test. All data is tested prior to being used in any calculations. The last piece of data read is not processed; consequently, n+1 reads are required for n meaningful pieces of data. Beginning students are often troubled by the repetition of the cout-cin pair, sometimes trying to replace them with logic which is inevitably more complicated. Suffice it to say that there simply is no more succinct manner in which to accomplish this task.

The pre-test nature of the while loop allows for the possibility that the loop body may never be executed at all. In the example at hand, the first data entered could be the sentinel. In the case of reading a set of scores in which the average is calculated following the sentinel-controlled loop (see previous lab for code detail), there will be no meaningful average; worse, the number of scores would be zero which would result in an undefined quotient. Any time division involves a variable as divisor, the division should be protected from a divisor of zero.

The for Control Structure

The for construct is especially well-suited for count-controlled loops. In count-controlled loops, the number of executions of the loop body is known before the loop body is executed the first time. As will be seen, the very format of the for loop suggests count-controlled repetition. As a general rule, use while for event-controlled loops, such as sentinel-controlled loops, and for with count-controlled loops. Consistency in this will make programs that much more readable and maintainable.

Here is an example of the syntax of the for control structure.

Information Icon.pngSyntax
for (INITIALIZE; TEST; UPDATE)
{
   BODY;
}

The for control structure is comprised of two parts, the header and the body; this much is the same as for the while control structure. The for control structure header in turn has three parts, each a C++ statement, separated by semicolons: initialize, test, and update.

  1. Initialize: Initialization occurs once, as the first (preliminary) step in executing the for loop, before the loop begins repeating. This statement should be used to initialize the loop variable used in the test part of the header. In general, this variable will “count” the number of times through the loop. As will be seen, this variable may or may not appear in the loop body.
  2. Test: After initialization, the test expression is then evaluated repeatedly; each time it is determined to be true (nonzero), the loop body is executed. The for loop execution ends the first time the test expression is found to be false (zero). Note that the expression is evaluated before each execution of the loop, exactly as is done for the while loop. In counting loops, this test will compare the loop variable against some limit. In the above example, the loop continues as long as the loop variable page is less than seven. How many times does the above loop body execute?
  3. Update: Immediately after each execution of the loop body (and thus just prior to the next evaluation of the test expression), the loop control update is performed. In most iterative or counting loops, the loop variable needs to be incremented. In the example above, the loop variable page is incremented by one before it is tested. It is also possible to count down by using a decrement here or count by more than one using either the += or -= operator.

A common mistake when constructing for loops is to use a comma in place of a semicolon.

Recall that the for control structure header is very flexible; refer to the previous lab for examples.

As mentioned above, variables can be declared inside the for loop header itself. Doing so can be useful when the only purpose of the variable is to count the number of iterations of the loop.

Equivalence of for and while Loops

It is interesting to note that since the for loop and the while loop are both pre-test loops, any for loop can be written as a while loop and vice versa. The following illustrates the conversion between a for and a while loop.

Information Icon.pngSyntax
                                               INITIALIZE;
for (INITIALIZE; TEST; UPDATE)       <==>      while (TEST)
{                                              {
   BODY;                                          BODY;
}                                                 UPDATE;
                                               }


Notice this follows the discussion earlier about the parts of the for loop header. The for control structure initializes only once before the loop, the condition is tested before each execution of the body of the loop, and the update is done at the end of the loop prior to the next test.

As suggested above, any while loop can also be written as a for loop, again due to the fact that both are pre-test loops.

Information Icon.pngSyntax
INITIALIZE;                                    INITIALIZE;
while (TEST)                         <==>      for ( ; TEST; )
{                                              {
   BODY;                                          BODY;
   UPDATE;                                        UPDATE;
}                                              }


Observe that the for loop's variable initialization and update are omitted from the header. As noted earlier, C++ considers the missing statements to be empty statements and will still execute the for loop.

The do-while Control Structure

Recall the syntax of the while loop.

Information Icon.pngSyntax
   while (TEST) 
      STATEMENT;  // body


The do-while control structure moves the EXPRESSION to the end of the structure, as follows:

Information Icon.pngSyntax
   do
      STATEMENT;
   while (TEST);


An example loop might display the integers from one to ten, one to a line.

Examplecode.pngExample Code
   int i = 1;

   do 
      cout << i++ << endl;
   while (i <= 10);


In order to use more than one statement as the body of the do-while loop, a compound statement must be used.

Information Icon.pngSyntax
   do
   {
      BODY;
   }
   while (TEST);


The earlier example can be rewritten with a two-statement loop body.

Examplecode.pngExample Code
   int i = 1;

   do 
   {
      cout << i << endl;
      i++;
   } 
   while (i <= 10);


When using the do-while, surrounding even a single statement with braces is a good idea for the sake of consistency and thus readability.

Examplecode.pngExample Code
   int i = 1;                                  int i = 1;                                  int i = 1;

   do                                <==>      do                                <==>      do {
   {                                           {                                              cout << i++ << endl;
      cout << i++ << endl;                        cout << i++ << endl;                     } while (i <= 10);
   }                                           } while (i <= 10);
   while (i <= 10);

Pre-Test Versus Post-Test in Looping

The do-while control structure differs from the while control structure in the time at which the test is made for the loop. Notice again that the condition in the do-while is after the body; following each execution of the body of the loop, the test is made to determine if the loop should execute again. The while loop will test before the body executes, so a while loop may not execute its body at all. Since the do-while does not test until after the loop body has been executed, the body of the do-while is always executed at least once. The while loop is sometimes referred to as a pre-test loop and the do-while as post-test, reflecting the time of the test relative to the body of the loop.

A while loop equivalent to the do-while is as follows.

Pseudocode.pngPseudocode
   do                                          // statements (copy of the body of the do-while loop)
   {                                 <==>      while (TEST) 
      // statements                            {
   }                                              // statements (another copy of the body of the do-while loop)
   while (TEST);                               }


The above while loop will execute the body of the loop at least once since a complete copy of the body precedes the test. When a program uses a while loop like this instead of a do-while, the program segment involved is much longer because of the copied code; further, differences in the copies can occur when changes are made, introducing errors and ultimately leading to code that is more difficult to maintain. The do-while can thus be an effective control structure under the right circumstances.

The do-while loop can be used for looping that is validating input from the user. The pseudo code for an input validation loop is as follows:

Pseudocode.pngPseudocode
   do 
   {
      // display message explaining what data is needed
      // get input from user
   }
   while // input from user is not what was expected

The following example is from a program that requires positive integer values be entered by the user:

Examplecode.pngExample Code
   int value;

   do 
   {
      cout << "Enter a positive integer value (non-positive to end):  ";
      cin >> value;
   }
   while (value <= 0);  // continue prompting and reading as long as input is not positive

The examples given above might lead one to believe that the difference between using a while control structure and a do-while control structure is simply altering the order of the elements and perhaps some of the statements. This is not always the case. As an example, consider a using a do-while loop for processing input from the user as the input is obtained. One might believe the pseudo code for an input processing loop to be as follows:

Pseudocode.pngPseudocode
   // incorrect                                                  // correct

   do                                                            // get input from user
   {                                                             while // input is valid
      // get input from user                                     {
      // do something requiring valid input         <!=>            // do something requiring valid input
   }                                                                // get input from user
   while // input is valid                                       }

Notice how some statements are repeated in the while loop, in particular, a copy of the code to get the first input from the user must be added prior to the beginning of the loop. This is not the only difference though. Note that the do-while loop as shown above would process the user input before any validation occurs as something is done with the input as soon as it is obtained from the user prior to any checks as to validity. As an example, if the loop was a sentinel-controlled loop, the sentinel value would be read and then processed as regular data before being identified by the do-while loop as a sentinel whereas the while loop would immediately recognize the sentinel and cease processing. When using a do-while loop, control logic must be added to the statements where input is processed to avoid processing input that is not valid (see pseudocode below). As a rule, the while loop is the more desirable option for this type of looping.

Pseudocode.pngPseudocode
   // correct                                                    // correct

   do                                                            // get input from user
   {                                                             while // input is valid
      // get input from user                                     {
      if // input is valid                          <==>            // do something requiring valid input
         // do something requiring valid input                      // get input from user
   }                                                             }
   while // input is valid

For example, suppose a program calculates the summation of the positive integers entered by the user.

Examplecode.pngExample Code
   int sum = 0;                                                           int sum = 0;
   int value;                                                             int value;
                                                                          
   do                                                                     cout << "Enter a positive integer (non-positive to end): ";       
   {                                                                      cin  >> value;
     cout << "Enter a positive integer (non-positive to end): ";          
     cin  >> value;                                                       while(value > 0)
                                                                          {
     if (value > 0) {                                                        sum += value;                        
       sum += value;                                              <==>       cout << "Enter a positive integer (non-positive to end): ";      
     }                                                                       cin  >> value;       
   }                                                                      }    
   while(value > 0);

Both of these are correct; input is not included in the summation unless it is a positive integer. The body of the do-while is longer and has an unsightly redundant test of the input. The while has redundant code to prompt and read the first value prior to the beginning of the loop.

Note: Additional refinements will be made to this task in a future laboratory.