CSC 207 Grinnell College Spring, 2012
 
Algorithms and Object-Oriented Design
 

Control Structures and Arrays in Java

Quick index: control structures, approximating Pi, arrays, Sieve of Eratosthenes

Abstract

This reading reviews some basic Java control structures and outlines the use of simple arrays. These constructs then are applied to solve several problems.

Control Structures

Basic Java control structures may be classified as follows:

For the most part, Java syntax is quite similar to C, and the ideas in Java follow the ideas in both Scheme and C.

After reviewing Java syntax, we illustrate several constructions by considering two sample programs.

if Statements

if statements have two forms, analogous to Scheme:

if (condition)
   statement;

if (condition)
   statement1;
else
   statement2;

In each case, the overall condition must be in parentheses and only a single statement can be given. As in Scheme and C, multiple statements can be placed in then or else by grouping them together in brackets { } -- just as a (begin ... ) was used in Scheme.

Also as in Scheme and C, the condition may be made up of several clauses, combined by such operations as:

   ! not
   && and
   || or

Example

The following code checks if a point (x, y) is contained in a circle of radius 1, centered at the origin:

     // check if point is in circle of radius 1.0
     if (x*x + y*y <= 1.0)
         count = count + 1;

switch Statements

Java's switch statement works with simple ordinal types (e.g., int, char), using a syntax and semantics similar to C.

   switch( variable )
   {
      case value1:
      case value2:
             // action for these values
             break;
      case value3:
      case value4:
             // action for these values
             break;
   ...
      default:
             // action for values not given
             break;
   }

A common use of the switch statement arises in menu-driven programs, in which a program performs a range of actions, based upon commands that user types.

for Loops

One type of for loop in Java uses the same basic syntax as C. (Later in the semester, we will see another for syntax that takes advantage of Java classes and objects.)


for (initialization ; continue-condition ; update)
   statement;

Here, initialization contains one or more statements (separated by commas) which initialize variables. continue-condition is a Boolean condition. Every time execution gets to the top of the loop, this condition is re-evaluated. If the condition is true, the statement is executed as the body of the loop. The update portion of the code allows variables to be updated from one iteration of the loop to the next.

Example

for-loops are particularly common when working through a sequence of numbers or indices. For example, the following code segment computes and prints factorials from 1! to n! factorial, for a given n:


for (i = 1, factorial = 1; i <= n; factorial = factorial * i, i = i + 1)
   System.out.println (factorial);   

while Loops and do..while Loops

In addition to the for loop, Java contains two versions of a while loop, as found in C. These alternatives sometimes simplify code when a simple test is needed at the start or the end of a loop. These loop forms have the following syntax:


while (condition)               do
   statement;                      statement;
                                while (condition);

In the first case, the condition is evaluated, and the statement is executed if that condition is true. The loop continues until the condition becomes false.

In the second case, a statement is executed first, and then the condition is evaluated. If the condition is true, the statement is evaluated again. The loop continues until the condition becomes false.

Overall, the loop continues until the condition becomes false. In the first version, that condition is checked at the start, and the statement will not be executed at all if the condition is false initially. In the second version, the statements are always evaluated once, before the condition is checked. In both versions, you should use braces { } if you want to include multiple statements within the loop.

Example

The following code shows the above factorial computation (without the printing), translated to these two forms:


i = 1;
factorial = 1;
while (i <= n) {
  factorial = i*factorial;
  i = i + 1;
}

i = 1;
factorial = 1;
do
  { factorial = i*factorial;
    i = i + 1;}
while (i <= n);

Example: Approximating Pi

The following application, approximating Pi, illustrates several of the basic control structures in Java.

Problem

a circle inscribed within a square

Consider a square of side 2 in the plane, centered at the origin, so the square extends one unit along each axis in each direction.

Suppose a point P is picked at random in the square. What is the likelihood that P also will be within a circle of radius 1, centered at the origin?

Discussion

Mathematically, the desired probability depends on the relative area of the circle and the square. Since the circle and square have radius 1 and side 2, respectively, their areas are Pi and 4, respectively. Putting this together gives the following:

Probability (P in circle) = Area Circle / Area Square = Pi / 4.

A similar analysis applies if we restrict P to the first quadrant.

Applying this to an experiment, we might pick N points at random in the square in the first quadrant. We then could count the number I of points inside the circle. We would expect that

I / N = (approx) Pi / 4.

Solving for Pi gives

Pi = (approx) 4 I / N

To use this estimate in a program to approximate Pi, we need to be able to create random points in the square, determine their distance from the origin, and count if they are in the circle. This work is done in the following outline:


Code Outline

  1. Read number N of points to be selected.
  2. Set counter to 0.
  3. Repeat N times:
    1. Create a point P in the unit square in the first quadrant.
    2. Check if P's distance to the origin is less than or equal to 1.
    3. If so,increment counter by 1.
  4. Print number of times point was in circle.
  5. Print estimate of Pi by the formula, Pi = (approx) 4 I / N.

Implementing the Outline

In implementing the outline, we first consider what properties we need for points. In the outline, we must create points and determine how far they are from the origin. One simple approach for this task is to declare variables x and y as double precision real numbers. Given such a point, its distance from the origin is sqrt(x*x + y*y). To check if this is in the circle, one might test sqrt(x*x + y*y) <= 1.0. However, squaring this test gives an equivalent, but simpler, test: x*x + y*y <= 1.0

Random number operations are common in many languages. In Java, the mathematics library class contains such a mechanism to generate random numbers between 0 and 1, and we will use that library operation.

Code

The resulting program approxPi.java in package mathComputationsfollows the outline very closely. The program uses a random method (function), available from Java Math library. The first line

   import java.lang.Math

tells the compiler to look in the Math library for additional code (e.g., random in this case). According to the specification of random, the method returns a real number (a double) that is greater than or equal to zero and less than 1.0.

Arrays

Arrays in Java correspond to vectors in Scheme and arrays in C. That is, arrays provide a mechanism to store values, based on an index.

As with Scheme and C, work with an array involves two basic parts, declaration and use.

Application: The Sieve of Eratosthenes

In ancient Greece, Eratosthenes gave the following algorithm for determining all prime numbers up to a specified number M:

  1. Write down the numbers 2, 3, ..., M.
  2. Cross out numbers as follows:
    A. Keep 2, but cross out all multiples of 2 (i.e., cross out 4, 6, 8, ...).
    B. Keep 3, but cross out all multiples of 3 (i.e., cross out 6, 9, ...). (Note: While 6 is crossed out twice, it only matters that it has been crossed out. We attach no significance to the number of times the 6 is crossed out.)
    C. Since 4 is already crossed out, go on to the next number that is not crossed out (i.e., 5). Keep 5, but cross out all multiples of 5 (i.e., 5, 10, 15, ...).
    General Step Suppose you have just processed the number P. Go on to the next number that is not crossed out -- Q. Keep Q, but cross out all multiples of Q.
  3. After you have finished all the crossing out, the numbers remaining are primes.

In translating this outline to a program, we will need to consider how to decide how to keep track of numbers and crossings out. One approach is to have an array crossedOut where crossedOut[i] is true if the value i has been crossed out previously and false if i has not been crossed out.

Program ~walker/java/examples/arrays/PrimeSieve.java follows the above outline closely. In the program, M is assigned a value at the start of the program, and the primes are printed at the end.

Some Simulations

Looping constructs and arrays apply in many contexts. One type of application involves simulation. Often these applications involve a random number generator.

Rolling a Die

The random method in the Math class may be used to simulate the rolling of a die as follows.

Math.random() returns a random number between 0.0 and 1.0, so the expression 6.0*Math.random() gives a random real number between 0.0 and 6.0, and 1.0+6.0*Math.random() gives a random real number between 1.0 and 7.0. Java's Math class also contains a floor which converts a real number to an integer by ignoring any value after the decimal point (i.e., by rounding down). Applying this to the previous expression gives floor(1.0 + 6.0*Math.random()), which is an expression which gives random integers between 1 and 6.

(Technical point: The previous expression could give 7 if Math.random() were exactly 1. However, for typical random number generators, Math.random() will not give exactly 1.0, although it can give 0.0. Thus, floor(1.0 + 6.0*Math.random()) can never give 7 -- only integers 1, 2, 3, 4, 5, 6.)


import java.lang.Math;

...

public static int roll () {
   return ((int)Math.floor(1.0 + 6.0*Math.random()));
}


This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/153.sp05/readings/reading-control-arrays.shtml

created 18 April 2000 for iteration and arrays
revised 24 March 2005 (while and do...while loops and arrays)
revised 22 January 2012 for conditionals, loops, and arrays
Valid HTML 4.01! Valid CSS!
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.


Copyright © 2011-2014 Henry M. Walker.
CC-BY-NC-SA
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License .