Laboratory 4

Iteration Structures

Introduction

Virtually all computer programs use loops extensively. Normally, a set of instructions is executed repeatedly until a specified condition is satisfied. In this lab we will look at two C++ constructs designed to control loops: the while loop and the forloop. We will work with a variety of standard methods of controlling loops. In the Theory of Computing it has been shown that all loops can be implemented using the while loop. The other forms of loop constructs are provided for convenience and readability.

Key Concepts

conditions (boolean expressions)

C++ while statements

Problem solving: Averaging

Nested loops

C++ for statements

Problem solving: Simulation

Problem solving: Producing a histogram

Before the Lab

Read Sections 4.7 – 4.12 in Cohoon and Davidson.

Preliminary

  • Turn the PC on, if necessary.
  • Access the network.
  • Copy the source files from the Lab 04 Source Files folder.
  • Start up CodeWarrior.
  • Open the LabWork project.

While Loops

Observation

The program AddList.cpp will read a list of five numbers and add them up. The program processes exactly five numbers, no more, no less.

  • Add the file AddList.cpp to the LabWork project.
  • Run the program to see what it does.
  • Look at the source code and be sure you understand it.

The object count is used to control the while loop. Note that three things are done to count:

count is initialized: int count = 0;

count is tested: while (count < 5)

count in incremented:count++;

  • What would happen if the condition were replaced by

count < 0

  • What would happen if the statement count++ were omitted?

Experimentation

We will modify AddList.cpp to allow it to add any number of numbers.

  • Modify AddList.cpp by having the user enter the number of times the loop is to be repeated. Call this integer size and use it to control the loop.
  • Run the program to be sure that it works.
  • What happens if you enter 0 for the size of the list?

For Loops

Observation

A for loop is a special statement that allows us to initialize a counter, increment the counter, and test the counter all in a single statement. When writing a loop controlled by a counter, it is preferable that it be written as a for loop. The general form of the for statement is

for (initialize counter; test counter; increment counter)

  • Modify AddList.cpp again by using a for loop rather than a while loop to control the program.
  • Run the program to be sure that it works.

Now we will modify this program to produce a program that averages a list of numbers.

  • Use Save As… to save a copy of AddList.cpp and name it Average.cpp.

The program Average.cpp will be similar to AddList.cpp except that its output will be the average of the list of numbers.

  • Modify the program so that after computing the sum, it divides by the number of numbers to get the average.
  • Run the program to see if it works.
  • What happens if you enter 0 numbers?

If there were no numbers, then

  • Modify the program to print an appropriate message to cout instead of trying to print the average.
  • Run the program to be sure that it works when there are 0 numbers.

Generating Random Numbers

Observation

The program RandomAdd.cpp will generate a list of random integers in the range from 1 to 100, using a for loop. It will print the integers and then print their total. The user tells the program how many integers to generate. We are using the random number generator because we would like to test our program with a large number of numbers, but we do not want to have to enter them by hand.

A random number generator uses a “seed” to generate the numbers. Every time a random number is generated, the seed is updated in preparation for the next random number. Typically, a program will go to the computer’s clock to get an initial value for the seed. That way the random numbers will be different every time the program is run.

In C++, there are two library functions needed to generate random numbers. The function srand() initializes the seed and the function rand() returns an integer in the range 0 to 32767. Normally, a program will call on srand() once at the beginning and then call on rand() repeatedly to produce a sequence of random numbers.

  • Add RandomAdd.cpp to the LabWork project.
  • Run the program.
  • Run the program again with the same input and note that the output is different. That is because it is random. It will be different every time.
  • Study the source code of RandomAdd.cpp to see how it works.

Note the statement

srand((unsignedint) time(0));

This statement calls on the time() library function to get the current time (number of seconds since midnight Jan 1, 1970). That value is cast as an unsigned integer, which is then passed on to srand() to initialize the seed. The important thing to us right now is that it works.

Later in the program there is the line

number = 1 + rand() % 100;

Given that rand() returns a random integer in the range from 0 to 32767,

  • What does the expression

1 + rand() % 100

do?

The next program we will look at is based on the famous “3x + 1” problem. Given a positive integer x, form another integer according to the following rule: if x is odd, multiply x by 3 and add 1; if x is even, divide x by 2. By repeatedly applying this rule, we generate a sequence of positive integers.

For example, if x = 7, then the next integer is 22 since 7 is odd. The term after 22 is 11 since 22 is even, and so on. Note that if we start with 1, 2, or 4, we immediately fall into the cycle

4, 2, 1, 4, 2, 1, …

It is conjectured, but not proven, that no matter what positive integer we begin with, the sequence will eventually fall into the cycle 4, 2, 1, … For example, the sequence beginning with 7 is 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, …

The program ThreeXPlusOne.cpp reads a positive integer and then generates the sequence for that integer until 1 occurs.

  • Add the file ThreeXPlusOne.cpp to the LabWork project.
  • Run the program several times, using different input values.

Note that the while loop is controlled by the condition x > 1. On each iteration of the loop, a new value of x is computed. The loop will continue as long as x > 1.

Sentinel Values

Experimentation

A loop that reads input may be controlled by a sentinel value. A sentinel value is a special value that is used to indicate the end of the input. Once the program reads the sentinel value, it stops reading input and continues on with the rest of the program. For example, if a program is reading test grades which are all in the range 0 to 100, then the programmer may use 9999 as a sentinel value since it could not possibly be a legitimate test grade. When the program reads 9999, it will stop reading input. We will use a loop controlled by a sentinel value to modify the program ThreeXPlusOne.cpp.

The program ThreeXPlusOne.cpp worked fine except that if the user wanted to generate several sequences, he had to restart the program each time. It would be better if, after generating a sequence, the program would allow him to enter a new starting value to generate the next sequence. Then, when he is ready to quit, he could enter a starting value of 0 to indicate that.

We will modify ThreeXPlusOne.cpp to incorporate this feature.

  • Add to it a while loop controlled by the sentinel value 0.

Let SENTINEL be a constint and assign it the value 0. Then write a while statement that compares the starting value x to the sentinel value SENTINEL. At the end of the loop, you must prompt the user and read another starting value.

Be sure not to modify the existing while loop that generates the sequence. Rather, you should “build” a second loop around it. In other words, when you are done, you will have the original while loop nested inside an outer while loop.

  • Run the program to see if it works.

Application

Open the MS Word document Lab 04 App.doc, found in the Lab 04 App subfolder, and follow the instructions.

Summary

In this lab, we saw how to use while loops for both definite (i.e., counter controlled) iteration and indefinite iteration. To program definite iteration, we saw that we could just as easily use for to write an equivalent loop. However, indefinite iteration is such that the number of iterations of the loop cannot be predetermined by the program. In such cases, the while loop seems more natural. Finally, we ran a simulation experiment in the Lab Application to see if a simulated die truly behave as we would expect. In running this experiment, and in producing a histogram to display its results, we saw important applications of for loops