revised 24 March 2005 (while and do...while loops and arrays)
revised 22 January 2012 for conditionals, loops, and arrays
| CSC 207 | Grinnell College | Spring, 2012 |
| Algorithms and Object-Oriented Design | ||
Quick index: control structures, approximating Pi, arrays, Sieve of Eratosthenes
This reading reviews some basic Java control structures and outlines the use of simple arrays. These constructs then are applied to solve several problems.
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 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 |
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;
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.
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.
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);
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.
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);
The following application, approximating Pi, illustrates several of the basic control structures in Java.
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?
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:
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.
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 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.
Array Declaration proceeds by declaring a variable. In the example, the relevant code is:
final int Number = 10; // final is optional here
int[] values = new int [Number];
// Java syntax allows either int[] values
// or int values []
The first declaration indicates that variable Number will be an integer initialized to 10. The extra word final at the start of that line indicates that the value of Number cannot be changed by the program. That is, Number will have the constant value 10.
The first part of the next line declares variable values as an array of integers. Specifically, int indicates the numbers in the array will be integers, and the brackets [] indicate there will be an array. The next part of the declaration initializes the variable values to be a new array of ints, and [Number] indicates the number of items in the array. As with C, the values will be accessed at index 0 through Number-1.
Rather than declare an array in one place and initialize it later, Java allows array initialization that is similar to C. Thus, the following declares and initializes values to an array of 11 ints.
final int Number = 10; // final is optional here
int[] values = { 3, 1, 4, 1, 5, 9 , 2, 6, 5, 3, 5} ;
Array Use: After an array is declared, elements within the array are accessed by providing an index (placed in brackets [ ] ). Thus, values[i] accesses the ith element of the array.
In ancient Greece, Eratosthenes gave the following algorithm for determining all prime numbers up to a specified number M:
| 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. |
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.
Looping constructs and arrays apply in many contexts. One type of application involves simulation. Often these applications involve a random number generator.
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 |
|
| For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. |
