Java Unit 7

Loops

7.1  While Loops and Do Loops

7.2  For Loops

7.3  Nested Loops

7.4  Graphical Examples

7.1  While Loops and Do Loops

It is desirable for programs to be able to take certain actions repetitively.  This is known as looping or iteration.  There are several structures in Java that allow this.  One of these is the while loop.  This kind of loop allows actions to be repeated without knowing in advance how many repetitions there will be.  It is controlled by the same kind of truth condition as those explained in Unit 6 for if statements.

A while loop can be used to get input from a user, for example.  The code fragment below illustrates such a use.  A value is set before the loop and is tested in the while statement.  If the condition is true the loop is entered and the body of the loop is executed.  Somewhere in the body of the loop the variable tested in the condition is altered.  After the body is concluded, execution returns to the top of the loop and the condition is tested again.  If the condition is false, the body is skipped and execution continues after the loop.

…

String answer = “yes”;

while(!answer.equalsIgnoreCase(“no”))

{

  /*  Do whatever is needed in the body of the loop.  */

  myterminal.println(“Go again?  Answer yes or no.”);

  answer = myterminal.getString();

}

…

As long as the user does not enter “no” at the prompt, the loop will repeat.  If “no” is entered, execution will then continue with any statements following the body of the loop.  Note that the test condition is not case sensitive.

A simple arithmetic operation can also be used to illustrate the nature of looping.  Integer division can be defined as repeated subtraction.  How many times one number goes into another is the same as how many times it can be subtracted from the other before the result is less than the number you’re dividing by.  A while loop is a suitable structure for implementing an algorithm like this.  The count of how many times the loop runs is the answer to the division problem.  You don’t know in advance what this value will be.  Here is a fragment of code illustrating the algorithm where the desired result is stored in the variable named quotient:

…

int dividend, divisor, quotient, remainder;

quotient = 0;

myterminal.println(“Enter an integer dividend.”);

dividend = myterminal.getInt();

myterminal.println(“Enter an integer divisor.”);

divisor = myterminal.getInt();

remainder = dividend;

while(remainder >= divisor)

{

  remainder = remainder – divisor;

  quotient++;

}

…

This simple implementation does not correctly handle all cases of integer division.  It has a defect that illustrates one of the pitfalls of programming with loops.  Consider what happens if the dividend is positive and the divisor is negative.  Before the loop the remainder is given the value of the dividend, so it’s positive.  The looping condition is (remainder >= divisor) which will certainly be true, so the loop will be entered.  Inside the loop the remainder has a negative value subtracted from it.  It remains positive and only increases in size.  The looping condition will never be false.

When a loop exists in code and the looping condition is never false, this results in an error known as an infinite loop.  The compiler cannot detect such a situation in advance.  This is a run time error where the program will keep on executing the loop and never stop.  The immediate solution to this problem is to kill the program using the key combinations CTRL+C or CTRL+ALT+DEL, or by closing the window the program is running in.  Sometimes the system will be so badly trapped in a loop that it will be necessary to restart the operating system.  After bringing the program to a halt you have to find the logic error in the source code that caused the looping condition never to be false.

In general, loops based on numeric values are based on a test of inequality, where one value or another either increases or decreases in the body of the loop.  The example below shows the general form where the value increases.  The example happens to use strict inequality, but both strict and non-strict inequality are possible depending on the logic of the specific situation.

while(x < y)

{

    increase x by some amount

}

Under certain conditions you might be able to write a loop that accomplished the same thing in the following form, where you expect x to hit the stopping value exactly:

     /*  NOT RECOMMENDED  */

while(x != y)

{

    increase x by some amount

}

This is unwise.  It is possible that x plus the increments will never exactly equal y.  This can happen because binary representations of decimal values may not be exact.  It can also happen because for some given set of values, x plus a series of increments will simply not add up to y.  This will lead to an infinite loop where the value of x will go beyond y.  If the condition is based on < or >, even if the exact value isn’t encountered, the loop will stop.

do loops are similar to while loops.  Rather than testing the looping condition at the beginning, they test the condition after the body of the loop has been executed.  A classic example of the use of a do loop is in handling user input where the body of the loop is to be executed once no matter what the user enters.  This saves the programmer the trouble of writing a separate prompt and input statement before the beginning of the loop.  This code fragment illustrates such a use:

do

{

  myterminal.println(“Enter a rate > 0”);

  rate = myterminal.getDouble();

  /*  Do whatever is needed in the body of the loop.  */

} while(rate > 0);

The key word do marks the top of the loop but it does not implement the condition.  The condition is only tested after the body of the loop has been executed one time.  If the user enters a positive value, then the loop will run again.  Note that there is no punctuation before the opening brace or after the closing brace of the loop and there is a semicolon after the condition.

7.2  For Loops

for loops are loops which are based on knowing in advance how many times they should run.  In general, it is possible to write a while loop that will also handle this case.  However, it is usually simpler to use a for loop.  It is not practical to write a for loop which is designed to handle an unknown number of repetitions.

Here is an example of a while loop that handles a fixed number of repetitions.  Suppose the variables startingvalue and endingvalue contain integers with startingvalue < endingvalue. 

int i = startingvalue;

while(i <= endingvalue)

{

/*  Do whatever is needed in the body.  */

i++;

}

            The elements of the loop are initialization of the loop control variable, i, to startingvalue, a condition depending on its upper limit, endingvalue, and its incrementation.  An equivalent for loop includes these three things in one compact line of code:

int i;

for(i = startingvalue; i <=endingvalue; i++)

{

/*  Do whatever is needed in the body.  */

}

            Quite often in programming it is more useful to start the loop index at 0 and have the stopping condition be a strict inequality.  Since the numbering of positions in a string starts at 0, it provides a good illustration of this idea:

int i;

String mystring = “Something”;

for(i = 0; i < mystring.length(); i++)

{

     /*  Do this for example.  */

     myterminal.println(mystring.substring(i, i + 1));

}

            In Java it is also possible to declare the loop control variable, or index, within the for statement.  If this is done, then the variable is defined within the set of braces containing the body of the loop as shown here:

for(int i = startingvalue; i <=endingvalue; i++)

{

/*  The variable i exists in these braces.  */

}

            When writing for loops it is possible to count up or down, i.e., increment or decrement.  It is also possible to count by values other than 1, such as 2, 3, etc.  It is also possible for the loop index to be a double rather than an int and count by fractional amounts.  When counting down, the stopping condition has to be changed to greater than rather than less than.  Here is a little example that illustrates these points:

for(double x = 3.5; x >= -2.0; x = x – 0.5)

{

     …

}

            The next series of examples has to do with the topic called “scope”.  This refers to the question of where in a program a variable is defined.  Scope will be covered in more detail in the next unit, but certain things can happen with loop index declarations that require an introduction to the topic now.  In general, it is not possible to declare two variables with the same name in the same program.  You may have gotten a compiler error already because your program contained statements such as these:

int myint = 5;

…

int myint = 3 * 2;

            Declaring the variable twice is known as a redeclaration error.

            For the following examples, consider the possibility that you would like to print out the value of the loop index every time through the loop, and you’d also like to print out its value after the loop is finished.  Recall that in certain cases, if you use a variable without storing a variable in it, the compiler will complain.  In the following examples, if a variable is declared, it is shown as being initialized, even if this is not necessary.  This is just so that the only problems under consideration when reading the code are problems related to scope.

In the following code the variable i is declared before the loop and again in the for statement.  Like the code above, this will result in a redeclaration error.

…

int i = 0;

for(int i = 1; i <= 7; i++)

{

     myterminal.println(i);

}

myterminal.println(i);

…

            Now consider the following, where i is declared in the for statement, is not declared elsewhere in the program.  Now the compiler will complain that the occurrence of i in the println() call after the loop cannot be resolved.  In other words, by declaring i inside the for statement, it is only defined inside the braces that belong to the loop.  This can be expressed by saying that the scope of the variable is the set of braces belonging to the loop.

     …

for(int i = 1; i <= 7; i++)

     {

     myterminal.println(i);

     }

     myterminal.println(i);

     …

            The next example does not cause a compiler error.  The declaration of the index again after the loop does not count as a redeclaration.  Within the loop, i is the loop index.  Following the loop, the newly declared i is a completely new and different variable.  From a logical point of view this code does not have the desired effect.  The variable i after the loop does not contain the value of the loop index after the loop has completed.  Why it is OK to declare the variable again after the loop, but not before is a deep subject.  For the time being you can just treat this as a fluke.

…

for(int i = 1; i <= 7; i++)

{

     myterminal.println(i);

}

int i = 0;

myterminal.println(i);

…

            To summarize, the best solution, as usual, is to declare and initialize all variables that will be needed at the top of the code.  In the code shown below, the variable i will be available before, during, and after the loop.  The value it has immediately after the loop will be the last value it took on inside the loop.

…

int i = 0;

for(i = 1; i <= 7; i++)

{

     myterminal.println(i);

}

myterminal.println(i);

…

            Here is an example of the use of a loop in order to implement a mathematical function.  Finding the integral power of some number can be defined in terms of repeated multiplication.  The base is the number to be multiplied by itself.  The power is the number of times it needs to be multiplied.  Since the number of multiplications is known in advance, this algorithm can be implemented using a for loop.  The power serves as the upper limit on the loop index.  Here is a code fragment illustrating this idea:

…

myterminal.println(“Enter the base:  “);

double mybase = myterminal.getDouble();

myterminal.println(“Enter an integral power:  “);

int mypower = myterminal.getInt();

double result = mybase;

for(int i = 1; i < mypower; i++)

{

     result = result * mybase;

}

myterminal.println(result);

…

            Note that just like the example where division was implemented as repeated subtraction, this implementation of powers does not handle all cases, such as negative or fractional powers.  It is designed simply to illustrate the idea of using a loop where the limit on the loop index is known in advance.

            Being able to do things multiple times makes it possible to implement various interesting algorithms.  Consider the problem of finding the area of a region in a plane.  Suppose you would like to find the area under the curve y = x² between x = 0 and x = 1.  For these values of x the values of y also fall between 0 and 1.  The area of interest is shown here with shading.

            If you are familiar with calculus, you know that the exact answer can be found by doing this integration:

            If you don’t know calculus, don’t want to use calculus, or you are confronted with a problem where there is no good solution from calculus, there is a different way to find the area.  Suppose you can randomly generate points that fall in the whole square area.  The x coordinate for these points would be between 0 and 1 and the y coordinate would also be between 0 and 1.  If the points are truly random, the following ratio would approximate the area under the curve.  The more points there were, the closer the approximation would become.

(The number of points where y is less than x²) / (The total number of points)

            A possible outcome for 18 randomly generated points is illustrated in the diagram below.  The shaded points fall below the curve.  The unshaded points fall above.  The ratio of shaded points to the total number of points, 6/18, is an approximation to the area under the curve.

Finding the area using random numbers in this way is called Monte Carlo integration.

There is a class in Java that supports random number generation.  For full information on this class, consult the API documentation.  The information needed in order to do this example is summarized here:

     import java.util.Random;

     …

     Random mygenerator = new Random();

     …

     double myrandomdouble;

     …

     myrandomdouble = mygenerator.nextDouble();

     …

            The call to the method nextDouble() will return a value such that:

            0 <= myrandomdouble < 1

            This is the result when the default constructor is used.  If the random number generator is constructed by sending in a parameter, this parameter will be the upper bound on the range of random numbers generated.

            Here is a program that does the Monte Carlo integration problem.  Comments are included which explain how the program implements the algorithm.  If you run it several times, specifying a different number of trials each time, you will see that the more points there are, the closer the result comes to the exact solution.

import java.util.Random;

public class MonteCarlo

{

  public static void main(String[] args)

  {

    MyTerminalIO myterminal = new MyTerminalIO();

    Random mygenerator = new Random();

    /*  trials is the total number of points.  */

    int trials = 0;

    int count = 0;

    double area = 0.0;

    double randx, randy;

    myterminal.print("How may points do you want?  ");

    trials = myterminal.getInt();

    for(int i = 1; i <= trials; i++)

    {

      /*  Both an x and a y value between      */

      /*  0 and 1 are generated.  Together     */

      /*  they represent a randomly generated  */

      /*  point in the unit square in the      */

      /*  x, y plane.                          */

      randx = mygenerator.nextDouble();

      randy = mygenerator.nextDouble();

      /*  This tests to see whether the point  */

      /*  falls below the curve.  If so, the   */

      /*  count is incremented.                */

      if(randy <= randx * randx)

        count++;

    }

    /*  The area is approximated by dividing the  */

    /*  the count of points below the curve by    */

    /*  the total number of points, (trials).     */

    area = (double) count / (double) trials;

    myterminal.println("The area under the curve is " + area);

  }

}

7.3  Nested Loops

The bodies of loops are set off by braces, and any set of braces in Java may contain any other syntactically correct set of statements.  This means that loops may contain other loops.  A while loop may contain another while loop or a for loop, and a for loop may contain another for loop or a while loop.  Any time one loop contains another this is referred to as nesting, and nesting can be arbitrarily deep.  One loop may contain another, which may contain yet another, and so on.

Here is a simple example of a program where a for loop is contained within a while loop.  The while loop handles user input and the for loop implements an algorithm for finding the sum of the positive integers less than or equal to a given integer.

public class NestedLoopEx1

{

  public static void main(String[] args)

  {

  MyTerminalIO myterminal = new MyTerminalIO();

  int inputvalue;

  int i;

  int mysum;

  myterminal.println("Enter a positive integer to find the sum");

  myterminal.println("of the integers less than or equal to it.");

  inputvalue = myterminal.getInt();

  while(inputvalue > 0)

  {

    mysum = 0;

    for(i = 1; i <= inputvalue; i++)

    {

      mysum = mysum + i;

    }

    myterminal.println("The sum is:  " + mysum);

    myterminal.println("If you would like to go again, enter another positive integer.");

    myterminal.println("Otherwise, enter 0 or a negative integer.");

    inputvalue = myterminal.getInt();

    }

  }

}

            It will turn out that nested for loops are of particular interest because of the pattern of values the loop indexes take on.  The following example program illustrates this pattern in the form of a table.  The outer loop, with index i, corresponds to the rows.  The inner loop, with index j, corresponds to the columns.  Note the use of print() and println() at various points in the loops in order to get the output to print row by row as a table. 

public class NestedLoopEx2

{

  public static void main(String[] args)

  {

    MyTerminalIO myterminal = new MyTerminalIO();

    int i;

    int j;

    myterminal.println("        Column 0    Column 1    Column 2    Column 3");

    for(i = 0; i < 4; i++)

    {

      myterminal.print("Row " + i + "  ");

      for(j = 0; j < 4; j++)

      {

        myterminal.print("(i=" + i + ", j=" + j +")  ");

      }

      myterminal.println();

    }

  }

}

            Here is the output of the program:

        Column 0    Column 1    Column 2    Column 3

Row 0  (i=0, j=0)  (i=0, j=1)  (i=0, j=2)  (i=0, j=3)

Row 1  (i=1, j=0)  (i=1, j=1)  (i=1, j=2)  (i=1, j=3)

Row 2  (i=2, j=0)  (i=2, j=1)  (i=2, j=2)  (i=2, j=3)

Row 3  (i=3, j=0)  (i=3, j=1)  (i=3, j=2)  (i=3, j=3)

Press any key to continue . . .

7.4    Graphical Examples

Each of the following examples contains a block of code similar to this one.  This block causes a delay in the execution of the program.  This is desirable so that the animation occurs at a speed that the human eye can see.  The parameter to the sleep() method is the number of milliseconds of delay.  In this case, it would cause a quarter of a second of delay.  For the time being, you do not need to worry about what the rest of the syntax means.  If you would like to use this when writing programs of your own you can simply copy it and change the parameter value as needed.

try

{

     Thread.sleep(250);

}

catch(InterruptedException e)

{

     System.out.println("InterruptedException:  " + e);

}

Here is an applet that animates the idea behind the preceding example, NestedLoopEx2.java.  This applet contains doubly nested loops that cause dots to shown in a 2 dimensional pattern, row by row, where each loop index corresponds to one of the dimensions.

import javax.swing.JApplet;

import java.awt.Graphics;

import java.awt.Graphics2D;

import java.awt.geom.Rectangle2D;

import java.awt.geom.Ellipse2D;

import java.awt.Color;

public class NestedLoopApplet extends JApplet

{

  public void paint(Graphics g)

  {

    Graphics2D g2 = (Graphics2D) g;

    int i, j;

    Ellipse2D.Double mycircle;

    double circlex = 75.0;

    double circley = 75.0;

    Color mycolor = new Color(0.75F, 0.0F, 0.75F);

    g2.setColor(mycolor);

    Rectangle2D.Double myrectangle = new Rectangle2D.Double(25.0, 25.0, 265.0, 265.0);

    g2.draw(myrectangle);

    for(i = 0; i < 4; i++)

    {

      for(j = 0; j < 4; j++)

      {

        mycircle = new Ellipse2D.Double(circlex, circley, 15.0, 15.0);

        g2.fill(mycircle);

        circlex = circlex + 50.0;

   /*  This code causes there to be a quarter of a

  second delay for every dot that is shown.  */

        try

        {

          Thread.sleep(250);

        }

        catch(InterruptedException e)

        {

          System.out.println("InterruptedException:  " + e);

        }  

 }

      circlex = 75.0;

      circley = circley + 50.0;

    }

  }

}

Here is an applet that animates Monte Carlo integration.  Interactive input using the MyTerminalIO class doesn’t work in an applet, so the number of trials is hard coded.  Certain numeric parameter values were chosen so that the output would look nice.  In particular, parameters are adjusted so that the circles representing the random data points stay within the boundaries of the rectangle, and so that the circles are correctly displayed with their centers above or below the line y = x² according to the values of their coordinates.  The adjustments make the code appear a little complicated, but the basic idea is the same as the non-graphical example of Monte Carlo integration.  Using the knowledge gained from the seven units covered so far, it is possible to write a relatively short applet that can help a person visualize the algorithm implemented by a piece of computer code.

import javax.swing.JApplet;

import java.awt.Graphics;

import java.awt.Graphics2D;

import java.awt.geom.Rectangle2D;

import java.awt.geom.Ellipse2D;

import java.awt.Color;

import java.util.Random;

public class MonteCarloApplet extends JApplet

{

  public void paint(Graphics g)

  {

    Graphics2D g2 = (Graphics2D) g;

    Random mygenerator = new Random();

    int trials = 100;

    int count = 0;

    double area = 0.0;

    double randx, randy;

    int i, j;

    Ellipse2D.Double mydot;

    Ellipse2D.Double mycircle;

    double dotx, doty, circlex, circley;

    Color mycolor = new Color(0.75F, 0.0F, 0.75F);

    g2.setColor(mycolor);

    /*  Draw the box.  */

Rectangle2D.Double myrectangle = new

Rectangle2D.Double(25.0, 25.0, 265.0, 265.0);

    g2.draw(myrectangle);

    /*  Draw the curve using little dots.  The index i goes

        through the range of values for the x dimension of

        the rectangle.  */

    for(i = 0; i < 265; i++)

    {

      /*  dotx has to be shifted 25 to the right since the x

          coordinate of the upper left hand corner of the

          rectangle is 25.  */

      dotx = (25.0 + i);

      /*  In this expression, i * i represents squaring.

          This result is divided by 265 in order to put it

          in proportion with the height of the rectangle.

          Because the y axis in graphics runs from top to

          bottom, if displayed without further adjustment

          the curve would appear upside down.  Subtracting

          from 290, the value of the lower edge of the

          rectangle gives the correct, mirror image of the

          curve.  */

      doty = 290.0 - (i * i) / 265.0;

      mydot = new Ellipse2D.Double(dotx, doty, 1.0, 1.0);

      g2.draw(mydot);

    }

    /*  Change the color to blue and draw the points,

        representing them with small circles.  */

    g2.setColor(Color.blue);

    for(i = 1; i <= trials; i++)

    {

      randx = mygenerator.nextDouble();

      randy = mygenerator.nextDouble();

/*  This code causes there to be a tenth of a second delay for every random point that is shown.  */

       try

       {

          Thread.sleep(100);

       }

       catch(InterruptedException e)

       {

          System.out.println("InterruptedException: " + e);

       }

      /*  In order for the Monte Carlo integration to be

          correct, randx and randy together are the

          coordinates of points, which are not visible.

          Circles are used to represent these points, and

          the random points are the centers of the circles.

          Circles are oriented to the upper left hand corner

          Of their bounding boxes, so the coordinates of the

          upper left hand corner have to be derived from the

          coordinates of the center.  It is also

          necessary to make adjustments so that the circles

          fall completely within the rectangle.  */

      /*  In this expression, multiplying by 265 proportions

          the x value to the width of the rectangle.  Adding

          25 brings it within the lefthand boundary of the

          rectangle.  The circles have a radius of 5, so