last revised March 24, 2005
| CSC 153: Computer Science Fundamentals | Grinnell College | Spring, 2005 |
| Laboratory Exercise Reading | ||
This reading introduces two Java constructs, while loops and arrays, and applies them to solve several problems.
The previous lab introduced the for loop as mechanism to iterate through a series of data or events.
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) out.println (factorial);
Java also contains two other types of loops that may simplify code when a simple test is needed at the start of 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);
Arrays in Java correspond to vectors in Scheme. That is, arrays provide a mechanism to store values, based on an index. As an example, program ~walker/java/examples/arrays/ArrayExample.java reads 10 numbers, prints them out in reverse order, and finds their maximum and minimum.
As this example shows, 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; int[] values = new int [Number];
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 this 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.
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 read from the keyboard, 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-iteration-arrays.shtml
|
created April 18, 2000 last revised March 24, 2005 |
|
| For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. |